I. Định nghĩa và khái niệm
1. Định nghĩa: Là cây mà tại mỗi nút có tối đa 2 con
2. Khái niệm:
- Nút gốc
- Nút lá
- Chiều cao của cây
. Nút gốc có chiều cao là 1
. Nút cha có chiều cao là h
thì nút con có chiều cao là h+1
3. Tổ chức dữ liệu
Struct NUT
{
<Type> Data;
NUT *left; *right;
};
typedef NUT *Tree;
Vd:
4. Các phép duyệt cây
- NLR(duyệt trái) A B C D E F
- LNR(duyệt giữa) C B D A E F
- LRN(duyệt phải) C D B F E A
- Theo mức A B E C D F
void NLR(Tree Root)
{
if(Root!= NULL)
{
<Thăm Root->Data>;
NLR(Root->left);
NLR(Root->right);
}
}
void LNR(Tree Root)
{
if(Root!= NULL)
{
LNR(Root->left);
<Thăm Root->Data>;
LNR(Root->right);
}
}
void LRN(Tree Root)
{
if(Root!= NULL)
{
LRN(Root->left);
LRN(Root->right);
<Thăm Root->Data>;
}
}
void DuyetMuc(Tree Root)
{
Queue = 0;
PUSH(Root, Queue);
While(Quee!=0){
x = POP(Queue);
<Thăm x->Data>;
if(x->left!=NULL) PUSH(x->left, Queue);
if(x->right!=NULL) PUSH(x->right, Queue);
}
}
Bài tập:
Tổ chức cây nhị phân chứa các số nguyên
1. Đếm cây có bao nhiêu nút
2. Tính tổng giá trị của các nút lá
3. Tính chiều cao của cây
Struct NUT
{
int x;
NUT *left, *right;
};
typedef NUT *Tree;
1. Đếm xem cây có bao nhiêu nút(dùng đệ quy)
int Dem(Tree Root)
{
if(Root==NULL) return 0;
else
return 1+Dem(Root->left) + Count(Root->right);
}
2. Tính tổng giá trị của các nút lá
int leafSum(Tree Root)
{
if(Root==NULL) return 0;
else if((Root->left)==NULL)&&(Root->right==NULL)) return Root->x;
else return leafSum(Root->left)+leafSum(Root->right);
}
3. Tính chiều cao của cây
int max(int a, int b)
{
if(a>b) return a;
else return b;
}
int hight(Tree Root)
{
if(Root==NULL) return 0;
else return 1+ max(hight(Root->left),hight(Root->right));
}
II. Cây tìm kiếm nhị phân(BST = Binary Search Tree)
1. Định nghĩa: Là cây nhị phân mà khóa ở mọi nút nó luôn luôn >= khóa của tất cả các nút ở cây con bên trái và đồng thời <= khóa của tất cả các nút ở cây con bên phải.
2. Các thao tác cơ bản
a. Bổ sung giá trị x vào cây
void insert(int x, Tree &Root)
{
if(Root==NULL)
{
Root=new (NUT);
Root->Data = x;
Root->left=Root->right=NULL;
}
else if(x<Root->Data) insert(x, Root->left);
else if(x>Root->Data) insert(x, Root->right);
}
b. Tìm kiếm(kiểm tra) giá trị x có trên cây hay không(BST)
- Không tìm thấy trả về giá trị NULL.
- Tìm thấy: trỏ đến nút tìm được
Tree Search(int x, Tree Root)
{
if(Root==NULL) return NULL;
else if(x==Root->Data) return Root;
else if(x<Root->Data) return Search(x, Root->left);
else return Search(x, Root->right);
}