Cấu trúc dữ liệu và giải thuật - chương 10

Cây nhị phân đầy đủ, gần đầy đủ: đầy đủ các node lá luôn nằm ở mức cao nhất và các nút không là nút lá có đầy đủ 2 nhánh con. Để nắm vững các tính chất của cây nhị phân mời các bạn tham khảo thêm chi tiết về chương 10.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - chương 10 A CCẤU TRÚC DỮ LIỆU VÀ B F GIẢI THUẬT (501040) D E G Chương 10: Cây nhị phân K H Định nghĩa Cây nhị phân Cây rỗng Hoặc có một node gọi là gốc (root) và 2 cây con gọi là cây con trái và cây con phải Ví dụ: Cây rỗng: Cây có 1 node: là node gốc Cây có 2 node: 2 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Các định nghĩa khác Mức: Node gốc ở mức 0. Node gốc của các cây con của một node ở mức m là m+1. Chiều cao: Cây rỗng là 0. Chiều cao lớn nhất của 2 cây con cộng 1 (Hoặc: mức lớn nhất của các node cộng 1) Đường đi (path) Tên các node của quá trình đi từ node gốc theo các cây con đến một node nào đó. 3 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Các định nghĩa khác (tt.) Node trước, sau, cha, con: Node x là trước node y (node y là sau node x), n ếu trên đường đi đến y có x. Node x là cha node y (node y là con node x), nếu trên đường đi đến y node x nằm ngay trước node y. Node lá, trung gian: Node lá là node không có cây con nào. Node trung gian không là node gốc hay node lá. 4 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Các tính chất khác Cây nhị phân đầy đủ, gần đầy đủ: Đầy đủ: các node lá luôn nằm ở mức cao nhất và các nút không là nút lá có đầy đủ 2 nhánh con. Gần đầy đủ: Giống như trên nhưng các node lá nằm ở mức cao nhất (hoặc trước đó một mức) và lấp đầy từ bên trái sang bên phải ở mức cao nhất. Chiều cao của cây có n node: Trung bình h = [lg n] + 1 Đầy đủ h = lg (n + 1) Suy biến h = n Số phần tử tại mức i nhiều nhất là 2i 5 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Phép duyệt cây Duyệt qua từng node của cây (mỗi node 1 lần) Cách duyệt: Chính thức: NLR, LNR, LRN, NRL, RNL, RLN Chuẩn: NLR (preorder), LNR (inorder), LRN (postorder) 6 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Ví dụ về phép duyệt cây NLR A B C D E F G H I J K L M N O P Kết quả: A B D H I N E J O K C F L P G M 7 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Ví dụ về phép duyệt cây LNR A B C D E F G H I J K L M N O P Kết quả: H D N I B J O E K A F P L C M G 8 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Ví dụ về phép duyệt cây LRN A B C D E F G H I J K L M N O P Kết quả: H N I D O J K E B P L F M G C A 9 Chương 10. Cây nhị phân Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM ...