›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Kiểu cấu trúc cây

pdf 48 trang Đức Chiến 04/01/2024 1150
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Kiểu cấu trúc cây", để 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_chuong_6_kieu_cau_truc_cay.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Kiểu cấu trúc cây

  1. CHƯƠNG 6 KIỂU CẤU TRÚC CÂY GV Th.S. Thiều Quang Trung Trường Cao đẳng Kinh tế Đối ngoại
  2. Nội dung 1 •Khái niệm cấu trúc cây - tree 2 •Đặc điểm cấu trúc cây 3 •Định nghĩa kiểu cấu trúc cây 4 •Các thao tác trên cấu trúc cây GV. Thiều Quang Trung 2
  3. Khái niệm cấu trúc cây • Cây là một tập hợp T các phần tử (gọi là nút của cây), gồm có: – một nút đặc biệt gọi là nút gốc, – các nút còn lại được chia thành những tập rời nhau T1, T2, ,Tn theo quan hệ phân cấp, trong đó Ti cũng là một cây. • Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này gọi là quan hệ cha –con. GV. Thiều Quang Trung 3
  4. Khái niệm cấu trúc cây • Bậc của một nút: là số 2 cây con của nút đó • Nút gốc: là nút không 2 2 có nút cha • Nút lá: là nút có bậc 0 1 1 0 bằng 0 • Nút nhánh: là nút có 0 0 bậc khác 0 và không phải là gốc GV. Thiều Quang Trung 4
  5. Khái niệm cấu trúc cây Mức 1 Mức 2 Mức 3 Mức 4 x • Chiề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ất GV. Thiều Quang Trung 5
  6. Đặc điểm cây nhị phân tìm kiếm • 7 Là cây nhị phân • Giá trị của một node bất kỳ luôn lớn hơn giá 3 36 trị của tất cả các node bên trái và nhỏ hơn giá 1 6 15 40 trị tất cả các node bên phải 4 23 ➔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 GV. Thiều Quang Trung 6
  7. Đị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; GV. Thiều Quang Trung 7
  8. Ví dụ khai báo typedef struct TNODE { int Key; struct TNODE *pLeft, *pRight; } *TREE; GV. Thiều Quang Trung 8
  9. 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ỷ, GV. Thiều Quang Trung 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 GV. Thiều Quang Trung 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 GV. Thiều Quang Trung 11
  12. Hàm tạo cây int ThemNut (TREE & t, int x) { if(t!=NULL) { if(x==t->Key) return 0; else { if(x 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; } } GV. Thiều Quang Trung 12
  13. Duyệt cây • Thứ tự trước (NLR) • Thứ tự giữa (LNR) • Thứ tự sau (LRN) GV. Thiều Quang Trung 13
  14. 7 3 36 Bước Kết quả duyệt theo thứ tự NLR 1 7 L7 R7 1 6 15 40 2 3 L3 R3 R7 4 23 3 1 R3 R7 4 6 L6 R7 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 GV. Thiều Quang Trung 14
  15. Hàm duyệt NLR • Tại node t đang xét, void NLR (TREE t) nếu khác rỗng thì: { – In giá trị của t if(t!=NULL) – Duyệt cây con bên { trái của t theo thứ tự cout Key pLeft); – Duyệt cây con bên NLR(t->pRight); phải của t theo thứ } tự NLR } GV. Thiều Quang Trung 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: • 27; 19; 10; 21; 35; 25; 41; 12; 46; 7 • H; B; C; A; E; D; Z; M; P; T • 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 GV. Thiều Quang Trung 1616
  17. 7 Bước Kết quả duyệt theo thứ tự LNR 1 L7 7 R7 3 36 2 L3 3 R3 7 R7 3 1 3 R3 7 R71 6 15 40 4 3 R3 7 R7 5 L6 6 7 R7 4 23 6 4 6 7 R7 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 1 3 4 6 7 15 23 36 40 GV. Thiều Quang Trung 17
  18. Hàm duyệt LNR void LNR (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ự LNR LNR(t->pLeft); – In giá trị của t cout Key pRight); phải của t theo thứ } tự LNR } GV. Thiều Quang Trung 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 R71 7 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 1 4 6 3GV. Thiều23 Quang Trung15 40 36 7 19
  20. Hàm duyệt LRN • Tại node t đang xét, void LRN (TREE 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 LRN(t->pRight); phải của t theo thứ tự cout Key<<“ “; LRN } – In giá trị của t } GV. Thiều Quang Trung 2020
  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, 7 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 GV. Thiều Quang Trung 2121
  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 GV. Thiều Quang Trung 2222
  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 GV. Thiều Quang Trung 2323
  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 GV. Thiều Quang Trung 2424
  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 GV. Thiều Quang Trung 2525
  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); } GV. Thiều Quang Trung 2626
  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); } GV. Thiều Quang Trung 2727
  28. 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 GV. Thiều Quang Trung 2828
  29. Ví dụ tìm x = 23 7 3 36 1 6 15 40 4 23 GV. Thiều Quang Trung 2929
  30. Xóa node trên cây 7 1. Node lá 2. Node có 1 cây con 3 36 3. Node có 2 cây con 1 6 15 40 4 23 GV. Thiều Quang Trung 3030
  31. Xóa node lá 7 3 36 Xóa 1 1 6 15 40 Xóa 23 4 23 GV. Thiều Quang Trung 3131
  32. Xóa node 1 cây con 7 3 36 Xóa 6 Xóa 15 1 64 1523 40 4 23 GV. Thiều Quang Trung 3232
  33. Xóa node 2 cây con 7 Tìm node thế mạng • Cách 1: Tìm node trái 3 2336 nhất của cây con phải • Cách 2: Tìm node phải 1 6 15 40 nhất của cây con trái 4 23 Xóa 36 (Cách 2) 16 GV. Thiều Quang Trung 3333
  34. Bài tập • 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 GV. Thiều Quang Trung 3434
  35. Viết hàm 1. In ra các node có giá trị chẵn 2. In ra các node có giá trị lớn hơn x 3. Độ cao của cây 4. Số node của cây 5. Tìm min, max 6. Tìm node có giá trị x GV. Thiều Quang Trung 3535
  36. Viết hàm 7. Số node lá (node bậc 0) 8. Số node có 1 cây con (node bậc 1) 9. Số node chỉ có 1 cây con phải 10. Số node có 1 cây con trái 11. Số node 2 cây con (node bậc 2) 12. Các node trên từng mức của cây 13. Độ dài đường đi từ gốc đến node x GV. Thiều Quang Trung 3636
  37. GV: Thiều Quang Trung 37
  38. Viết các hàm C/C++ thao tác cây • Thêm 1 nút • Tìm nhánh thay thế • Hủy 1 nút • Tìm nút x • Đếm số nút lá • Đếm nút có 1 nhánh • Đếm nút có 2 nhánh • Tìm chiều cao của cây • Duyệt cây theo thứ tự giảm dần RNL • In cấu trúc cây GV. Thiều Quang Trung 38
  39. Thêm 1 nút x vào cây int themnode(tree &t,int x) { if(t!=NULL) { if(t->key==x) return 0; if(t->key>x) return themnode(t->pleft,x); else return themnode(t->pright,x); } t=new node; if(t==NULL) return -1; t->key=x; t->pleft=t->pright=NULL; return 1; } GV. Thiều Quang Trung 39
  40. Tìm nhánh thay thế void thaythe(tree &p,tree &t) { if(t->pleft) thaythe(p,t->pleft); else { p->key=t->key; p=t; t=t->pright; } } GV. Thiều Quang Trung 40
  41. Xóa 1 nút x khỏi cây void huynode(tree &t,int x) { if(t) { if(t->key pright,x); else { if(t->key>x) huynode(t->pleft,x); else { node *p; p=t; if(t->pleft==NULL) t=t->pright; else { if(t->pright==NULL) t=t->pleft; else thaythe(p,t->pright);} delete p; } } } else cout << "\nKhong tim thay so can tim!"; } GV. Thiều Quang Trung 41
  42. Tìm nút x bool find(tree t,int x) { if (t!=NULL) { if (x==t->key) { cout key; return TRUE; } else if(x key) find(t->pleft,x); else find(t->pright,x); } else { cout << "Khong tim thay "; return FALSE ; } } GV. Thiều Quang Trung 42
  43. Đếm số nút lá int sonutLa(tree t) { if (t==NULL) return 0; if ((t->pleft == NULL)&&(t->pright==NULL)) return 1; return sonutLa(t->pleft)+sonutLa(t->pright); } GV. Thiều Quang Trung 43
  44. Đếm chiều cao của cây int height(tree t) { if (t==NULL) return(0); else return (1+ max(height(t->pleft),height(t->pright))); } GV. Thiều Quang Trung 44
  45. Đếm số nút có 1 nhánh int sonut1con(tree t) { if (t==NULL) return 0; if ((t->pleft == NULL)&&(t->pright==NULL)) return 0; if (t->pleft == NULL) return 1 + sonut1con(t->pright); if (t->pright == NULL) return 1 + sonut1con(t->pleft); else return sonut1con(t->pleft)+sonut1con(t->pright); } GV. Thiều Quang Trung 45
  46. Đếm số nút có 2 nhánh int sonut2con(tree t) { if (t==NULL) return 0; if ((t->pleft == NULL)&&(t->pright==NULL)) return 0; if (t->pleft == NULL) return sonut2con(t->pright); if (t->pright == NULL) return + sonut2con(t->pleft); else return 1 + sonut2con(t->pleft)+sonut2con(t->pright); } GV. Thiều Quang Trung 46
  47. Duyệt cây theo thứ tự giảm dần void RNL(tree t) { if(t) { RNL(t->pright); cout key pleft); } } GV. Thiều Quang Trung 47
  48. In cấu trúc cây void printtree(tree t,int dichphai) { int i; tree temp=t; if (temp!=NULL) { printtree(temp->pright,dichphai+4); for (i=1;i key pleft,dichphai+4); } } GV. Thiều Quang Trung 48