Bài giảng Cấu trúc dữ liệu 1: Chương 4C - Huỳnh Cao Thế Cường

Nội dung chính được trình bày trong chương này gồm có: Cài đặt cây nhị phân, một số tính chất của cây nhị phân, BST–Thêm một nút có khóa cho trước vào cây TKNP, BST–Xóa một nút có khóa cho trước ra khỏi cây TKNP,... Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu 1: Chương 4C - Huỳnh Cao Thế Cường TRƯỜNGĐẠIHỌCANGIANGKHOAKỸTHUẬTCÔNGNGHỆMÔITRƯỜNG CẤUTRÚCDỮLIỆU1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@agu.edu.vn 1 1 CÂY VÀ CÂY NHỊ PHÂN Định nghĩa: Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó có 1 nút đặc biệt được gọi là 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 người ta còn gọi là quan hệ cha-con. 2 CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY Mối quan hệ cha - con (parenthood): để xác định hệ thống cấu trúc trên các nút. Mỗi nút, trừ nút gốc, có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. Mỗi nút biểu diễn một phần tử trong tập hợp đang xét Mối quan hệ cha con được biểu diễn theo qui ước nút cha ở dòng trên nút con ở dòng dưới và được nối bởi một đoạn thẳng. 3 CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY Bậc của một nút: Là số cây con của nút đó . Bậc của một cây: Là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây). Cây có bậc n thì gọi là cây n-phân. Nút gốc: Là nút không có nút cha. 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 và không phải là gốc. Mỗi nút, trừ nút gốc, có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. 4 CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY Mức của một nút:  Mức (gốc (T) ) = 0.  Gọi T1, T2, T3, ... , Tn là các cây con của T0  Mức (T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) + 1. Độ dài đường đi từ gốc đến nút x: Là số nhánh cần đi qua kể từ gốc đến x. Độ dài đường đi trung bình: PI = PT/n (n là số nút trên cây T). Rừng cây: Là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng. 5Một số ví dụ về đối tượng các cấu trúc dạng cây Sơ đồ tổ chức của một công ty 6 CÂY NHỊ PHÂN (BINARY TREES) Định nghĩa  Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con.  Các nút con của cây được phân biệt thứ tự rõ ràng • một nút con gọi là nút con trái • một nút con gọi là nút con phải. • Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. 7CÂY NHỊ PHÂN (BINARY TREES) 8CÂY NHỊ PHÂN (BINARY TREES) 9 Một số tính chất của cây nhị phân Số nút nằm ở mức I 2I Số nút lá 2h-1, với h là chiều cao của cây.Chiều cao của cây h log2(số nút trong cây). Số nút trong cây 2h-1. 10 Cây nhị phân Duyệt cây nhị phân  Duyệt tiền tự (Node-Left-Right): duyệt nút gốc, duyệt tiền tự con trái rồi duyệt tiền tự con phải.  Duyệt trung tự (Left-Node-Right): duyệt trung tự con trái rồi đến nút gốc sau đó là duyệt trung tự con phải.  Duyệt hậu tự (Left-Right-Node): duyệt hậu tự con trái rồi duyệt hậu tự con phải sau đó là nút gốc. Node Left Right 11 Cây nhị phân A B C D E F GH I J K L M 12 Cây nhị phân A B C D E F GH I J K L M Các danh sách duyệt cây nhị phân Tiền tự ABDHIEJCFKLGM Trung tự HDIBJEAKFLCGM Hậu tự HIDJEBKLFMGCA 13 Cài đặt cây nhị phântypedef int ElementType;struct TreeNode;typedef struct TreeNode *Node;typedef struct TreeNode *Tree;//Khai bao cay nhi phanstruct TreeNode{ ElementType Element; Node Left; //Con tro Trai Node Right; //Con tro Phai}; 14 Cài đặt cây nhị phân Tạo cây rỗng : Cây rỗng là một cây là không chứa một nút nào cả. Tree MakeEmpty(Tree T) { if(T!=NULL) { MakeEmpty(T->Left); MakeEmpty(T->Right); free(T); } return NULL; } 15 Cài đặt cây nhị phân Kiểm tra cây rỗng int IsEmpty_Tree(Tree T) { return (T==NULL); } 16 Cài đặt cây nhị phân Xác định con trái của một nút Node LeftChild(Tree p) { if (p!=NULL) return p->Left; else return NULL; } Xác định con phải của một nút Node RightChild(Tree p) { if (p!=NULL) return p->Right; else return NULL; } 17 Cài đặt cây nhị phân Kiểm tra nút lá:  Nếu nút là nút lá thì nó không có bất kỳ một con nào cả nên khi đó con trái và con phải của nó cùng bằng NULL int IsLeaf(Tree p) { if(p!=NULL) return(LeftChild( ...