Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 19: Cây nhị phân - Ngô Hữu Phước

19.1. Khái niệm về cây nhị phân (1/7) 19.1.1. Giới thiệu và định nghĩa:  Cây nhị phân là trường hợp đặc biệt của cây, trong đó không có node nào trên cây có bậc lớn hơn 2.  Do đó cây nhị phân T có thể định nghĩa:  Có một node đặc biệt trên cây gọi là root của cây.  Các node khác trên cây được chia thành 2 tập T1 và T2, trong đó chúng cũng là cây nhị phân.  Cây con T1 được gọi là cây con bên trái.  Cây con T2 được gọi là cây con bên phải. 19.1. Khái niệm về cây nhị phân (2/7) Từ định nghĩa cây nhị phân ta nhận thấy rằng:  Số node tối đa trên cây nhị phân tại mức i là 2i−1  Nếu k là độ sâu của cây thì số phần tử tối đa trên cây là: 2k − 1 = 2k−1 + 2k−2 + + 20

pdf24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 177 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 19: Cây nhị phân - Ngô Hữu Phước, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 19. Cây nhị phân @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University1 Bài 19: Cây nhị phân Nội dung: 19.1. Khái niệm về cây nhị phân. 19.2. Biểu diễn cây nhị phân. 19.4. Duyệt cây nhị phân. Tham khảo: 1. Deshpande Kakde: C and Data structures.chm, Chapter 21: Trees 2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 5: Trees 3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 9 Trees. 4. Bài giảng TS Nguyễn Nam Hồng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University2 19.1. Khái niệm về cây nhị phân (1/7) 19.1.1. Giới thiệu và định nghĩa:  Cây nhị phân là trường hợp đặc biệt của cây, trong đó không có node nào trên cây có bậc lớn hơn 2.  Do đó cây nhị phân T có thể định nghĩa:  Có một node đặc biệt trên cây gọi là root của cây.  Các node khác trên cây được chia thành 2 tập T1 và T2, trong đó chúng cũng là cây nhị phân.  Cây con T1 được gọi là cây con bên trái.  Cây con T2 được gọi là cây con bên phải. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University3 19.1. Khái niệm về cây nhị phân (2/7) Từ định nghĩa cây nhị phân ta nhận thấy rằng:  Số node tối đa trên cây nhị phân tại mức i là 2i−1  Nếu k là độ sâu của cây thì số phần tử tối đa trên cây là: 2k − 1 = 2k−1 + 2k−2 + + 20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University4 A B C GD H E I F Ví dụ về cây nhị phân 19.1. Khái niệm về cây nhị phân (3/7) Cây lệch: Trong thực tế, có dạng đặc biệt: cây lệch. Cây lệch là cây chỉ có cây con trái hoặc phải. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University5 A B C A B C Cây lệch trái Cây lệch phải 19.1. Khái niệm về cây nhị phân (4/7) Cây nhị phân đầy đủ (Full binary tree):  Cây nhị phân đầy đủ có độ cao là k thì các node ở mức thấp hơn có đủ con trái và phải.  Như vậy, với cây nhị phân đầy đủ có độ cao là k thì số node trên cây là 2k-1. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University6 A B C E F G Ví dụ về cây nhị phân đầy đủ có độ cao là 3 D Ví dụ: Với k=3, số node trên cây nhị phân đầy đủ là 23-1=7 19.1. Khái niệm về cây nhị phân (5/7) Cây nhị phân hoàn chỉnh (Complete binary tree):  Cây nhị phân hoàn chỉnh có độ cao là k, với độ cao k-1 là đầy đủ.  Tại độ cao là k, các node được đưa vào cây từ trái sang phải.  Nhận xét:  Các node tại mức k-2 về trước có đủ 2 con.  Các node ở mức k-1 có thể có 2 con hoặc 1 con. Nếu có 1 con trì có con trái (các node cùng mức trước đó đã có 2 con) @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University7 A B C E F Ví dụ về cây nhị phân hoàn chỉnh D A B C E D 19.1. Khái niệm về cây nhị phân (6/7) So sánh giữa cây nhị phân đầy đủ và hoàn chỉnh:  Cây nhị phân đầy đủ là trường hợp riêng của cây nhị phân hoàn chỉnh.  Cây nhị phân hoàn chỉnh chưa chắc đã là cây nhị phân đầy đủ. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University8 A B C E F Cây nhị phân hoàn chỉnh D A B C E D F G Cây nhị phân đầy đủ 19.1. Khái niệm về cây nhị phân (7/7) Cây nhị phân cân bằng (Balanced binary tree):  Cây nhị phân cân bằng là cây mà tại mỗi node độ cao cây con trái và phải không lệch nhau quá 1. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University9 A B C E F Ví dụ về cây nhị phân cân bằng D A B C E D 19.2. Biểu diễn cây nhị phân (1/6)  Với cây nhị phân hoàn chỉnh có thể biểu diễn cây bằng mảng có n phần tử.  Nếu cây nhị phân hoàn chỉnh được biểu diễn dưới dạng mảng, giá trị của phần tử thứ i sẽ được chứa trong mảng tại vị trí thứ i (1<=i<=n).  Khi đó, phần tử “cha” của i sẽ là i/2 và 2 con của node i sẽ là 2i và 2i+1. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University10 A1 2 3 4 5 A B D C E B C D E Biểu diễn cây nhị phân hoàn chỉnh bằng mảng 19.2. Biểu diễn cây nhị phân (2/6)  Với cây nhị phân bất kỳ cũng có thể biểu diễn dạng mảng.  Tuy nhiên, cách biểu diễn trên gây lãng phí bộ nhớ. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University11 A1 A B D C E F G H I B C D E F G H I 2 3 4 5 6 7 8 9 10 11 Ô nhớ lãng phí 19.2. Biểu diễn cây nhị phân (3/6)  Với cách biểu diễn trên có ưu điểm là có khả năng truy cập dữ liệu nhanh. Tuy nhiên, nhược điểm chính là lãng phí ô nhớ.  Có thể biểu diễn cây dạng mảng, trong đó, mỗi node sẽ có cấu trúc:  Dữ liệu của node.  Chỉ số của node con trái.  Chỉ số của node con phải. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University12 Data Right indexLeft index 19.2. Biểu diễn cây nhị phân (4/6)  Ví dụ về biểu diễn cây nhị phân. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13 Data Right indexLeft index A B D C E F G H I 1. A 32 2. B 54 3. C 76 4. D 00 5. E 98 6. F 00 7. G 00 8. H 00 9. I 00 19.2. Biểu diễn cây nhị phân (5/6)  Việc biểu diễn cây dạng mảng không phù hợp với việc thường xuyên thêm bớt trên cây. Chi phí cho việc thêm bớt quá lớn. Do đó, ta có thể biểu diễn cây dạng liên kết. Trong trường hợp này, mỗi phần tử sẽ có 3 thành phần:  Thành phần dữ liệu,  Con trỏ liên kết trái,  Con trỏ liên kết phải @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University14 Data Right ptrLeft ptr Biểu diễn trên ngôn ngữ C: struct tnode { TreeEntry data; struct tnode *lchild,*rchild; }; 19.2. Biểu diễn cây nhị phân (6/6) @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University15 A B C D NULL NULL NULL NULL Ví dụ về biểu diễn cây dạng liên kết 19.3. Duyệt cây nhị phân (1/9)  Đối với cây nói chung, cây nhị phân nói riêng, dữ liệu được lấy ra phụ thuộc vào cách duyệt cây.  Thông thường, có 4 cách duyệt cây sau:  Duyệt tiền thứ tự (PreOrder): NLR.  Duyệt hậu thứ tự (PostOrder): LRN.  Duyệt trung thứ tự (InOrder): LNR  Duyệt theo chiều rộng (LevelOrder). @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University16 19.3. Duyệt cây nhị phân (2/9) Duyệt tiền thứ tự (Preorder): NLR 1. Thăm node đang xét trước các node con của nó. 2. Thăm cây con bên trái. 3. Thăm cây con bên phải. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University17 19.3. Duyệt cây nhị phân (3/9) Duyệt tiền thứ tự (Preorder): NLR Thứ tự đã duyệt: A B D E H I C F G @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University18 void NLR(Tree root) { if (root != NULL) { xử lý root; NLR (root->left); NLR (root->right); } } A B C D E F G 1 2 3 4 5 6 7 8 9 H I 19.3. Duyệt cây nhị phân (4/9) Duyệt trung thứ tự (Inorder): LNR 1. Thăm cây con bên trái của node đang xét trước. 2. Thăm node đang xét. 3. Thăm cây con bên phải của node đang xét. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19 19.3. Duyệt cây nhị phân (5/9) Duyệt trung thứ tự (Inorder): LNR Thứ tự đã duyệt: D B H E I A F C G @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University20 void LNR(Tree root) { if (root != NULL) { LNR(root->left); xử lý root; LNR(root->right); } } A B C D E F G 6 2 1 4 3 5 8 7 9 H I 19.3. Duyệt cây nhị phân (6/9) Duyệt hậu thứ tự (Postorder): LRN 1. Thăm cây con bên trái của node đang xét trước. 2. Thăm cây con bên phải của node đang xét trước. 3. Thăm node đang xét. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University21 19.3. Duyệt cây nhị phân (7/9) Duyệt hậu thứ tự (Postorder): LRN Thứ tự đã duyệt: D H I E B F G C A @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University22 void LRN(Tree root) { if (root != NULL) { LRN (root->left); LRN (root->right); xử lý root; } } A B C D E F G 9 5 1 4 2 3 8 6 7 H I 19.3. Duyệt cây nhị phân (8/9)  Thăm các node bắt đầu từ mức thấp nhất cho đến các mức cao.  Tại mỗi mức, thăm từ con trái trước, sau đó thăm con phải.  Sử dụng queue hỗ trợ trong quá trình duyệt cây.  Phương pháp này còn được gọi là Level-Order Traversal. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University23 19.3. Duyệt cây nhị phân (9/9) Thứ tự đã duyệt: A B C D G H I E F @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University24 A B C D E F G 1 2 4 5 8 9 3 6 7 H I
Tài liệu liên quan