Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 19: Cây nhị phân

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 19: Cây nhị phân" trình bày những kiến thức về khái niệm về cây nhị phân, biểu diễn cây nhị phân, duyệt cây nhị phân.
Nội dung trích xuất từ 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 Cấu trúc dữ liệu và giải thuật Bài 19. Cây nhị phân Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical UniversityBài 19: Cây nhị phânNộ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.2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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.3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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: A Số node tối đa trên cây nhị B C phân tại mức i là 2i−1 Nếu k là độ sâu của cây thì số D E F G phần tử tối đa trên cây là: 2k − 1 = 2k−1 + 2k−2 + … + 20 H I Ví dụ về cây nhị phân4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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. A A B B C C Cây lệch trái Cây lệch phải5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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.Ví dụ: Với k=3, số node trên cây Anhị phân đầy đủ là 23-1=7 B E C D F G Ví dụ về cây nhị phân đầy đủ có độ cao là 36 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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) A A B E B E C D C D F Ví dụ về cây nhị phân hoàn chỉnh7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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 đủ. A A B E B E C D F G C D F Cây nhị phân đầy đủ Cây nhị phân hoàn chỉnh8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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. A A B E B E C D C D F Ví dụ về cây nhị phân cân bằng9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19.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 (119.2. Biểu diễn cây nhị p ...