cay nhi phan

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.02 MB, 66 trang )

(1)CÂY NHỊ PHÂN TÌM KIẾM. 1. TMT.

(2) NộI DUNG 1. 2. 3. 4. 5. 6. 7.. Các khái niệm Đặc điểm Hình dạng Các khái niệm Định nghĩa kiểu dữ liệu Các lưu ý khi cài đặt Các thao tác. 2.

(3) CÁC KHÁI NIệM Bậc của một nút: là số cây con của nút đó.  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.  Nút nhánh: là nút có bậc khác 0 và không phải là gốc. . 2 2. 2. 0. 1. 1. 0. 0. 0. 3.

(4) CÁC KHÁI NIệM (TT) Độ 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.  Độ cao của cây: Độ dài đường đi từ gốc đến nút lá ở mức thấp nhất. . Mức 0 Mức 1. Mức 2. Mức 3. 4.

(5) ĐặC ĐIểM CÂY NHị PHÂN TÌM KIếM Là cây nhị phân  Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải Nút có giá trị nhỏ nhất nằm ở 40 40 trái nhất của cây Nút có giá trị lớn nhất nằm ở phải nhất của cây . 77 33. 36 36. 11. 66 44. 15 15 23 23. 5.

(6) ĐịNH NGHĨA KIểU Dữ LIệU Nút Trỏ trái. Giá trị. Trỏ phải. TNODE. Key. pLeft. typedef struct TNODE { <Data> Key; struct TNODE *pLeft, *pRight; } *TREE;. pRight. 6.

(7) VÍ Dụ KHAI BÁO CÂY NHị PHÂN BIểU DIễN CÁC NODE LÀ Số NGUYÊN typedef struct TNODE { int Key; struct TNODE *pLeft, *pRight; } *TREE;. 7.

(8) CÁC LƯU Ý KHI CÀI ĐặT Bước 1: Khai báo kiễu dữ liệu biểu diễn cây Bước 2: Xây dựng hàm đưa dữ liệu (nhập) vào cây Bước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, … Các lưu ý khác: 1. Trước khi tạo node mới phải xin cấp phát vùng nhớ. 2. Trước khi tạo cây mới phải khởi tạo cây rỗng. 3. Trước khi kết thúc chương trình phải huỷ cây (giải phóng vùng nhớ). 8.

(9) CấU TRÚC CHƯƠNG TRÌNH Khai báo cấu trúc cây Khởi tạo cây rỗng Xây dựng cây Các thao tác Hủy cây 9.

(10) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 10.

(11) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 11.

(12) XÂY DựNG CÂY 7. 36 36 76436 15 40 3115 40 31764. 3. 1. 6 . . 4. 15. 40. Nếu node cần thêm < node đang xét thì thêm về bên trái. Ngược lại thì thêm về bên phải. 12.

(13) XÂY DựNG CÂY (TT) int ThemNut (TREE & t, int x) { if(t!=NULL) { if(x==t->Key) return 0; else { if(x<t->Key) ThemNut(t->pLeft, x); else ThemNut(t->pRight, x); } } else { t=new TNODE; if(t==NULL) return -1; t->Key=x; t->pLeft=t->pRight=NULL; return 1; }. 13.

(14) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 14.

(15) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 15.

(16) DUYệT CÂY Thứ tự trước Thứ tự giữa Thứ tự sau. (NLR) (LNR) (LRN) 16.

(17) NLR. 77 33. 36 36. 11. 66 44. 7 7 7 7. 3 3 3. L7 L3 R3 1 6 L6 1 6 4. 15 15. 40 40 23 23 R7. 36 L36 36 15 R15 40 36 15 23 40. R36 17.

(18) NLR Tại node t đang xét, nếu khác rỗng thì . In giá trị của t . Duyệt cây con bên trái của t theo thứ tự NLR . Duyệt cây con bên phải của t theo thứ tự NLR. void NLR (TREE t) { if(t!=NULL) { cout<<t->Key<<“\t”; NLR(t->pLeft); NLR(t->pRight); } } 18.

(19) BÀI TẬP Bài 1  Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau: 27 19 10 21 35 25 41 12 46 7  Hãy duyệt cây trên theo thứ tự trước Bài 2  Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau: H B C A E D Z M P T  Hãy duyệt cây trên theo thứ tự trước Bài 3  Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau: Huế Đà Nẵng Hà Nội Vĩnh Long Cần Thơ Sóc Trăng Nha TrangĐồng Nai Vũng Tàu An Giang Tiền Giang 19 Bình Dương Hải Dương.

(20) LNR. 77 33. 36 36. 11. 66 44. L7 1 1. L3 3 R3 3 L6 6 3 4 6. 7. 15 15. 40 40 23 23. R7 7 L36 36 R36 7 15 R15 36 40 7 15 23 36 2040.

(21) LNR Tại node t đang xét, nếu khác rỗng thì . Duyệt cây con bên trái của t theo thứ tự LNR . In giá trị của t . Duyệt cây con bên phải của t theo thứ tự LNR. void LNR (TREE t) { if(t!=NULL) { LNR(t->pLeft); cout<<t->Key<<“ “; LNR(t->pRight); } } 21.

(22) LRN. 77 33. 36 36. 11. 66 44. 1 1. L7 R7 L3 R3 3 L6 6 3 4 6 3. 15 15. 40 40 23 23. 7 L36 R36 36 R15 15 40 36 23 15 40 36. 7 7 7. 22.

(23) LRN Tại node t đang khác rỗng thì . Duyệt cây con của t theo thứ . Duyệt cây con của t theo thứ . In giá trị của t. void LRN (TREE t) { xét, nếu if(t!=NULL) { bên trái LRN(t->pLeft); tự LRN LRN(t->pRight); bên phải cout<<t->Key<<“ “; tự LRN } } 23.

(24) BÀI TẬP. Bài 4  Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau: 27 19 10 21 3 15 41 50 30 27  Hãy duyệt cây trên theo thứ tự giữa Bài 5  Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau: H B C A E D T M X O 24  Hãy duyệt cây trên theo thứ tự sau.

(25) VấN Đề CầN QUAN TÂM Xây dựng cây từ kết quả duyệt theo thứ tự trước (NLR). Chọn giá trị đầu tiên làm node gốc.  Lần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc xây dựng cây. . Xây dựng cây từ kết quả duyệt theo thứ tự sau (LRN). Chọn giá trị cuối cùng làm node gốc.  Lần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc xây 25 dựng cây. .

(26) VấN Đề CầN QUAN TÂM (TT) Xây dựng cây từ kết quả duyệt theo thứ tự giữa (LNR)  Gọi r: Số lượng giá trị cho trước.  Gọi m = r div 2: Giá trị ở giữa.  Chọn giá trị thứ m làm node gốc.  Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về trái vào cây theo nguyên tắc xây dựng cây.  Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 đến cuối vào cây theo nguyên tắc xây dựng cây. 26.

(27) BÀI TẬP Bài 6  Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự LeftRight-Node thì được dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8.  Hãy duyệt cây T trên theo thứ tự NodeLeft-Right.  Cây T có chiều cao là bao nhiêu? Tìm các đường đi từ gốc có độ dài là 4 trên 27 cây.

(28) BÀI TẬP Bài 7  Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Node-Left-Right thì được dãy sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19.  Hãy duyệt cây T trên theo thứ tự LeftRight-Node.  Liệt kê các nút lá của cây. Liệt kê các 28 nút nhánh của cây..

(29) CÀI ĐẶT void Nhap(TREE &t) { int x; do{ cout<<“Nhap gia tri: “; cin>>x; int kq=ThemNut(t, x); if(kq==0||kq==-1) break; }while (true); }. 29.

(30) CÀI ĐẶT void main() { TREE t; t=NULL; Nhap(t); cout<<“Duyet cay theo thu tu giua: “; LNR(t); Huy(t); }. 30.

(31) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 31.

(32) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 32.

(33) CHO BIếT CÁC THÔNG TIN CủA CÂY 1. 2. 3. 4. 5. 6. 7. 8. 9.. Số node lá (node bậc 0) Số node có 1 cây con (node bậc 1) Số node chỉ có 1 cây con phải Số node có 1 cây con trái Số node 2 cây con (node bậc 2) Độ cao của cây Số node của cây Các node trên từng mức của cây Độ dài đường đi từ gốc đến node x. 33.

(34) Số NODE LÁ Nếu node t khác rỗng thì . Nếu node t có bậc 0 thì Trả về 1 . Ngược lại Trả về Số node lá cây trái t + Số node lá cây phải t Nếu node t rỗng thì Trả về 0 34.

(35) Số NODE LÁ (TT) int DemNutLa (TREE t) { if(t) { if(t->pLeft==NULL && t->pRight==NULL) return 1; else return DemNutLa(t->pLeft)+DemNutLa(t->pRight); } else return 0; } 35.

(36) Số NODE CÓ 1 CÂY CON Nếu node t khác rỗng thì d=Số node bậc 1 của cây trái t + Số node bậc 1 của cây phải t Nếu node t có bậc 1 thì trả về d+1 Ngược lại trả về d Nếu node t rỗng thì Trả về 0. 36.

(37) Số NODE CÓ 1 CÂY CON int DemNut1Con(TREE t) { if(t) { int d=DemNut1Con(t->pLeft)+DemNut1Con(t->pRight); if((t->pLeft!=NULL&&t->pRight==NULL) ||(t->pLeft==NULL&&t->pRight!=NULL)) return d+1; else return d; } else return 0; } 37.

(38) Số NODE CHỉ CÓ 1 CÂY CON PHảI. Nếu node t khác rỗng thì d = Số node chỉ có 1 cây con phải của cây con trái t + Số node chỉ có 1 cây con phải của cây con phải t Nếu node t chỉ có 1 cây con phải thì trả về d+1 Ngược lại trả về d Nếu node t rỗng thì Trả về 0 38.

(39) Số NODE CÓ 1 CÂY CON PHảI int DemNut1ConPhai(TREE t) { if(t) { int d=DemNut1ConPhai(t->pLeft) +DemNut1ConPhai(t->pRight); if(t->pLeft==NULL && t->pRight!=NULL) return d+1; else return d; } else return 0; } 39.

(40) Số NODE CHỉ CÓ 1 CÂY CON TRÁI. 40.

(41) Số NODE CÓ 2 CÂY CON. 41.

(42) Độ CAO CủA CÂY int DoCaoCay(TREE t) { if(t) { int t1=DoCaoCay(t->pLeft); int t2=DoCaoCay(t->pRight); return Max(t1, t2)+1; } else return 0; }. 42.

(43) Số NODE CủA CÂY. 43.

(44) CÁC NODE TRÊN TừNG MứC 77 33. 36 36. 11. 66 44. 15 15. Mức 2: 1 6 15 40 40 40. 23 23 44.

(45) CÁC NODE TRÊN TừNG MứC void InMuck(TREE t, int k, int m=0) { if(t) { if(m==k) { printf("%d\t", t->Key); return; } else { m++; InMuck(t->pLeft, k,m); InMuck(t->pRight, k, m); } } }. 45.

(46) IN CÁC NODE CủA TấT Cả MứC. 46.

(47) Độ DÀI ĐƯờNG ĐI Từ GốC ĐếN NODE X. 47.

(48) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 48.

(49) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 49.

(50) TÌM KIếM 1. 2. 3. 4. 5.. Tìm Tìm Tìm Tìm Tìm. x min min của cây con bên phải max max của cây con bên trái. 50.

(51) VÍ Dụ TÌM X = 23. 77 33. 36 36. 11. 66 44. 15 15. 40 40 23 23 51.

(52) TÌM X TNODE * TimKiem(TREE t,int x) { if(t!=NULL) { if(t->Key==x) return t; if(x<t->Key) return TimKiem(t->pLeft,x); else return TimKiem (t->pRight,x); } return NULL; }. 52.

(53) TÌM MIN TNODE* Min(TREE t) { while(t->pLeft!=NULL) { t=t->pLeft; } return t; } 53.

(54) MIN CÂY CON BÊN PHảI. 54.

(55) TÌM MAX. 55.

(56) TÌM MAX CÂY CON BÊN TRÁI. 56.

(57) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 57.

(58) CÁC THAO TÁC. 1. 2. 3. 4. 5.. Xây dựng cây Duyệt cây Cho biết các thông tin của cây Tìm kiếm Xoá node trên cây. 58.

(59) XÓA NODE TRÊN CÂY 77 33. 36 36. 1. 2.. 11. 66 44. 15 15. 40 40. 3.. Node lá Node có 1 cây con Node có 2 cây con. 23 23 59.

(60) XÓA NODE LÁ 77 33. Xóa 1 Xóa 23. 36 36. 11. 66 44. 15 15. 40 40 23 23 60.

(61) XÓA NODE 1 CÂY CON 77 33. Xóa 6 Xóa 15. 36 36. 11. 6446 44. 23 15 15 23. 40 40 23 23 61.

(62) XÓA NODE 2 CÂY CON Tìm node thế mạng Cách 1: Tìm node trái 77 nhất của cây con phải 36 23 36 23 Cách 2: Tìm node phải nhất của cây con 66 15 40 15 40 trái. 33 11 44. 23 23 16 16. Xóa 36 (Cách 2) 62.

(63) TÌM NODE THế MạNG void TimTheMang (TREE &pHuy,TREE & q) { if(q->pLeft) TimTheMang(pHuy, q->pLeft); else { pHuy->Key=q->Key; pHuy=q; q=q->pRight; } }. 63.

(64) XÓA MộT NODE CÓ GIÁ TRị X void HuyNut (TREE & t, int x) { if(t!=NULL) { if(x<t->Key) HuyNut(t->pLeft,x); else{ if(x>t->Key) HuyNut(t->pRight,x); else{ TNODE * pHuy=t; if(t->pLeft==NULL) t=t->pRight; else if(t->pRight==NULL) t=t->pLeft; else TimTheMang(pHuy,t->pRight); delete pHuy; } } }. }. 64.

(65) HUỷ TOÀN Bộ CÂY Nếu node khác rỗng Hủy. cây bên trái t Hủy cây bên phải t Hủy node t 65.

(66) Cho dãy số theo thứ tự nhập từ trái sang phải như sau: 20 15 35 30 11 13 17 36 47 16 38 28 14 Hãy vẽ cây nhị phân tìm kiếm cho dãy số trên. Hãy cho biết kết quả duyệt cây trên theo thứ tự trước, giữa và sau. Cho biết độ cao của cây, các nút lá, các nút có bậc 2. Vẽ lại cây sau khi thêm nút: 25 và 91 Trình bày từng bước và vẽ lại cây sau 66 khi lần lượt xoá các nút: 11 và 35.

(67)

cay nhi phan

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về