intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST
Báo xấu
43
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

"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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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.com 1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  2. 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. 2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  3. 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. 3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  4. 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: 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ân 4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  5. 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. A A B B C C Cây lệch trái Cây lệch phải 5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  6. 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. Ví dụ: Với k=3, số node trên cây A nhị 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à 3 6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  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) A A B E B E C D C D F Ví dụ về cây nhị phân hoàn chỉnh 7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  8. 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 đủ. 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ỉnh 8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  9. 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. A A B E B E C D C D F Ví dụ về cây nhị phân cân bằng 9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  10. 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
  11. 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ớ. 1 A A 2 B 3 C B C 4 D 5 E 6 F D E F G 7 G 8 H I 9 10 H 11 I Ô nhớ lãng phí 11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  12. 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. Left index Data Right index 12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  13. 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. Left index Data Right index 2 1. A 3 A 4 2. B 5 6 3. C 7 B C 0 4. D 0 8 5. E 9 D E F G 0 6. F 0 0 7. G 0 H I 0 8. H 0 0 9. I 0 13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  14. 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 Left ptr Data Right ptr Biểu diễn trên ngôn ngữ C: struct tnode { TreeEntry data; struct tnode *lchild,*rchild; }; 14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  15. 19.2. Biểu diễn cây nhị phân (6/6) A B C D NULL NULL NULL NULL Ví dụ về biểu diễn cây dạng liên kết 15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  16. 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). 16 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  17. 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. 17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  18. 19.3. Duyệt cây nhị phân (3/9) Duyệt tiền thứ tự (Preorder): NLR void NLR(Tree root) 1 { A if (root != NULL) { 2 7 B C xử lý root; NLR (root->left); 3 4 8 9 NLR (root->right); D E F G } } 5 6 H I Thứ tự đã duyệt: A B D E H I C F G 18 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  19. 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. 19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  20. 19.3. Duyệt cây nhị phân (5/9) Duyệt trung thứ tự (Inorder): LNR void LNR(Tree root) 6 { A if (root != NULL) 2 8 { B C LNR(root->left); 1 4 7 9 xử lý root; D E F G LNR(root->right); } 3 5 H I } Thứ tự đã duyệt: D B H E I A F C G 20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
73=>1