Chương 6: Cấu trúc cây - Cô Võ Thị Hường

T2  Nếu là các cây không có thứ tự thì T1=T2 B 11/51 4.1.7 Phép duyệt cây  Là phép thăm các nút trong cây một cách hệ thống sao cho tất cả các nút đều được thăm và được thăm đúng một lần  Có 3 cách duyệt cây cơ bản :  Duyệt cây theo thứ tự trước (preorder)  Duyệt cây theo thứ tự giữa (inorder)  Duyệt cây theo thứ tự sau (postorder ) 12/51 4.1.7 Phép duyệt cây  Duyệt cây theo thứ tự trước (preorder) Nếu cây khác rỗng  Thăm gốc  Duyệt cây con trái theo thứ tự trước  Duyệt cây con phải theo thứ tự trước 13/51 4.1.7 Phép duyệt cây A B E F C G H D I K 14/51 4.1.7 Phép duyệt cây  Duyệt cây theo thứ tự giữa (inorder) Nếu cây khác rỗng  Duyệt cây con trái theo thứ tự giữa  Thăm gốc  Duyệt cây con phải theo thứ tự giữa 15/51 4.1.7 Phép duyệt cây A B E F C G H D I K Giữa: EBFGAHCIDK Sau: EFGBHCIKDA Trước: ABEFGCHDIK 16/51 4.1.7 Phép duyệt cây  Duyệt cây theo thứ tự sau (postorder) Nếu cây khác rỗng  Duyệt cây con trái theo thứ tự sau  Duyệt cây con phải theo thứ tự sau  Thăm gốc 17/51 4.1.7 Phép duyệt cây A B E F C G H D I K Thứ tự trước : ABEFGCHDIK Thứ tự giữa : EBFGAHCIDK Thứ tự sau : EFGBHCIKDA 18/51 4.1.8 Cây gán nhãn và cây biểu thức  Cây gán nhãn : Mỗi nút trong cây được gán với một nhãn  Cây biểu thức : Mỗi nút trong cây được gán với một thành phần của biểu thức theo cách  Mỗi nút lá được gán với một toán hạng  Mỗi nút trong được gán với một toán tử 19/51 4.1.8 Cây gán nhãn và cây biểu thức  Ví dụ cây biểu thức P = a*(b - c) + d/e + / * a - b   d e c Duyệt theo thứ tự trước : Duyệt theo thứ sau : +*a-bc/de abc-*de/+ 20/51 4.2 CÂY NHỊ PHÂN  Khái niệm, đặc điểm, tính chất  Biểu diễn cây nhị phân  Cây nhị phân tìm kiếm 21/51 4.2.1 Khái niệm, đặc điểm, tính chất    Là dạng đặc biệt của cây. Mỗi nút trong có tối đa 2 con, phân biệt con bên trái và con bên phải của nút Là cây có thứ tự Các dạng cây nhị phân đặc biệt  Cây nhị phân suy biến 22/51 4.2.1 Khái niệm, đặc điểm, tính chất  Các dạng cây nhị phân đặc biệt  Cây nhị phân hoàn chỉnh : Các mức đều đạt tối đa số nút trừ mức cao nhất trong cây 23/51 4.2.1 Khái niệm, đặc điểm, tính chất  Các dạng cây nhị phân đặc biệt  Cây nhị phân hoàn chỉnh đầy đủ : Các mức đều đạt tối đa số nút 24/51 4.2.1 Khái niệm, đặc điểm, tính chất  Trong cây nhị phân  Số lượng nút tối đa ở mức i là 2i-1  Số lượng nút tối đa ở cây nhị phân mức i 2i – 1  Trong các cây nhị phân có cùng số nút thì cây nhị phân suy biến có chiều cao lớn nhất, cây nhị phân hoàn chỉnh, hoàn chỉnh đầy đủ có chiều cao nhỏ nhất 25/51 4.2.2 Biểu diễn cây nhị phân  Biểu diễn bằng mảng  Biểu diễn bằng con trỏ 26/51 4.2.2 Biểu diễn cây nhị phân  Biểu diễn bằng mảng : Dùng mảng một chiều làm cấu trúc lưu trữ.  Cách 1 : Gốc lưu ở vị trí 0, cha lưu ở vị trí i thì con trái lưu ở vị trí 2*i+1, con phải lưu ở vị trí 2*i+2  Các cách khác : (Giới thiệu trong biểu diễn cây tổng quát Ví dụ : 27/51 4.2.2 Biểu diễn cây nhị phân A  Biểu diễn bằng mảng B C  D A B 0 1 C 2 3 4 5 6 D E ... 7 … 15 … 28/51 4.2.2 Biểu diễn cây nhị phân   Biểu diễn bằng con trỏ Mỗi nút trong cây là một bản ghi gồm có 3 trường left data right data chứa thông tin của nút  left là một con trỏ trỏ vào con bên trái của nút  right là một con trỏ trỏ vào con bên phải của nút Cây là con trỏ trỏ vào nút gốc   29/51 4.2.2 Biểu diễn cây nhị phân  Ví dụ A B NULL  D NULL NULL C E NULL NULL F NULL NULL G NULL Nhận xét : Cây nhị phân có n nút thì có 2*n con trỏ Trong đó n-1 con trỏ khác NULL n+1 con trỏ NULL 30/51 4.2.3 Cây nhị phân tìm kiếm  Định nghĩa, khai báo cấu trúc dữ liệu  Các phép toán cơ bản 31/51 Định nghĩa cây nhị phân tìm kiếm  Là cây nhị phân đặc biệt dùng để lưu trữ và tìm kiếm thông tin  Khóa của nút cha không nhỏ hơn khóa của nút con bên trái và không lớn hơn khóa của nút con bên phải 32/51 Khai báo cấu trúc dữ liệu struct node { key ; node *left, *right ; } *t; 33/51 Các phép toán cơ bản  Khởi tạo cây t rỗng : creat(t)  Kiểm tra cây t rỗng : empty(t)  Chèn khóa x vào cây t : insert(x,t)  Loại khóa x trong cây t : del(x,t)  Duyệt cây t theo 3 cách duyệt cơ bản 34/51 Các phép toán cơ bản  Khởi tạo cây t rỗng : creat(t) void creat(node *&t) { t = NULL; } 35/51 Các phép toán cơ bản  Kiểm tra cây t rỗng : empty(t) void empty(node *t) { return t == NULL; } 36/51 Các phép toán cơ bản  Chèn khóa x vào cây t : insert(x,t) void insert( x, node *&t) { if (t==NULL) { t =new node; t->key=x ; t->left =NULL ; t->right =NULL ; } else if (xkey) insert(x,t->left) else insert(x,t->right) } 37/51 Các phép toán cơ bản  Loại khóa x trong cây t  Nếu t->key== x x 38/51 Các phép toán cơ bản  Trường hợp 1 : nếu t->left==NULL t p x p=t ; t =t->right ; delete(p) ; 39/51 Các phép toán cơ bản  Trường hợp 2 : nếu t->right==NULL p=t ; t =t->right ; delete(p) ; p t x 40/51 Các phép toán cơ bản  Trường hợp 3 : Nếu t->left!=NULL, t->right!=NULL t p=t->left Nếu p->right==NULL p q x 41/51 Các phép toán cơ bản  Trường hợp 3 : nếu t->left!=NULL, t->right!=NULL t p p=t->left Nếu p->right!=NULL max s q max 42/51 Các phép toán cơ bản  Nếu t->key!=x if (t->key>x) del(x,t->left) ; else del(x,t->right); !x 43/51 Các phép toán cơ bản  Loại khóa x trong cây t : del(x,t) void del( x, node *&t) { node *p,*q,*s; if (t!=NULL) { if (t->key==x) if (t->left==NULL) { p=t; t =t->right; delete(p);} else if (t->right==NULL) { p=t; t =t->left; delete(p);} else 44/51 Các phép toán cơ bản else { p=t->left; if (p->right==NULL) {p->right=t->right;q=t; t=p; delete q;} else { s=p; while (s->right->right!=NULL) s=s->right; t->key=s->right->key; q=s->right; s->right = s->right->left; delete q; } } else if (t->key>x) del(x,t->left) ; else del(x,t->right); } } 45/51 Các phép toán cơ bản  Duyệt cây t theo thứ tự trước void hienpre(node * t) { if (t!=NULL) { cout<key<<“ “ ; hienpre(t->left) ; hienpre(t->right) ; } } 46/51 Các phép toán cơ bản  Duyệt cây t theo thứ tự giữa void hienin(node * t) { if (t!=NULL) { hienin(t->left) ; cout<key<<“ “ ; hienin(t->right) ; } } 47/51 Các phép toán cơ bản  Duyệt cây t theo thứ tự sau void hienpost(node * t) { if (t!=NULL) { hienpost(t->left) ; hienpost(t->right) ; cout<key<<“ “ ; } } 48/51