›
›

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

pdf 41 trang vanle 4030
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Cây nhị phân tìm kiếm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_cay_nhi_phan_tim_kiem.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Cây nhị phân tìm kiếm

  1. INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY Data structures and algorithms Tree structure
  2. Nội dung 1. Khái niệm 2. Đặc điểm 3. Hình dạng 4. Định nghĩa kiểu dữ liệu 5. Các lưu ý khi cài đặt 6. Các thao tác 2
  3. Khái niệm  Bậc của một nút: là số cây con của nút đó 2  Nút gốc: là nút không có nút cha 2 2  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 1 1 0 0 và không phải là gốc 0 0 3
  4. Khái niệm  Độ dài đường đi từ Mức 0 gốc đến nút x: là số nhánh cần đi qua kể Mức 1 từ gốc đến x  Độ cao của cây: Độ Mức 2 dài đường đi từ gốc đến nút lá ở mức thấp Mức 3 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ỳ 7 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 3 36 phải Nút có giá trị nhỏ nhất nằm ở 1 6 15 40 trái nhất của cây Nút có giá trị lớn nhất nằm ở 4 23 phải nhất của cây 5
  6. Định nghĩa kiểu dữ liệu Giá trị Key Nút TNODE Trỏ trái Trỏ phải pLeft pRight typedef struct TNODE { Key; struct TNODE *pLeft, *pRight; } *TREE; 6
  7. Ví dụ khai báo 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ỷ, 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. Tạo 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. Tạo cây 7 36 3 1 6 4 15 40 40153613746  Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên trái  Ngược lại thì thêm về bên phải 11
  12. Hàm tạo cây int ThemNut (TREE & t, int x) { if(t!=NULL) { if(x==t->Key) return 0; // x đã có trong cây else { if(x Key) return ThemNut(t->pLeft, x); else return ThemNut(t->pRight, x); } } else { t=new TNODE; if(t==NULL) return -1; //không đủ bộ nhớ t->Key=x; t->pLeft=t->pRight=NULL; return 1; //thêm x thành công } } 12
  13. Duyệt cây Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) 13
  14. 7 Bước Kết quả duyệt theo thứ tự NLR 1 7 L7 R7 3 36 2 3 L3 R3 R7 1 6 15 40 3 1 R3 R7 4 6 L6 R7 4 23 5 4 R7 6 36 L36 R36 7 15 R15 R36 8 23 R36 9 40 KQ 7 3 1 6 4 36 15 23 40 14
  15. Hàm duyệt NLR Tại node t đang xét, nếu khác void NLR (TREE t) rỗng thì { if(t!=NULL)  In giá trị của t {  Duyệt cây con bên trái của t cout Key pLeft);  Duyệt cây con bên phải của NLR(t->pRight); t theo thứ tự NLR } } 15
  16. Bài tập Vẽ 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: a. 27; 19; 10; 21; 35; 25; 41; 12; 46; 7 b. H; B; C; A; E; D; Z; M; P; T c. 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 16
  17. Bước Kết quả duyệt theo thứ tự LNR 7 1 L7 7 R7 2 L3 3 R3 7 R7 3 36 3 1 3 R3 7 R7 4 3 R3 7 R7 1 6 15 40 5 L6 6 7 R7 6 4 6 7 R7 4 23 7 6 7 R7 8 7 R7 9 L36 36 R36 10 15 R15 36 R36 11 23 36 R36 12 36 R36 13 40 KQ 17 1 3 4 6 7 15 23 36 40
  18. Hàm duyệt LNR Tại node t đang xét, nếu khác void LNR (TREE t) rỗng thì { if(t!=NULL)  Duyệt cây con bên trái của t theo thứ tự LNR { LNR(t->pLeft);  In giá trị của t cout Key pRight); } } 18
  19. Bước Kết quả duyệt theo thứ tự LRN 7 1 L7 R7 7 2 L3 R3 3 R7 7 3 36 3 1 R3 3 R7 7 4 L6 6 3 R7 7 1 6 15 40 5 4 6 3 R7 7 6 6 3 R7 7 4 23 7 3 R7 7 8 L36 R36 36 7 9 R15 15 R36 36 7 10 23 15 R36 36 7 11 15 R36 36 7 12 40 36 7 13 36 7 14 7 KQ 19 1 4 6 3 23 15 40 36 7
  20. Hàm duyệt LRN void LRN (TREE t) Tại node t đang xét, nếu khác rỗng thì { if(t!=NULL)  Duyệt cây con bên trái của { t theo thứ tự LRN LRN(t->pLeft);  Duyệt cây con bên phải LRN(t->pRight); của t theo thứ tự LRN cout Key<<“ “;  In giá trị của t } } 20
  21. Bài tập  Bài 4 Vẽ cây nhị phân tìm kiếm theo thứ tự nhập: 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 Vẽ cây nhị phân tìm kiếm theo thứ tự nhập: H, B, C, A, E, D, T, M, X, O Hãy duyệt cây trên theo thứ tự sau 21
  22. Vấn đề cần quan tâm Tạo cây từ kết quả duyệt 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 tạo cây Tạo cây từ kết quả duyệt 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 tạo cây 22
  23. Vấn đề cần quan tâm Tạo cây từ kết quả duyệt 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 tạo 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 tạo cây 23
  24. Bài tập Bài 6 Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự NLR 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ự LRN  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 24
  25. Bài tập Bài 7 Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự LRN 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ự NLR  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 25
  26. Hàm nhập dữ liệu vào cây void Nhap(TREE &t) { int x; do{ cout >x; int kq=ThemNut(t, x); if(kq==0||kq==-1) break; }while (true); } 26
  27. Hàm main gọi thao tác duyệt LNR void main() { TREE t; t=NULL; Nhap(t); cout<<“Duyet cay theo thu tu giua: “; LNR(t); Huy(t); } 27
  28. Các thao tác 1. Tạo 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 28
  29. Các thao tác 1. Tạo 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 29
  30. 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 chỉ có 1 cây con trái 5. Số node có 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 30
  31. Các thao tác 1. Tạo 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. Tạo 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. 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 33
  34. Ví dụ tìm x = 23 7 3 36 1 6 15 40 4 23 34
  35. Các thao tác 1. Tạo 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 35
  36. Các thao tác 1. Tạo 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 36
  37. Xóa node trên cây 7 3 36 1. Node lá 2. Node có 1 cây con 1 6 15 40 3. Node có 2 cây con 4 23 37
  38. Xóa node lá 7 3 36 Xóa 1 Xóa 23 1 6 15 40 4 23 38
  39. Xóa node 1 cây con 7 3 36 Xóa 6 Xóa 15 1 64 1523 40 4 23 39
  40. Xóa node 2 cây con Tìm node thế mạng  Cách 1: Tìm node trái nhất 7 của cây con phải (min của T->Right) 3 2336  Cách 2: Tìm node phải nhất của cây con trái 1 6 15 40 (max của T->Left) 4 23 Xóa 36 (Cách 2) 16 40
  41. Cho 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, 14  Vẽ cây nhị phân tìm kiếm cho dãy số trên  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 41