Bài giảng Cấu trúc dữ liệu: Cây nhị nhân - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Cây nhị nhân cung cấp cho người học những kiến thức như: Định nghĩa Cây nhị phân; Phép duyệt cây; Cây liên kết; Thiết kế của Cây nhị phân; Thiết kế Node; Phương thức duyệt cây NLR; Phương thức hủy vùng nhớ đã cấp;...Mời các bạn cùng 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: Cây nhị nhân - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết TS. Lê Minh Trung – ThS Lương Trần Ngọc KhiếtKhoa Công nghệ Thông tin, Đại học Sư phạm TP. HCMCay nhi phan (Binary Tree) Cây nhị nhân (Binary Tree) Cây nhị phân tìm kiếm (Binary Search Tree) Cây cân bằngĐịnh nghĩa Cây Nhị Phân Cây nhị phân  Là cây mỗi node chỉ có tối đa hai con  Là cây trong đó mỗi node có cây con trái và cây con phải đều là cây nhị phânCác định nghĩa khác Mức:  Node gốc ở mức 0.  Node gốc của các cây con của một node ở mức m là m+1. Chiều cao:  Cây rỗng là 0.  Chiều cao lớn nhất của 2 cây con cộng 1  (Hoặc: mức lớn nhất của các node cộng 1) Đường đi (path)  Tên các node của quá trình đi từ node gốc theo các cây con đến một node nào đó.Các định nghĩa khác (tt.) Node trước, sau, cha, con:  Node x là trước node y (node y là sau node x), nếu trên đường đi đến y có x.  Node x là cha node y (node y là con node x), nếu trên đường đi đến y node x nằm ngay trước node y. Node lá, trung gian:  Node lá là node không có node con nào.  Node trung gian không là node gốc hay node lá.Các tính chất khác Cây nhị phân đầy đủ, gần đầy đủ:  Đầy đủ: các node lá luôn nằm ở mức cao nhất và các nút không là nút lá có đầy đủ 2 nhánh con.  Gần đầy đủ: Giống như trên nhưng các node lá nằm ở mức cao nhất (hoặc trước đó một mức) và lấp đầy từ bên trái sang bên phải ở mức cao nhất. Chiều cao của cây có n node:  Trung bình h = [lg n] + 1  Đầy đủ h = lg (n + 1)  Suy biến h = n Số phần tử tại mức i nhiều nhất là 2iVí dụ  Gốc (root): node 0 Mức 0  Chiều cao: 4 = lg(15 +1) Mức 1  Node 1 là node cha node Mức 2 3,4. Mức 3  Node 3,4 là node con node 1 và là hai node anh em.  Node 11 là node lá, node 2 là node trong.Phép duyệt cây Duyệt qua từng node của cây (mỗi node 1 lần) Cách duyệt:  Chính thức: NLR, LNR, LRN, NRL, RNL, RLN  Chuẩn: NLR (preorder), LNR (inorder), LRN (postorder)Ví dụ về phép duyệt cây NLR A B C D E F G H I J K L M N O P Kết quả: A B D H I N E J O K C F L P G MVí dụ về phép duyệt cây LNR A B C D E F G H I J K L M N O P Kết quả: H D N I B J O E K A F P L C M GVí dụ về phép duyệt cây LRN A B C D E F G H I J K L M N O P Kết quả: H N I D O J K E B P L F M G C ACây liên kết Thiết kế của Cây Nhị Phântemplateclass BinaryTree{public: BinaryTree(void); //phương thức khởi tạo BinaryTree(const BinaryTree &); //phương thức khởi tạo ~BinaryTree(void); //phương thức hủy bool IsEmpty() const; //kiểm tra rỗng int Height() const; //tính chiều cao void Clear(); //xóa bộ nhớ được cấp void PreOrder(void (*visit)(Record &)) const; //duyệt cây NLR void PostOrder(void (*visit)(Record &)) const;//duyệt cây LRN void InOrder(void (*visit)(Record &)) const; //duyệt cây LNR void operator=(const BinaryTree &); //toán tử gánprotected: BinaryNode *root; //con trỏ gốcprivate: //phương thức phụ trợ}; Thiết kế Nodetemplate templatestruct Record struct BinaryNode{ { Key key; Record data; Value value; BinaryNode *left, *right; Record(){}; BinaryNode(); Record(Key k, Value v) BinaryNode(Key &k, Value &v); {key=k; value =v;} BinaryNode(Record &);}; };template templateBinaryNode:: BinaryNode::BinaryNode(Record &x){ BinaryNode(Key &k, Value &v){this -> data = x; (this -> data).key = k;this ->left = this->right = (this ->data).value =v;nullptr; this ->left = this->right = nullptr;} }templateclass BinaryTree ...