Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 7: Cây

Chia sẻ: Vdgv Vdgv | Ngày: | Loại File: PDF | Số trang:131

Thêm vào BST

Báo xấu

128
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 7 Cây nằm trong bài giảng cấu trúc dữ liệu và thuật toán nhằm trình bày về các nội dung chính như sau: cấu trúc cây (Tree), cấu trúc cây nhị phân (Binary Tree), cấu trúc cây nhị phân tìm kiếm (Binary Search Tree) và cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 7: Cây

Chương 7: CÂY (Tree)
Nội dung 2  Cấu trúc cây (Tree)  Cấu trúc cây nhị phân (Binary Tree)  Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)  Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree) Chương 7: Cây (Tree)
Tree – Định nghĩa 3  Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó có 1 nút đặc biệt được gọi là gốc, các nút còn lại được chia thành những tập rời nhau T1, T2 , ... , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây  A tree is a set of one or more nodes T such that:  i. there is a specially designated node called a root  ii. The remaining nodes are partitioned into n disjointed set of nodes T1, T2,…,Tn, each of which is a tree Chương 7: Cây (Tree)
Tree – Ví dụ 4  Sơ đồ tổ chức của một công ty Công ty A R&D Kinh doanh Tài vụ Sản xuất Nội địa Quốc tế TV CD Amplier Châu âu Mỹ Các nước Chương 7: Cây (Tree)
Tree – Ví dụ 5  Cây thư mục Chương 7: Cây (Tree)
Tree – Ví dụ 6 Chương 7: Cây (Tree)
Tree – Ví dụ Chương 7: Cây (Tree)
Tree – Ví dụ 8  Không phải cây Nhận xét: Trong cấu trúc cây không tồn tại chu trình Chương 7: Cây (Tree)
Tree - Một số khái niệm cơ bản 9  Bậc của một nút (Degree of a Node of a Tree):  Là số cây con của nút đó. Nếu bậc của một nút bằng 0 thì nút đó gọi là nút lá (leaf node)  Bậc của một cây (Degree of a Tree):  Là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân  Nút gốc (Root node):  Là nút không có nút cha  Nút lá (Leaf node):  Là nút có bậc bằng 0 Chương 7: Cây (Tree)
Tree - Một số khái niệm cơ bản 10  Nút nhánh:  Là nút có bậc khác 0 và không phải là gốc  Mức của một nút (Level of a Node):  Mức (gốc (T) ) = 0  Gọi T1, T2, T3, ... , Tn là các cây con của T0 Mức(T1) = Mức(T2) = ... = Mức(Tn) = Mức(T0) + 1 Chương 7: Cây (Tree)
Tree – Ví dụ Chương 7: Cây (Tree)
Tree – Ví dụ 12 Nút gốc (root node) Owner Manager Chef Waitress Waiter Cook Helper nút lá (leaf node) Chương 7: Cây (Tree)
Tree – Ví dụ 13 Tree nodes Tree edges Chương 7: Cây (Tree)
Tree – Ví dụ 14 Gốc(root) Nút trong cha và con lá Chương 7: Cây (Tree)
A Tree Has Levels 15 LEVEL 0 Owner Jake Manager Chef Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len Chương 7: Cây (Tree)
Level One 16 Owner Jake Manager Chef LEVEL 1 Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len Chương 7: Cây (Tree)
Level Two 17 Owner Jake Manager Chef Brad Carol LEVEL 2 Waitress Waiter Cook Helper Joyce Chris Max Len Chương 7: Cây (Tree)
Định nghĩa Node 0 là tổ tiên của tất cả các node 18 Gốc Nodes 1-6 là con cháu của node 0 Node 0 Node 1,2,3 con của gốc Node 1 Node 2 Node 3 Node 1 là cha của Nodes 4,5 Node 4 Node 5 Node 6 lá Node 4, 5 là anh em Chương 7: Cây (Tree)
Một số khái niệm cơ bản 19  Độ dài đường đi từ gốc đến nút x: Px = số nhánh cần đi qua kể từ gốc đến x  Độ dài đường đi tổng của cây: PT   PX XT trong đó Px là độ dài đường đi từ gốc đến X  Độ dài đường đi trung bình: PI = PT/n (n là số nút trên cây T)  Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng Chương 7: Cây (Tree)
Depth-first Search 20 Chương 7: Cây (Tree)