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

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST

Báo xấu

26
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ết Khoa Công nghệ Thông tin, Đại học Sư phạm TP. HCM
Cay 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ân
Cá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à 2i
Ví 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 M
Ví 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 G
Ví 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 A
Cây liên kết
Thiết kế của Cây Nhị Phân template class 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án protected: BinaryNode *root; //con trỏ gốc private: //phương thức phụ trợ };
Thiết kế Node template template struct 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 template BinaryNode:: 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; } }
template class BinaryTree Lớp 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án protected: BinaryNode *root; //con trỏ gốc private: int getHeight(BinaryNode *) const; void makeEmpty(BinaryNode* &); void recursivePreOrder(BinaryNode*,void (*visit)(Record &)) const; void recursivePostOrder(BinaryNode*,void (*visit)(Record &)) const; void recursiveInOrder(BinaryNode*,void (*visit)(Record &)) const; void Copy(const BinaryTree* &, BinaryTree* &); };
Các phương thức template template int BinaryTree:: BinaryTree:: getHeight(BinaryNode* BinaryTree(void) subRoot) const { { if(root == nullptr)return 0; root = nullptr; return max(getHeight(subRoot->left), } getHeight(subRoot -> right))+1; } template bool template BinaryTree:: int IsEmpty() const BinaryTree::Height() { const{ return root==nullptr; return getHeight(root); } }
Phương thức duyệt cây NLR template void BinaryTree::recursivePreOrder (BinaryNode* subRoot, void (*visit)(Record &)) const { if(subRoot!=nullptr){ (*visit)(subRoot->data); recursivePreOrder(subRoot->left, visit); recursivePreOrder(subRoot->right, visit); } } template void BinaryTree::PreOrder(void (*visit)(Record &)) const { recursivePreOrder(root,visit); }
Phương thức duyệt cây LNR template void BinaryTree::recursiveInOrder (BinaryNode* subRoot, void (*visit)(Record &)) const { if(subRoot!=nullptr){ recursiveInOrder(subRoot->left, visit); (*visit)(subRoot->data); recursiveInOrder(subRoot->right, visit); } } template void BinaryTree::InOrder(void (*visit)(Record &)) const { recursiveInOrder(root,visit); }
Phương thức duyệt cây LRN template void BinaryTree::recursivePostOrder (BinaryNode* subRoot, void (*visit)(Record &)) const { if(subRoot!=nullptr){ recursivePostOrder(subRoot->left, visit); recursivePostOrder(subRoot->right, visit); (*visit)(subRoot->data); } } template void BinaryTree::PostOrder(void (*visit)(Record &)) const { recursivePostOrder(root,visit); }
Phương thức Copy template void BinaryTree::Copy(const BinaryTree* &Q, BinaryTree* &P) { if(Q==nullptr)P=nullptr; else{ P = new BinaryNode(Q -> data); Copy(Q->left, P->left); Copy(Q-> right, P->right); } }