Chương 3- Cây

CHƯƠNG 3- CÂY Chương 3: Cây 3.1 Các khái niệm cơ bản 3.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ân 3.1 CÁC KHÁI NIỆM CƠ BẢN Khái niệm cây: Cây gồm một tập hợp hữu hạn các nút-node Có một quan hệ thứ tự bộ phận (cha-con) giữa các nút. 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. 3.1 CÁC KHÁI NIỆM CƠ BẢN Bậ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 (internal 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. 3.1 CÁC KHÁI NIỆM CƠ BẢN Mứ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. 3.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. 3.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ân 3.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT Câ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 nhau 3.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT Tí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) 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN Biể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. 3.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. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ví dụ: 1 3 7 6 5 4 2 Ta 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] 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ví dụ: 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Phé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. 3.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út Khó khăn trong việc bổ sung, loại bỏ các phần tử 3.2.2 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CÁCH LƯU TRỮ MÓC NỐI Nhượ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ỏ. BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Cấ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ái Right: trỏ đến nút con phải typedef int element_type; typedef struct node { element_type element; struct node *left, *right; } NODE; BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Câ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; BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Phép toán cơ sở: Phép xác định con trái: V=*V.Left Phép xác định con phải: V=*V.right Phé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: BIỂ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. PHÉP DUYỆT CÂY Duyệ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) THỦ TỤC PREORDER Nếu cây rỗng thì không làm gì cả. Nếu cây không rỗng thì: 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 THỦ TỤC PREORDER void Preorder(NODE *root) { if (root != NULL) { coutelement; Preorder (root->left); Preorder (root->right); } } THỦ TỤC INORDER Nế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ữa Thăm gốc Duyệt cây con phải theo thứ tự giữa THỦ TỤC INORDER void Inorder(NODE *root) { if (root != NULL) { Inorder (root->left); coutelement; Inorder (root->right); } } THỦ TỤC POSTORDER Nế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ự sau Duyệt cây con phải theo thứ tự sau Thăm gốc THỦ TỤC POSTORDER void Postorder(NODE *root) { if (root != NULL) { Postorder (root->left); Postorder (root->right); coutelement; } } Bài tập Bài 1.Viết chương trình thực hiện các công việc sau Khởi tạo và nhập giá trị của một cây Viế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.