- Trang Chủ
- Cơ sở dữ 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
Xem mẫu
- 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);
}
}
nguon tai.lieu . vn
