Bài giảng Cây nhị phân tìm kiếm

CÂY NHỊ PHÂN TÌM KIẾM TMT * NộI DUNG 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 * 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. * 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. * Đặ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 7 3 36 1 6 15 40 23 4 * Nút ĐịNH NGHĨA KIểU Dữ LIệU typedef struct TNODE { Key; struct TNODE *pLeft, *pRight; } *TREE; Giá trị Trỏ trái Trỏ phải TNODE Key pLeft pRight * 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; * 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ớ). * 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 * 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 * 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 * 40 15 4 6 1 36 3 XÂY DựNG CÂY 7 Nếu node cần thêm Key) return 0; else { if(xKey) 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; } } * 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 * 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 * DUYệT CÂY Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) * 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 7 3 36 1 6 15 40 23 4 * 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) { coutKeypLeft); NLR(t->pRight); } } * 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 * 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 7 3 36 1 6 15 40 23 4 * 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); coutKeypRight); } } * 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 7 3 36 1 6 15 40 23 4 * 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); coutKey>x; int kq=ThemNut(t, x); if(kq==0||kq==-1) break; }while (true); } * CÀI ĐẶT void main() { TREE t; t=NULL; Nhap(t); coutpLeft==NULL && t->pRight==NULL) return 1; else return DemNutLa(t->pLeft)+DemNutLa(t->pRight); } else return 0; } * 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 * 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; } * 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 * 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; } * Số NODE CHỉ CÓ 1 CÂY CON TRÁI * Số NODE CÓ 2 CÂY CON * Độ 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; } * Số NODE CủA CÂY * CÁC NODE TRÊN TừNG MứC Mức 2: 1 6 15 40 7 3 36 1 6 15 40 23 4 * 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); } } } * IN CÁC NODE CủA TấT Cả MứC * Độ DÀI ĐƯờNG ĐI Từ GốC ĐếN NODE X * 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 * 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 * TÌM KIếM Tìm x Tìm min Tìm min của cây con bên phải Tìm max Tìm max của cây con bên trái * VÍ Dụ TÌM X = 23 7 3 36 1 6 15 40 23 4 * TÌM X TNODE * TimKiem(TREE t,int x) { if(t!=NULL) { if(t->Key==x) return t; if(xKey) return TimKiem(t->pLeft,x); else return TimKiem (t->pRight,x); } return NULL; } * TÌM MIN TNODE* Min(TREE t) { while(t->pLeft!=NULL) { t=t->pLeft; } return t; } * MIN CÂY CON BÊN PHảI * TÌM MAX * TÌM MAX CÂY CON BÊN TRÁI * 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 * 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 * XÓA NODE TRÊN CÂY Node lá Node có 1 cây con Node có 2 cây con 7 3 36 1 6 15 40 23 4 * XÓA NODE LÁ Xóa 1 Xóa 23 7 3 36 1 6 15 40 23 4 * XÓA NODE 1 CÂY CON Xóa 6 Xóa 15 7 3 36 1 6 15 40 23 4 4 23 * 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) 7 3 36 1 6 15 40 23 4 16 23 * 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; } } * XÓA MộT NODE CÓ GIÁ TRị X void HuyNut (TREE & t, int x) { if(t!=NULL) { if(xKey) 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; } } } } * 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 * 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 *