Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 6: Cây và cây nhị phân

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 6: Cây và cây nhị phân

1. Click To EditNỘI Master DUNG Title Style CÂY VÀ CÂY NHỊ PHÂN Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 1
2. ĐịnhClick Nghĩa To Cây Edit Master Title Style Cây là một tập hợp T các phần tử (gọi là nút của cây), trong đĩ cĩ một nút đặc biệt gọi là nút gốc, các nút cịn lại được chia thành những tập rời nhau T1, T2, ,Tn theo quan hệ phân cấp, trong đĩ Ti cũng là 1 cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta gọi là quan hệ cha – con. Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 2
3. MộtClick Số Khái To Niệm Edit Master Title Style • Bậc của một nút: là số cây con của nút đĩ . • Bậc của một cây: là bậc lớn nhất của các nút trong cây • Nút gốc: là nút khơng cĩ nút cha. • Nút lá: là nút cĩ bậc bằng 0 . • Mức của một nút: – Mức (gốc (T) ) = 0. – Gọi T1, T2, T3, , Tn là các cây con của T0 : Mức (T1) = Mức (T2) = . . . = Mức (Tn) = Mức (T0) + 1. • Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x. Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 3
4. Ví DụClick 1 Tổ To Chức Edit Dạng Master Cây Title Style BB-Electronic Corp. R&D Kinh doanh Tài vụ Sản xuất Nội địa Quốc tế TV CD Amplier Châu âu Mỹ Các nước Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 4
5. CâyClick Nhị Phân To Edit Master Title Style • Mỗi nút cĩ tối đa 2 cây con Cây Cây con con trái phải Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 5
6. MộtClick Số Tính To Chất Edit Của Master Cây Nhị Title Phân Style • Số nút nằm ở mức i 2i. • Số nút lá 2h-1, với h là chiều cao của cây. • Chiều cao của cây h log2(N) – N = số nút trong cây • Số nút trong cây 2h-1. Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 6
7. CấuClick Trúc DữTo LiệuEdit CủaMaster Cây NhịTitle Phân Style typedef struct tagTNode { Data Key; struct tagTNode *pLeft; Key struct tagTNode *pRight; }TNode; typedef TNode *TREE; Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 7
8. Ví Dụ Cây Được Tổ Chức Trong Bộ Nhớ TrongClick To Edit Master Title Style 1f 2f 6 3f 3f 2f 7f 9 N N 4 5f 5f 7f N 5 N N 8 N Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 8
9. DuyệtClick Cây To Nhị Edit Phân Master Title Style . Cĩ 3 trình tự thăm gốc : . Duyệt trước . Duyệt giữa . Duyệt sau . Độ phức tạp O (log2(h)) Trong đĩ h là chiều cao cây Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 9
10. Ví DụClick Kết ToQuả Edit Của Master Phép Duyệt Title Cây Style 9 2 8 1 6 5 7 10 3 12 4 • NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4. • LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4. • Kết quả của phép duyệt : LRN, NRL,LRN, LNR? Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 10
11. DuyệtClick Trước To Edit Master Title Style void NLR(TREE Root) { if (Root != NULL) { ; //Xử lý tương ứng theo nhu cầu NLR(Root->pLeft); NLR(Root->pRight); } } Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 11
12. DuyệtClick Giữa To Edit Master Title Style void LNR(TREE Root) { if (Root != NULL) { LNR(Root->pLeft); ; // Xử lý tương ứng theo nhu cầu LNR(Root->pRight); } } Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 12
13. DuyệtClick Sau To Edit Master Title Style void LRN(TREE Root) { if (Root != NULL) { LRN(Root->pLeft); LRN(Root->pRight); ; // Xử lý tương ứng theo nhu cầu } } Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 13
14. BiểuClick Diễn Cây To TổngEdit Quát Master Bằng TitleCây Nhị Style Phân A B E C A F H D B C D G I J E F G H I J Cấu trúc dữ liệu 1 vá giảivá 1 thuậtliệu dữ trúc Cấu CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 14