Cấu trúc dữ liệu và giải thuật - Chương 4: Cây nhị phân tìm kiếm

Chương 4. Cây nhị phân tìm kiếmTrần Minh TháiEmail: minhthai@itc.edu.vnWebsite: www.minhthai.edu.vn1Nội dungKhái niệmĐặc điểmĐịnh nghĩa kiểu dữ liệuCác lưu ý khi cài đặtCác thao tác2Khái niệmBậ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 chaNú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ốc3222110000Mức 4Mức 3Mức 2Mức 1Khái niệmChiều dài đường đi đến nút x: là số nhánh cần đi qua kể từ gốc đến xĐộ cao của cây: Độ sâu (mức) của nút lá thấp nhất4xĐặc điểm cây nhị phân tìm kiếmLà cây nhị phânGiá 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ây57336161540234Định nghĩa kiểu dữ liệu6typedef struct TNODE{ Key; struct TNODE *pLeft, *pRight;} *TREE; NútGiá trịTrỏ tráiTrỏ phảiTNODEKeypLeftpRightVí dụ khai báotypedef struct TNODE{ int Key; struct TNODE *pLeft, *pRight;} *TREE;7Các lưu ý khi cài đặtBước 1: Khai báo kiễu dữ liệu biểu diễn câyBước 2: Xây dựng hàm đưa dữ liệu (nhập) vào câyBước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, 8Cấu trúc chương trình9Khai báo cấu trúc câyKhởi tạo cây rỗngXây dựng câyCác thao tácHủy câyCác thao tác1. Tạo cây2. Duyệt cây3. Cho biết các thông tin của cây4. Tìm kiếm5. Xoá node trên cây 10Tạo cây114015461363736316415407Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên tráiNgược lại thì thêm về bên phảiHàm tạo cây12int ThemNut (TREE & t, int x){ if(t!=NULL) { if(x==t->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; }}Duyệt câyThứ tự trước (NLR)Thứ tự giữa (LNR)Thứ tự sau (LRN)1314BướcKết quả duyệt theo thứ tự NLR17L7R723L3R3R731R3R746L6R754R7636L36R36715R15R36823R36940KQ73164361523407336161540234Hàm duyệt NLRTại node t đang xét, nếu khác rỗng thìIn giá trị của tDuyệt cây con bên trái của t theo thứ tự NLRDuyệt cây con bên phải của t theo thứ tự NLR 15void NLR (TREE t){ if(t!=NULL) { coutKeypLeft); NLR(t->pRight); }}Bài tậpVẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang phải và duyệt cây theo thứ tự trước:27; 19; 10; 21; 35; 25; 41; 12; 46; 7H; B; C; A; E; D; Z; M; P; THuế; Đà 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ương1617BướcKết quả duyệt theo thứ tự LNR1L77R72L33R37R7313R37R743R37R75L667R76467R7767R787R79L3636R361015R1536R36112336R361236R361340KQ13467152336407336161540234Hàm duyệt LNRTạ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ự LNRIn giá trị của tDuyệt cây con bên phải của t theo thứ tự LNR 18void LNR (TREE t){ if(t!=NULL) { LNR(t->pLeft); coutKeypRight); }}19BướcKết quả duyệt theo thứ tự LRN1L7R772L3R33R7731R33R774L663R775463R77663R7773R778L36R363679R1515R36367102315R363671115R36367124036713367147KQ14632315403677336161540234Hàm duyệt LRNTạ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ự LRNDuyệt cây con bên phải của t theo thứ tự LRN In giá trị của t 20void 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);}26Hàm main gọi thao tác duyệt LNRvoid main(){ TREE t; t=NULL; Nhap(t); cout<<“Duyet cay theo thu tu giua: “; LNR(t); Huy(t);}27Tìm kiếmTìm xTìm minTìm min của cây con bên phảiTìm maxTìm max của cây con bên trái28Ví dụ tìm x = 23297336161540234Xóa node trên câyNode láNode có 1 cây conNode có 2 cây con 307336161540234Xóa node láXóa 1Xóa 23317336161540234Xóa node 1 cây conXóa 6Xóa 15327336161540234423Xóa node 2 cây conTìm node thế mạngCách 1: Tìm node trái nhất của cây con phảiCách 2: Tìm node phải nhất của cây con tráiXóa 36 (Cách 2)3373361615402341623Cho dãy số theo thứ tự nhập từ trái sang phải: 20, 15, 35, 30, 11, 13, 17, 36, 47, 16, 38, 28, 14Vẽ cây nhị phân tìm kiếm cho dãy số trênCho biết kết quả duyệt cây trên theo thứ tự trước, giữa và sauCho biết độ cao của cây, các nút lá, các nút có bậc 2Vẽ lại cây sau khi thêm nút: 25 và 91Trì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à 3534Viết hàmIn ra các node có giá trị chẵnIn ra các node có giá trị lớn hơn xĐộ cao của câySố node của câyTìm min, maxTìm node có giá trị x35Viết hàmSố 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ảiSố node có 1 cây con trái Số node 2 cây con (node bậc 2)Các node trên từng mức của câyĐộ dài đường đi từ gốc đến node x 36