Tài liệu tham khảo về môn cấu trúc dữ liệu | Môn: CẤU TRÚC DỮ LIỆU Chương 5: CÂY (TREE) NỘI DUNG CHƯƠNG 5 Khái niệm cây – Biểu diễn cây Cây nhị phân (Binary Tree) Định nghĩa Biểu diễn và các thao tác Cây nhị phân tìm kiếm (Binary Searching Tree) Cây cân bằng (Balanced Tree) Định nghĩa – Cấu trúc dữ liệu Các thao tác trên cây cân bằng BÀI TẬP niệm cây – Biểu diễn cây Định nghĩa cây . Một số khái niệm liên quan . Bậc của 1 cây . Bậc của 1 nút . Nút gốc . Nút kết thúc . Nút trung gian . Mức của 1 nút . Chiều cao (chiều sâu) của 1 cây . Nút trước, nút sau của 1 nút . Nút cha, nút con của 1 nút . Chiều dài đường đi của 1 nút . Chiều dài đường đi của 1 cây . Rừng niệm cây – Biểu diễn cây (tt) Đị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 | Môn: CẤU TRÚC DỮ LIỆU Chương 5: CÂY (TREE) NỘI DUNG CHƯƠNG 5 Khái niệm cây – Biểu diễn cây Cây nhị phân (Binary Tree) Định nghĩa Biểu diễn và các thao tác Cây nhị phân tìm kiếm (Binary Searching Tree) Cây cân bằng (Balanced Tree) Định nghĩa – Cấu trúc dữ liệu Các thao tác trên cây cân bằng BÀI TẬP niệm cây – Biểu diễn cây Định nghĩa cây . Một số khái niệm liên quan . Bậc của 1 cây . Bậc của 1 nút . Nút gốc . Nút kết thúc . Nút trung gian . Mức của 1 nút . Chiều cao (chiều sâu) của 1 cây . Nút trước, nút sau của 1 nút . Nút cha, nút con của 1 nút . Chiều dài đường đi của 1 nút . Chiều dài đường đi của 1 cây . Rừng niệm cây – Biểu diễn cây (tt) Đị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. niệm cây – Biểu diễn cây (tt) . Một số khái niệm liên quan . 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 đó . 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 . 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) . Nút kết thúc 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) niệm cây – Biểu diễn cây (tt) . Một số khái niệm liên quan (tt) . 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) . 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ó .
