Cây nhị phân là cấu trúc dữ liệu dùng để lưu trữ một tập các dữ liệu có cùng kiểu và các dữ liệu này được lưu trữ không liên tiếp trong bộ nhớ. Mỗi nút (phần tử) trên cây sẽ giữ địa chỉ của nút con bên trái và địa chỉ của nút con bên phải , khi đó chỉ cần biết địa chỉ nút gốc (nút không là con của bất kỳ nút nào ) là có thể truy xuất đến tất cả các nút.
Danh sách liên kết đơn là trường hợp đặc biệt của cây nhị phân mà tất cả các nút chỉ con trái hoặc tất cả các nút chỉ con phải.
Ưu khuyết điểm của cây nhị phân.
Ưu điểm: Có được ưu điểm của danh sách liên kết như là: Thao tác hủy hoặc chèn rất nhanh , có thể cấp phát thêm nút hoặc thu hồi bộ nhớ đã cấp phát cho nút và kích thước cây không bị giới hạn bởi 64 KB.
Có thêm ưu điểm khác là tìm kiếm nhanh (trong khi danh sách liên kết tìm kiếm chậm).
Nhược điểm: Tốn thêm bộ nhớ để lưu trữ địa chỉ nút con trái, con phải.
**** Code xử lý trong cây nhị phân.
I- Khai báo cấu trúc của 1 nút
Mã:
struct node
{
int data;//Noi dung cua nut
node *letf , *right;//Dia chi nut trai , nut phai
};
typedef node *nodeptr
II - Khởi tạo cây
Mã:
void init_tree(nodeptr &root)
{
root = NUll;
}
III - Kiểm tra cây rỗng
Mã:
int empty_tree(nodeptr root)
{
if(root == NULL) return 1;
else return 0;
}
IV - Tạo 1 nút cho cây
Mã:
nodeptr make_node(int x)
{
noteptr p = new node;
p->data = x;
p->left = p->right = NULL;
return p;
}
V - Chèn 1 nút vào cây có sẵn
Mã:
nodeptr insert_node(nodeptr &root , int x)
{
nodeptr p =make_node(x) ;
nodeptr q,f;
if(root == NULL)
{
root = p;
}
else
{
root = q;
f=NULL;
while(q!=NULL)
{
f = q;
if(x < q ->data)
{
q = q->left;
}
else
{
q = q->right;
}
}
if(x < f->data)
{
f->left = p;
}
else
{
f->right = p;
}
}
return p;
}
VI - Tìm kiếm
Mã:
nodeptr search_node(nodeptr root , int x)
{
nodeptr p = root;
while(p!=NULL)
{
if(p->data == x) return p;
else if(x < p->data) p = p->left;
else p = p->right;
}
return NULL;
}
VII - Hàm hủy 1 nút của cây
Mã:
int del_node(nodeptr &root, int x)
{
nodeptr p, q, f;
p = root;
f = NULL;
while(p!=NULL)
{
if(p->data == x) break;
else
{
f = p;
if(x<p->data) p = p->left;
else p = p->right;
}
}
if(p==NULL) return 0;
else
{
if(p->left !=NULL && p->right!=NULL)
{
q = p->right;
f = p;
while(q->left!=NULL)
{
f = q;
q = q->left;
}
p->data = q->data;
p = q;
}
if(p->left!=NULL) q = p->left;
else q = p->right;
if(p==root) root = q;
else
{
if(p=f->left) f->left = q;
else f->right = q;
}
delete p;
return 1;
}
}
VIII - Hàm nhập dữ liệu vào cây
Mã:
void input_tree(nodeptr &root)
{
int n,x;
root = NULL;
printf("\nSo phan tu: ");
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
printf("Phan tu thu %d: ",i);
scanf("%d", &x);
insert_node(root, x);
}
}
IX - Duyệt cây
//Có 3 cách duyệt cây
//Cách 1 : Node - Left - Right (NLR)
/*trong đó: Node là nút gốc(root)
Left là nút bên trái của nút gốc
Right là nút bên phải của nút gốc */\
Mã:
void NLR(nodeptr root)
{
if(root!=NULL)
{
printf("%d", root->data);
NLR(root->left);
NLR(root->right);
}
}
//Cách 2: Left -Node -Right
Mã:
void LNR(nodeptr root)
{
if(root!=NULL)
{
LNR(root->left);
printf("%d", root->data);
LNR(root->right);
}
}
//Cách 3: Left - Right -Node
Mã:
void LRN(nodeptr root)
{
if(root!=NULL)
{
LNR(root->left);
printf("%d", root->data);
LNR(root->right);
}
}
XX- Hàm hủy cây
Mã:
void del_tree(nodeptr &root)
{
if(root!=NULL)
{
del_tree(root->left);
del_tree(root->right);
delete root;
root = NULL;
}
}
Danh sách liên kết đơn là trường hợp đặc biệt của cây nhị phân mà tất cả các nút chỉ con trái hoặc tất cả các nút chỉ con phải.
Ưu khuyết điểm của cây nhị phân.
Ưu điểm: Có được ưu điểm của danh sách liên kết như là: Thao tác hủy hoặc chèn rất nhanh , có thể cấp phát thêm nút hoặc thu hồi bộ nhớ đã cấp phát cho nút và kích thước cây không bị giới hạn bởi 64 KB.
Có thêm ưu điểm khác là tìm kiếm nhanh (trong khi danh sách liên kết tìm kiếm chậm).
Nhược điểm: Tốn thêm bộ nhớ để lưu trữ địa chỉ nút con trái, con phải.
**** Code xử lý trong cây nhị phân.
I- Khai báo cấu trúc của 1 nút
Mã:
struct node
{
int data;//Noi dung cua nut
node *letf , *right;//Dia chi nut trai , nut phai
};
typedef node *nodeptr
II - Khởi tạo cây
Mã:
void init_tree(nodeptr &root)
{
root = NUll;
}
III - Kiểm tra cây rỗng
Mã:
int empty_tree(nodeptr root)
{
if(root == NULL) return 1;
else return 0;
}
IV - Tạo 1 nút cho cây
Mã:
nodeptr make_node(int x)
{
noteptr p = new node;
p->data = x;
p->left = p->right = NULL;
return p;
}
V - Chèn 1 nút vào cây có sẵn
Mã:
nodeptr insert_node(nodeptr &root , int x)
{
nodeptr p =make_node(x) ;
nodeptr q,f;
if(root == NULL)
{
root = p;
}
else
{
root = q;
f=NULL;
while(q!=NULL)
{
f = q;
if(x < q ->data)
{
q = q->left;
}
else
{
q = q->right;
}
}
if(x < f->data)
{
f->left = p;
}
else
{
f->right = p;
}
}
return p;
}
VI - Tìm kiếm
Mã:
nodeptr search_node(nodeptr root , int x)
{
nodeptr p = root;
while(p!=NULL)
{
if(p->data == x) return p;
else if(x < p->data) p = p->left;
else p = p->right;
}
return NULL;
}
VII - Hàm hủy 1 nút của cây
Mã:
int del_node(nodeptr &root, int x)
{
nodeptr p, q, f;
p = root;
f = NULL;
while(p!=NULL)
{
if(p->data == x) break;
else
{
f = p;
if(x<p->data) p = p->left;
else p = p->right;
}
}
if(p==NULL) return 0;
else
{
if(p->left !=NULL && p->right!=NULL)
{
q = p->right;
f = p;
while(q->left!=NULL)
{
f = q;
q = q->left;
}
p->data = q->data;
p = q;
}
if(p->left!=NULL) q = p->left;
else q = p->right;
if(p==root) root = q;
else
{
if(p=f->left) f->left = q;
else f->right = q;
}
delete p;
return 1;
}
}
VIII - Hàm nhập dữ liệu vào cây
Mã:
void input_tree(nodeptr &root)
{
int n,x;
root = NULL;
printf("\nSo phan tu: ");
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
printf("Phan tu thu %d: ",i);
scanf("%d", &x);
insert_node(root, x);
}
}
IX - Duyệt cây
//Có 3 cách duyệt cây
//Cách 1 : Node - Left - Right (NLR)
/*trong đó: Node là nút gốc(root)
Left là nút bên trái của nút gốc
Right là nút bên phải của nút gốc */\
Mã:
void NLR(nodeptr root)
{
if(root!=NULL)
{
printf("%d", root->data);
NLR(root->left);
NLR(root->right);
}
}
//Cách 2: Left -Node -Right
Mã:
void LNR(nodeptr root)
{
if(root!=NULL)
{
LNR(root->left);
printf("%d", root->data);
LNR(root->right);
}
}
//Cách 3: Left - Right -Node
Mã:
void LRN(nodeptr root)
{
if(root!=NULL)
{
LNR(root->left);
printf("%d", root->data);
LNR(root->right);
}
}
XX- Hàm hủy cây
Mã:
void del_tree(nodeptr &root)
{
if(root!=NULL)
{
del_tree(root->left);
del_tree(root->right);
delete root;
root = NULL;
}
}