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

CHƯƠNG 3- CÂY1Chương 3: Cây3.1 Các khái niệm cơ bản3.2 Cây nhị phân 3.2.1 Định nghĩa và tính chất 3.2.2 Biểu diễn cây nhị phân 3.2.3 Duyệt cây nhị phân23.1 CÁC KHÁI NIỆM CƠ BẢNKhái niệm cây:Cây gồm một tập hợp hữu hạn các nút-nodeGiữa các nút có một quan hệ thứ tự bộ phận (cha-con).Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root).Cây không có nút nào gọi là cây rỗng.33.1 CÁC KHÁI NIỆM CƠ BẢNBậc – degree – của một nút là số con của nó. Nút lá (leaf) –terminal node – là nút không có con, bậc của nút lá bằng 0.Ngược với nút lá là các nút có con, gọi là nút phân nhánh hay nút trung gian (branch node).Bậc của cây là bậc cao nhất của các nút trong cây.Cây nhị phân là cây bậc 2. Nếu cây có bậc cao hơn 2 ta gọi là cây nhiều nhánh.43.1 CÁC KHÁI NIỆM CƠ BẢNMức – level – là đẳng cấp của nút trong mô hình phân cấp. Quy ước nút gốc có mức 1, nếu nút cha có mức i thì nút con có mức i + 1.Chiều cao – height – hay con gọi là chiều sâu – depth – là mức lớn nhất của nút trên cây.Đường đi – path – từ nút p đến nút q trên một cây là dãy nút p = n1,n2,,nk = q sao cho ni là cha của ni+1.53.1 CÁC KHÁI NIỆM CƠ BẢNĐộ dài đường đi – path length – là số cung nối từng cặp hai nút trên đường đi, nó chính là số nút trừ 1.Cây có thứ tự - ordered tree – là cây mà có xét đến thứ tự giữa các con của một nút. Nói nôm na là có xét đến quan hệ “anh em”.Con trưởng hay con cực trái là một nút là con thứ nhất trong quan hệ thứ tự giữa các nút cùng cha.Em liền kề của một nút là nút đứng ngay sau trong quan hệ thứ tự giữa các nút cùng cha.Rừng – forest- là danh sách hữu hạn cây. 63.2 CÂY NHỊ PHÂN3.2.1 Định nghĩa và tính chất.3.2.2 Biểu diễn cây nhị phân.3.2.3 Duyệt cây nhị phân73.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤTCây nhị phân là cây bậc 2, một nút có nhiều nhất là hai con.Cây nhị phân là cây có xét đến thứ tự, phân biệt con thứ nhất, con thứ hai gọi là con trái và con phải.Ba cây nhị phân này có cùng số nút nhưng có cấu trúc khác nhau83.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤTTính chất của cây nhị phân:Số lượng tối đa của mỗi nút ở mức i trên cây nhị phân là 2i-1 (i ≥ 1).Số lượng tối đa của mỗi nút trên cây nhị phân có chiều cao h là 2h -1 (h ≥ 1).( Chứng minh)93.2.1 BIỂU DIỄN CÂY NHỊ PHÂNBiểu diễn cây nhị phân bằng cấu trúc mảng.Biểu diễn cây nhị phân bằng danh sách các nút.Biểu diễn cây nhị phân bằng móc nối các nút.103.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Với cây nhị phân hoàn chỉnh hoặc đầy đủ trái ta có thể dùng cấu trúc mảng để thể hiện một cây: Xếp liên tiếp các nút của cây vào mảng theo thứ tự từ trên xuống dưới, từ trái sang phải. Trường hợp một nút bị khuyết thì thay bằng giá trị đặc biệt ví dụ giá trị Null. 113.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNGVí dụ: ABDECFG1376542Ta lưu trữ cây nhị phân đầy đủ bằng 1 vector V theo nguyên tắc nút thứ i của cây được lưu trữ ở V[i]123.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNGVí dụ: ABCDEFGV[1]V[2]V[3]V[4]V[5]V[6]V[7]133.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNGPhép xác định nút con trái và con phải: nút tại chỉ số mảng i có con trái tại chỉ số 2i và con phải tại chỉ số 2i+1.Phép xác định nút cha: nút tại chỉ số mảng j có cha tại chỉ số [j/2].Phép duyệt: là phép duyệt mảng.143.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNGƯu điểm:Triển khi nhanh.Truy cập nhanh chóng vào bất kỳ nút nào, chi phí truy cập là đồng đều cho mọi nút.Nhược điểm:Rất phí chỗ nếu cây “gầy”, khuyết nhiều nútKhó khăn trong việc bổ sung, loại bỏ các phần tử153.2.2 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CÁCH LƯU TRỮ MÓC NỐINhược điểm của việc lưu trữ cây nhị phân bằng cấu trúc mảng là khó và mất thời gian trong việc bổ sung, loại bỏ các nút thường xuyên, để khắc phục ta có thể lưu trữ bằng cách lưu trữ móc nối.Trường hợp này ta móc nối trực tiếp nút cha với nút con bằng con trỏ.16BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚTCấu trúc của một nút gồm 3 trường: Data: chứa dữ liệu;Left: trỏ đến nút con tráiRight: trỏ đến nút con phảitypedef int element_type; typedef struct node { element_type element; struct node *left, *right; } NODE;17BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚTCây sẽ được trỏ bằng một con trỏ đến nút gốc cây. Kiểu Ref là kiểu con trỏ đến 1 nút;18Khai bao câytypedef int TData;typedef struct TNode{TData Data; TNode* left; TNode* right; };typedef TNode* TTree;19Khởi tạo cây rỗngvoid MakeNullTree(TTree *T){ (*T)=NULL;}20Kiểm tra cây rỗngint EmptyTree(TTree T){ return T==NULL;}21Tạo câyTTree node(TData v,TTree l,TTree r){TTree N; N=(TNode*)malloc(sizeof(TNode)); N->Data=v; N->left=l; N->right=r; return N;}22BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚTPhép toán cơ sở:Phép xác định con trái: V=*V.LeftPhép xác định con phải: V=*V.rightPhép xác định nút cha: rất khó xác định nên phải thêm một con trỏ cha nữa trong cấu trúc.Phép duyệt cây được trình bày sau:23BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚTƯu điểm:Rất linh hoạt đối với các phép toán thêm vào, lấy ra một nút, một cây con.Không lãng phí vùng nhớ nếu cây “gầy”Nhược điểm:Rất phức tạp khi biểu diễn.24PHÉP DUYỆT CÂYDuyệt theo thứ tự trước (Preoder traversal)Duyệt theo thứ tự giữa (Inoder traversal)Duyệt theo thứ tự sau (Postorder traversal)25THỦ TỤC PREORDERNếu cây rỗng thì không làm gì cả.Nếu cây không rỗng thì:Thăm gốcDuyệt cây con trái theo thứ tự trướcDuyệt cây con phải theo thứ tự trước26THỦ TỤC PREORDERvoid PreOrder(TTree T){TTree p; p=T; if(p!=NULL) { printf("%d ",p->Data); PreOrder(p->left); PreOrder(p->right); }}27THỦ TỤC INORDERNếu cây rỗng thì không làm gì cả.Nếu cây không rỗng thì:Duyệt cây con trái theo thứ tự giữaThăm gốcDuyệt cây con phải theo thứ tự giữa28THỦ TỤC INORDERvoid InOrder(TTree T){TTree p; p=T; if(p!=NULL) { InOrder(p->left); printf("%d ",p->Data); InOrder(p->right); }}29THỦ TỤC POSTORDERNếu cây rỗng thì không làm gì cả.Nếu cây không rỗng thì:Duyệt cây con trái theo thứ tự sauDuyệt cây con phải theo thứ tự sauThăm gốc30THỦ TỤC POSTORDERvoid PosOrder(TTree T){TTree p; p=T; if(p!=NULL) { PosOrder(p->left); PosOrder(p->right); printf("%d ",p->Data); }}31Bài tập mẫuViết chương trình tạo cây nhị phân và hiển thị theo tiền tố trung tố hậu tố32void main(){TTree T; clrscr(); T=node(5,node(15,node(25,NULL, node(35,NULL,node(50,NULL,node(100,NULL,NULL)))),NULL),NULL); cout<<"TIEN TO: "; PreOrder(T);cout<<"\n"; cout<<"TRUNG TO: "; InOrder(T); cout<<"\n"; cout<<"HAU TO: "; PosOrder(T);cout<<"\n"; getch();}33Bài tậpViết chương trình đếm số nút lá trong cây cho trướcViết chương trình đếm số nút của cây cho trước viết chương trình tính chiều cao cảu cây nhị phân cho trước.(chiều cao của cây là khoảng cách từ gốc đến nút lá xa nhất)34Bài tập làm thêmBài 1.Viết chương trình thực hiện các công việc sauKhởi tạo và nhập giá trị của một câyViết các chương trình duyệt cây theo thứ tự trước, giữa, sau (không dùng đệ quy)Bài 2: Làm các bài tập chương 6, trang 143-146 sách Cấu trúc dữ liệu và giải thuật, Đỗ Xuân Lôi, NXB Đại học Quốc gia Hà Nội.35