Chapter 5: CÂY (TREE)

1.2. Một số khái niệm cơ bản1.2.a. Bậc của 1 nútBậc của 1 nút (node’s degree) là số cây con của nút đó1.2.b. Bậc của 1 câyBậc của 1 cây (tree’s degree) là bậc lớn nhất của các nút trong câyCây có bậc N gọi là cây N phân1.2.c. Nút gốcNút gốc (root’s tree) là nút không phải là nút gốc cây con của bất kỳ 1 cây con nào khác trong cây (nút không làm gốc cây con)1.2.d. Nút lá Nút kết thúc hay còn gọi nút lá (leaf’s node) là nút có bậc = 0 (nút không có...
Nội dung trích xuất từ tài liệu:
Chapter 5: CÂY (TREE)Môn: CẤU TRÚC DỮ LIỆU Chương 5: CÂY (TREE) 1 NỘI DUNG CHƯƠNG 5 Khái niệm cây – Biểu diễn cây1. Cây nhị phân (Binary Tree)2. Định nghĩa 1. Biểu diễn và các thao tác 2. Cây nhị phân tìm kiếm (Binary Searching Tree) 3. Cây cân bằng (Balanced Tree)3. Định nghĩa – Cấu trúc dữ liệu 1. Các thao tác trên cây cân bằng 2.BÀI TẬP 2 1.Khái niệm cây – Biểu diễn cây1.1 Định nghĩa cây1.2. Một số khái niệm liên quan 1.2.a. Bậc của 1 cây 1.2.b. Bậc của 1 nút 1.2.c. Nút gốc 1.2.d. Nút kết thúc 1.2.e. Nút trung gian 1.2.f. Mức của 1 nút 1.2.g. Chiều cao (chiều sâu) của 1 cây 1.2.h. Nút trước, nút sau của 1 nút 1.2.i. Nút cha, nút con của 1 nút 1.2.j. Chiều dài đường đi của 1 nút 1.2.k. Chiều dài đường đi của 1 cây 1.2.l. Rừng 3 1.Khái niệm cây – Biểu diễn cây (tt)1.1 Định nghĩa cây Cây là một tập hợp các phần tử (nút) được tổ chức và có các đặc điểm Hoặc là tập hợp rỗng (cây rỗng)  Hoặc là tập hợp khác rỗng trong đó có 1 nút duy nhất làm  nút gốc (Root’s Node), các nút còn lại được phân thành các nhóm trong đó mỗi nhóm là 1 cây con (Sub-Tree) Các cây con cũng có thể là tập rỗng hay khác rỗng trong đó có 1 nút là gốc cây con. 4 1.Khái niệm cây – Biểu diễn cây (tt)1.2. Một số khái niệm cơ bản1.2.a. Bậc của 1 nút Bậc của 1 nút (node’s degree) là số cây con của nút đó1.2.b. Bậc của 1 cây Bậc của 1 cây (tree’s degree) là bậc lớn nhất của các nút trong cây Cây có bậc N gọi là cây N phân1.2.c. Nút gốc Nút gốc (root’s tree) là nút không phải là nút gốc cây con c ủa bất kỳ 1 cây con nào khác trong cây (nút không làm g ốc cây con)1.2.d. Nút lá Nút kết thúc hay còn gọi nút lá (leaf’s node) là nút có b ậc = 0 (nút không có nút cây con) 5 1.Khái niệm cây – Biểu diễn cây (tt)1.2. Một số khái niệm liên quan (tt)1.2.e. Nút trung gian Nút trung gian hay còn gọi nút giữa (interior’s node) là nút không phải là nút gốc và cũng không phải nút kết thúc (nút có bậc khác không và là nút gốc của cây con nào đó trong cây)1.2.f. Mức của 1 nút Mức của 1 nút (node’s level) bằng mức của nút gốc cây con chứa nó +1. Mức của nút gốc = 11.2.g. Chiều cao (chiều sâu) của 1 cây Chiều cao (chiều sâu) của 1 cây (tree’s height | tree’s depth) là mức cao nhất của 1 nút trong cây1.2.h. Nút trước, nút sau của 1 nút Nút T được gọi là nút trước của 1 nút (ancestor’s node) c ủa nút S nếu cây con có gốc là T chứa cây con có gốc là S. Khi đó S được gọi là nút sau của nút T (descendant’s node) 6 1.Khái niệm cây – Biểu diễn cây (tt)1.2. Một số khái niệm liên quan (tt)1.2.i. Nút cha, nút con của 1 nút Nút B được gọi là nút cha (parent’s node) của nút C n ếu nút B là nút trước của nút B và mức của nút C lớn h ơn m ức c ủa B là 1 mức. Khi đó nút C được gọi là nút con (child’s node) của B1.2.j. Chiều dài đường đi của 1 nút Chiều dài đường đi của 1 nút là số đỉnh (số nút) tính t ừ nút gốc để đi đến nút đó. Chiều dài đường đi của nút gốc luôn = 1, chiều dài đường đi tới 1 nút bằng chiều dài đường đi tới nút cha của nó + 1 7 1.Khái niệm cây – Biểu diễn cây (tt)1.2. Một số khái niệm liên quan (tt)1.2.k. Chiều dài đường đi của 1 cây Chiều dài đường đi của 1 cây (path’s length of the tree) là tổng tất cả các chiều dài đường đi của tất cả các nút trên cây (chiều dài đường đi trong internal path’s length). Tính chiều dài đường đi ngoài (external path’s length) b ằng cách mở rộng tất cả các nút của cây sao cho các nút của cây có cùng bậc (thêm vào các nút giả) với bậc của cây. Chiều dài đường đi ngoài bằng tổng chiều1.2.l. Rừng. Rừng (forest) là tập hợp các cây. Khi cây mất gốc  rừng 8 1.Khái niệm cây – Biểu diễn cây (tt)1.3. Biểu diễn cây Dùng đồ thị, Dùng giản đồ tập hợp, Sử dụng dạng phân cấp chỉ sốBIỂU DIỄN CÂY TRONG BỘ NHỚ MÁY TÍNH Để biểu diễn cây trong bộ nhớ máy tính dùng danh sách liên kết. Để biểu diễn cây N-phân dùng danh sách có N mối liên kết để quản lý N địa chỉ nút con. Cấu trúc dữ liệu của cây N-phân tương tự cấu trúc dữ liệu đa liên kết.const int N = 100;typedef struct NTNode{ T Key; NTNode * SubNode[N];}NTOneNode;typedef struct NTOneNode * NTType;Để quản lý cây, chỉ cần quản lý địa chỉ nút gốc NTType NTree; 9 ...