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 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).
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 7: CâyChươ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 treeChươ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ướcChương 7: Cây (Tree) Tree – Ví dụ 5  Cây thư mụcChương 7: Cây (Tree) Tree – Ví dụ 6Chươ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ìnhChươ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 0Chươ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) + 1Chươ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 edgesChươ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 LenChương 7: Cây (Tree) Level One 16 Owner Jake Manager ChefLEVEL 1 Brad Carol Waitress Waiter Cook Helper Joyce Chris Max LenChương 7: Cây (Tree) Level Two 17 Owner Jake Manager Chef Brad CarolLEVEL 2 Waitress Waiter Cook Helper Joyce Chris Max LenChươ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 ...