ݺߣ

ݺߣShare a Scribd company logo

Cây Nhị Phân

•
•
Nghĩa Hoàng
Nghĩa Hoàng
1 of 66
CÂY NHỊ PHÂN TÌM KIẾM TMT1
N I DUNGộ 1. Các khái ni mệ 2. Đ c đi mặ ể 3. Hình d ngạ 4. Các khái ni mệ 5. Đ nh nghĩa ki u d li uị ể ữ ệ 6. Các l u ý khi cài đ tư ặ 7. Các thao tác 2
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 22 110 0 0 0 3
Mức 3 Mức 2 Mức 1 Mức 0 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.ở ứ ấ ấ 4
Đ 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ị ỏ ấ ằ ở 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ả ấ ủ 7777 33 3636 11 66 1515 4040 232344 5
Nút Đ NH NGHĨA KI U D LI Uị ể ữ ệ typedef struct TNODE { <Data> Key; struct TNODE *pLeft, *pRight; Giá trị Trỏ trái Trỏ phải TNODE Key pLeft pRight 6
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
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
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
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 10
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 11
40401515446611363633 XÂY D NG CÂYự 77 3636 33 11 66 44 1515 4040 7777  Nếu node cầnNếu node cần thêmthêm << node đangnode đang xét thì thêm vềxét thì thêm về bên tráibên trái..  Ngược lại thì thêmNgược lại thì thêm vềvề bên phảibên phải.. 12
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
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 14
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 15
DUY T CÂYệ Th t tr cứ ự ướ (NLR) Th t gi aứ ự ữ (LNR) Th t sauứ ự (LRN) 16
NLR 7 L7 R7 7 3 L3 R3 36 L36 R36 7 3 1 6 L6 36 15 R15 40 7 3 1 6 4 36 15 23 40 7777 33 3636 11 66 1515 4040 232344 17
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)void NLR (TREE t) {{ if(t!=NULL)if(t!=NULL) {{ cout<<t->Key<<“t”;cout<<t->Key<<“t”; NLR(t->pLeft);NLR(t->pLeft); NLR(t->pRight);NLR(t->pRight); }} }} 18
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ề Bình D ngươ H i D ngả ươ 19
LNR L7 7 R7 L3 3 R3 7 L36 36 R36 1 3 L6 6 7 15 R15 36 40 1 3 4 6 7 15 23 36 40 7777 33 3636 11 66 1515 4040 232344 20
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
LRN L7 R7 7 L3 R3 3 L36 R36 36 7 1 L6 6 3 R15 15 40 36 7 1 4 6 3 23 15 40 36 7 7777 33 3636 11 66 1515 4040 232344 22
LRN 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 LRNủ ứ ự . Duy t cây con bên ph iệ ả c a t theo th t LRNủ ứ ự . In giá tr c a tị ủ void LRN (TREE t) { if(t!=NULL) { LRN(t->pLeft); LRN(t->pRight); cout<<t->Key<<“ “; } } 23
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 Hãy duy t cây trên theo th t sauệ ứ ự 24
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ắ d ng cây.ự 25
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
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 Left-ằ ệ ứ ự Right-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 Node-ệ ứ ự Left-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 câyườ ừ ố ộ 27
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 Left-ệ ứ ự Right-Node. Li t kê các nút lá c a cây. Li t kê cácệ ủ ệ nút nhánh c a cây.ủ 28
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
CÀI Đ TẶ void main() { TREE t; t=NULL; Nhap(t); cout<<“Duyet cay theo thu tu giua: “; LNR(t); Huy(t); } 30
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 31
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 32
CHO BI T CÁC THÔNG TIN C A CÂYế ủ 1. S node lá (node b c 0)ố ậ 2. S node có 1 cây con (node b c 1)ố ậ 3. S node ch có 1 cây con ph iố ỉ ả 4. S node có 1 cây con tráiố 5. S node 2 cây con (node b c 2)ố ậ 6. Đ cao c a câyộ ủ 7. S node c a câyố ủ 8. Các node trên t ng m c c a câyừ ứ ủ 9. Đ dài đ ng đi t g c đ n node xộ ườ ừ ố ế 33
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
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
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
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
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
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
S NODE CH CÓ 1 CÂY CON TRÁIố ỉ 40
S NODE CÓ 2 CÂY CONố 41
Đ 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
S NODE C A CÂYố ủ 43
CÁC NODE TRÊN T NG M Cừ ứ M c 2: 1 6 15 40ứ 7777 33 3636 11 66 1515 4040 232344 44
CÁC NODE TRÊN T NG M Cừ ứ void InMuck(TREE t, int k, int m=0) { if(t) { if(m==k) { printf("%dt", t->Key); return; } else { m++; InMuck(t->pLeft, k,m); InMuck(t->pRight, k, m); } } } 45
IN CÁC NODE C A T T C M Củ ấ ả ứ 46
Đ DÀI Đ NG ĐI T G C Đ Nộ Ườ ừ ố ế NODE X 47
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 48
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 49
TÌM KI Mế 1. Tìm x 2. Tìm min 3. Tìm min c a cây con bên ph iủ ả 4. Tìm max 5. Tìm max c a cây con bên tráiủ 50
VÍ D TÌM X = 23ụ 7777 33 3636 11 66 1515 4040 232344 51
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
TÌM MIN TNODE* Min(TREE t) { while(t->pLeft!=NULL) { t=t->pLeft; } return t; } 53
MIN CÂY CON BÊN PH Iả 54
TÌM MAX 55
TÌM MAX CÂY CON BÊN TRÁI 56
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 57
CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 58
XÓA NODE TRÊN CÂY 1. Node lá 2. Node có 1 cây con 3. Node có 2 cây con 7777 33 3636 11 66 1515 4040 232344 59
XÓA NODE LÁ Xóa 1 Xóa 23 7777 33 3636 11 66 1515 4040 232344 60
XÓA NODE 1 CÂY CON Xóa 6 Xóa 15 7777 33 3636 11 66 1515 4040 232344 44 2323 61
XÓA NODE 2 CÂY CON Tìm node th m ngế ạ Cách 1: Tìm node trái nh t c a cây con ph iấ ủ ả Cách 2: Tìm node ph iả nh t c a cây con tráiấ ủ Xóa 36 (Cách 2) 7777 33 3636 11 66 1515 4040 232344 1616 2323 62
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
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
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
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ừ ướ ẽ ạ khi l n l t xoá các nút:ầ ượ 11 và 35 66

More Related Content

Cây Nhị Phân

  • 1. CÂY NHỊ PHÂN TÌM KIẾM TMT1
  • 2. N I DUNGộ 1. Các khái ni mệ 2. Đ c đi mặ ể 3. Hình d ngạ 4. Các khái ni mệ 5. Đ nh nghĩa ki u d li uị ể ữ ệ 6. Các l u ý khi cài đ tư ặ 7. 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 22 110 0 0 0 3
  • 4. Mức 3 Mức 2 Mức 1 Mức 0 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.ở ứ ấ ấ 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ị ỏ ấ ằ ở 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ả ấ ủ 7777 33 3636 11 66 1515 4040 232344 5
  • 6. Nút Đ NH NGHĨA KI U D LI Uị ể ữ ệ typedef struct TNODE { <Data> Key; struct TNODE *pLeft, *pRight; Giá trị Trỏ trái Trỏ phải TNODE Key pLeft 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. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 10
  • 11. CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 11
  • 12. 40401515446611363633 XÂY D NG CÂYự 77 3636 33 11 66 44 1515 4040 7777  Nếu node cầnNếu node cần thêmthêm << node đangnode đang xét thì thêm vềxét thì thêm về bên tráibên trái..  Ngược lại thì thêmNgược lại thì thêm vềvề bên phảibê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. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 14
  • 15. CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 15
  • 16. DUY T CÂYệ Th t tr cứ ự ướ (NLR) Th t gi aứ ự ữ (LNR) Th t sauứ ự (LRN) 16
  • 17. NLR 7 L7 R7 7 3 L3 R3 36 L36 R36 7 3 1 6 L6 36 15 R15 40 7 3 1 6 4 36 15 23 40 7777 33 3636 11 66 1515 4040 232344 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)void NLR (TREE t) {{ if(t!=NULL)if(t!=NULL) {{ cout<<t->Key<<“t”;cout<<t->Key<<“t”; NLR(t->pLeft);NLR(t->pLeft); NLR(t->pRight);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ề Bình D ngươ H i D ngả ươ 19
  • 20. LNR L7 7 R7 L3 3 R3 7 L36 36 R36 1 3 L6 6 7 15 R15 36 40 1 3 4 6 7 15 23 36 40 7777 33 3636 11 66 1515 4040 232344 20
  • 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 L7 R7 7 L3 R3 3 L36 R36 36 7 1 L6 6 3 R15 15 40 36 7 1 4 6 3 23 15 40 36 7 7777 33 3636 11 66 1515 4040 232344 22
  • 23. LRN 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 LRNủ ứ ự . Duy t cây con bên ph iệ ả c a t theo th t LRNủ ứ ự . In giá tr c a tị ủ void LRN (TREE t) { if(t!=NULL) { LRN(t->pLeft); LRN(t->pRight); cout<<t->Key<<“ “; } } 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 Hãy duy t cây trên theo th t sauệ ứ ự 24
  • 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ắ d ng cây.ự 25
  • 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 Left-ằ ệ ứ ự Right-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 Node-ệ ứ ự Left-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 câyườ ừ ố ộ 27
  • 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 Left-ệ ứ ự Right-Node. Li t kê các nút lá c a cây. Li t kê cácệ ủ ệ nút nhánh c a cây.ủ 28
  • 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. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 31
  • 32. CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 32
  • 33. CHO BI T CÁC THÔNG TIN C A CÂYế ủ 1. S node lá (node b c 0)ố ậ 2. S node có 1 cây con (node b c 1)ố ậ 3. S node ch có 1 cây con ph iố ỉ ả 4. S node có 1 cây con tráiố 5. S node 2 cây con (node b c 2)ố ậ 6. Đ cao c a câyộ ủ 7. S node c a câyố ủ 8. Các node trên t ng m c c a câyừ ứ ủ 9. Đ 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ừ ứ M c 2: 1 6 15 40ứ 7777 33 3636 11 66 1515 4040 232344 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("%dt", 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. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 48
  • 49. CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 49
  • 50. TÌM KI Mế 1. Tìm x 2. Tìm min 3. Tìm min c a cây con bên ph iủ ả 4. Tìm max 5. Tìm max c a cây con bên tráiủ 50
  • 51. VÍ D TÌM X = 23ụ 7777 33 3636 11 66 1515 4040 232344 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
  • 56. TÌM MAX CÂY CON BÊN TRÁI 56
  • 57. CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 57
  • 58. CÁC THAO TÁC 1. Xây d ng câyự 2. Duy t câyệ 3. Cho bi t các thông tin c a câyế ủ 4. Tìm ki mế 5. Xoá node trên cây 58
  • 59. XÓA NODE TRÊN CÂY 1. Node lá 2. Node có 1 cây con 3. Node có 2 cây con 7777 33 3636 11 66 1515 4040 232344 59
  • 60. XÓA NODE LÁ Xóa 1 Xóa 23 7777 33 3636 11 66 1515 4040 232344 60
  • 61. XÓA NODE 1 CÂY CON Xóa 6 Xóa 15 7777 33 3636 11 66 1515 4040 232344 44 2323 61
  • 62. XÓA NODE 2 CÂY CON Tìm node th m ngế ạ Cách 1: Tìm node trái nh t c a cây con ph iấ ủ ả Cách 2: Tìm node ph iả nh t c a cây con tráiấ ủ Xóa 36 (Cách 2) 7777 33 3636 11 66 1515 4040 232344 1616 2323 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ừ ướ ẽ ạ khi l n l t xoá các nút:ầ ượ 11 và 35 66