Bài 6 : CÂY VÀ CÂY NHỊ PHÂN | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
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 TI, T2, …,Tn theo quan hệ phân cấp, trong đó Ti cũng là 1 cây. Bài giảng giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao
Môn: Cấu trúc dữ liệu và giải thuật (IT003)
Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Thông tin:
Tác giả:
Thông tin :
Môn:
Cấu trúc dữ liệu và giải thuật (IT003)
Trường:
Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Tác giả:
Tài liệu liên quan:
Preview text:
Click To Edit Master NỘI T DUNG itle Style ải gi CÂY VÀ CÂY NHỊ PHÂN
ẬT 1 ật UthuẢI THá GI1 v VÀ liệu LIỆUỮ DCÚ TR u trúc dữ ẤU C Cấ 1 Clic Định k To Edi
Nghĩa Cây t 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 ải những tập rời nhau T , …,T theo quan hệ gi , T 1 2 n ẬT 1 ật Uthu
phân cấp, trong đó T cũng là 1 cây. Mỗi nút ở i ẢI TH á GI 1 v
cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ VÀ liệu LIỆUỮ
này người ta gọi là quan hệ cha – con. D C Ú TR u trúc dữ ẤU C Cấ 2 Clic Một k To Edit
Số Khái Niệm 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 . ải
gi • Mức của một nút: ẬT 1 ật Uthu – Mức (gốc (T) ) = 0. ẢI TH á GI
– Gọi T1, T2, T3, ... , Tn là các cây con của T0 : 1 v VÀ
Mức (T1) = Mức (T2) = . . . = Mức (Tn) = Mức (T0) liệu LIỆU + 1. Ữ D C
• Độ dài đường đi từ gốc đến nút x: là số nhánh Ú TR u trúc dữ
cần đi qua kể từ gốc đến x. ẤU C Cấ 3 Ví Clic Dụ k To Edi 1 Tổ Chức t Master Dạng Cây Title Style BB-Electronic Corp. R&D Kinh doanh Taøi vuï Saûn xuaát ải giẬT 1 ật U Noäi ñòa Quoác teá TV CD Amplier thuẢI THá GI1 v VÀ liệu Chaâu aâu Myõ Caùc nöôùc LIỆU Ữ D C Ú TR u trúc dữ ẤU C Cấ 4 Clic Cây k T Nhị P o Edi hân t Master Title Style
• Mỗi nút có tối đa 2 cây con Caây Caây con ải con gi traùi phaûi
ẬT 1 ật UthuẢI THá GI1 v VÀ liệu LIỆUỮ DCÚ TR u trúc dữ ẤU C Cấ 5 Clic Một k Số T To Edit ính Chất Master Của Cây Title Styl Nhị Phân e
• 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.
ải • Chiều cao của cây h giẬT 1 ật log2(N)
U thuẢI THá – N = số nút trong cây GI 1 v VÀ
• Số nút trong cây 2h-1. liệu LIỆUỮ D C Ú TR u trúc dữ ẤU C Cấ 6 Clic Cấu k To Edit Master Trúc Dữ Liệu Của Title Styl Cây Nhị Phân e typedef struct tagTNode { Data Key; struct tagTNode *pLeft; Key struct tagTNode *pRight; ải }TNode; giẬT 1 ật U
thuẢI THá typedef TNode *TREE; GI 1 v VÀ liệu LIỆUỮ D C Ú TR u trúc dữ ẤU C Cấ 7
Ví Dụ Cây Được Tổ Chức Trong Bộ Nhớ
Click To Edit Master Title Style Trong 1f 2f 6 3f 3f ải 2f gi 7f 9 N ẬT 1 ật N 4 5f
U thuẢI THá GI1 v VÀ 5f 7f liệu LIỆU N 5 N N 8 N Ữ D C Ú TR u trúc dữ ẤU C Cấ 8 Clic Duyệt k T Cây o Edit Master Nhị Phân Title Style
Có 3 trình tự thăm gốc : Duyệt trước Duyệt giữa Duyệt sau ải
gi Độ phức tạp O (log2(h)) ẬT 1 ật Uthu
Trong đó h là chiều cao cây ẢI TH á GI 1 v VÀ liệu LIỆUỮ DCÚ TR u trúc dữ ẤU C Cấ 9 Ví Clic Dụ k To Edit Master
Kết Quả Của Phép Title Styl Duyệt Cây e 9 2 8 1 6 5 7 ải giẬT 1 ật Uthu 10 ẢI TH á GI 1 v 3 12 4 VÀ
liệu • NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4. LIỆU Ữ D • C
LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4. Ú
TR u trúc dữ • Kết quả của phép duyệt : LRN, NRL,LRN, LNR? ẤU C Cấ 10 Clic Duyệt k To Edi Trước t Master Title Style void NLR(TREE Root) { if (Root != NULL) { ải
; //Xử lý tương ứng theo nhu cầu gi NLR(Root->pLeft);
ẬT 1 ật Uthu NLR(Root->pRight); ẢI TH á GI 1 v } VÀ liệu } LIỆU Ữ D C Ú TR u trúc dữ ẤU C Cấ 11 Clic Duyệt k To Edi Giữa t Master Title Style void LNR(TREE Root) { if (Root != NULL) { ải LNR(Root->pLeft);
giẬT 1 ật ; // Xử lý tương ứng theo nhu U thu cầu ẢI TH á GI 1 v LNR(Root->pRight); VÀ liệu LIỆU } Ữ D C } Ú TR u trúc dữ ẤU C Cấ 12 Clic Duyệt k T Sau o Edit Master Title Style void LRN(TREE Root) { if (Root != NULL) { ải LRN(Root->pLeft);
giẬT 1 ật U LRN(Root->pRight);
thuẢI THá ; // Xử lý tương ứng theo nhu GI 1 v VÀ cầu liệu LIỆU Ữ } D C Ú } TR u trúc dữ ẤU C Cấ 13 Biể Clic u k Diễn To Edi Cây Tổ t ng Master Quát Bằn T g itle Styl Cây Nhị e Phâ n A B E C A ải giẬT 1 ật F H D U thuẢI THá B C D GI 1 v G I VÀ liệu LIỆUỮ J D C E F G H I J Ú TR u trúc dữ ẤU C Cấ 14