CÂY TÌM KIẾM NHỊ PHÂN
1. Định nghĩa
Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút cây lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải.
Lưu ý: dữ liệu lưu trữ tại mỗi nút có thể rất phức tạp như là một record chẳng hạn, trong trường hợp này khoá của nút được tính dựa trên một trường nào đó, ta gọi là trường khoá. Trường khoá phải chứa các giá trị có thể so sánh được, tức là nó phải lấy giá trị từ một tập hợp có thứ tự.
Qui ước: Cũng như tất cả các cấu trúc khác, ta coi cây rỗng là cây TKNP
Nhận xét:
- Trên cây TKNP không có hai nút cùng khoá.
- Cây con của một cây TKNP là cây TKNP.
2. Duyệt cây nhị phân
Ta có thể áp dụng các phép duyệt cây tổng quát để duyệt cây nhị phân. Tuy nhiên vì cây nhị phân là cấu trúc cây đặc biệt nên các phép duyệt cây nhị phân cũng đơn giản hơn. Có ba cách duyệt cây nhị phân thường dùng (xem kết hợp với hình III.13):
- Duyệt tiền tự (Node-Left-Right): duyệt nút gốc, duyệt tiền tự con trái rồi duyệt tiền tự con phải.
- Duyệt trung tự (Left-Node-Right): duyệt trung tự con trái rồi đến nút gốc sau đó là duyệt trung tự con phải.
- Duyệt hậu tự (Left-Right-Node): duyệt hậu tự con trái rồi duyệt hậu tự con phải sau đó là nút gốc.
3. Tìm kiếm một nút có khóa cho trước trên cây TKNP
Để tìm kiếm 1 nút có khoá x trên cây TKNP, ta tiến hành từ nút gốc bằng cách so sánh khoá của nút gốc với khoá x.
- Nếu nút gốc bằng NULL thì không có khoá x trên cây.
- Nếu x bằng khoá của nút gốc thì giải thuật dừng và ta đã tìm được nút chứa khoá x.
- Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên phải.
- Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên trái.
4. Cài đặt
Có nhiều cách cài đặt theo dữ liệu có cấu trúc, tùy vào sở thích và quan điểm của từng người về danh sách có đầu hoặc không đầu. Sau đây là chương trình rất đơn giản và dễ hiểu:
Code:
/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"
//Cau truc cua Node
typedef struct Node{
int info;
Node*Left;
Node*Right;
}Node;
//Khoi tao Node
Node*MakeNode(int x) {
Node*p = new Node;
p ->info = x;
p ->Left = NULL;
p ->Right = NULL;
return p;
}
//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Node**k,Node*p) {
if (p->info < (*k)->info ) {
if((*k)->Left)
InsertNode(&(*k)->Left,p);
else
(*k)->Left = p;
}
else
if (p->info > (*k)->info){
if((*k)->Right)
InsertNode(&(*k)->Right,p);
else
(*k)->Right = p;
}
}
//Thu tuc them node cho cay ban dau
void PushNode(Node**k,int x) {
Node*p = MakeNode(x);
if (*k == NULL)
*k = p;
else
InsertNode(&*k,p);
}
//Nhap cac Node vao cay
void Tree(Node**k) {
int x;
printf("Nhap vao cac phan tu trong cay nhi phan tim kiem.\n");
printf("Nhap so 0 thi ket thuc:");
do {
scanf("%d",&x);
if (x != 0)
PushNode(&*k,x);
} while(x != 0);
}
//Duyet tien to
void NLR(Node* k) {
if(k != NULL) {
printf("%4d",k->info);
NLR(k->Left);
NLR(k->Right);
}
}
//Duyet trung to
void LNR(Node* k) {
if(k != NULL) {
LNR(k->Left);
printf("%4d",k->info);
LNR(k->Right);
}
}
//Duyet hau to
void LRN(Node* k) {
if(k != NULL) {
LRN(k->Left);
LRN(k->Right);
printf("%4d",k->info);
}
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Node*k,int x) {
Node*temp = k;
while (temp != NULL ) {
if (temp -> info == x)
return 1;
else
{
if (temp -> info > x)
temp = temp -> Left;
else
temp = temp -> Right;
}
}
return 0;
}
//Chuong trinh chinh
void main() {
Node* T = NULL; //Khoi tao cay ban day
int n;
clrscr();
Tree(&T);
printf("\nGia tri cua cay khi duyet NLR.\n");
NLR(T);
printf("\nGia tri cua cay khi duyet LNR.\n");
LNR(T);
printf("\nGia tri cua cay khi duyet LRN.\n");
LRN(T);
printf("\nBan muon tim phan tu gi trong cay? ");
scanf("%d",&n);
if ( Search(T,n) == 0 )
printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
else
printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);
getch();
}Bạn có thể viết ngắn hơn:
Code:
/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"
//Cau truc cua Node
typedef struct Node{
int info;
Node*Left;
Node*Right;
}Node;
//Dinh nghia cay nhi phan
typedef Node * Tree;
//Khoi tao Node
Node *MakeNode(int x) {
Node*p = new Node;
p ->info = x;
p ->Left = NULL;
p ->Right = NULL;
return p;
}
//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Tree *k,Node*p) {
if (p->info < (*k)->info ) {
if((*k)->Left)
InsertNode(&(*k)->Left,p);
else
(*k)->Left = p;
}
else
if (p->info > (*k)->info){
if((*k)->Right)
InsertNode(&(*k)->Right,p);
else
(*k)->Right = p;
}
}
//Thu tuc them node cho cay ban dau
void PushNode(Tree *k,int x) {
Tree p = MakeNode(x);
if (*k == NULL)
*k = p;
else
InsertNode(&*k,p);
}
//Nhap cac Node vao cay
void InputTree(Tree *k) {
int x;
printf("Nhap vao cac phan tu trong cay nhi phan tim kiem.\n");
printf("Nhap so 0 thi ket thuc:");
do {
scanf("%d",&x);
if (x != 0)
PushNode(&*k,x);
} while(x != 0);
}
//Duyet tien to
void NLR(Tree k) {
if(k != NULL) {
printf("%4d",k->info);
NLR(k->Left);
NLR(k->Right);
}
}
//Duyet trung to
void LNR(Tree k) {
if(k != NULL) {
LNR(k->Left);
printf("%4d",k->info);
LNR(k->Right);
}
}
//Duyet hau to
void LRN(Tree k) {
if(k != NULL) {
LRN(k->Left);
LRN(k->Right);
printf("%4d",k->info);
}
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Tree k,int x) {
Tree temp = k;
while (temp != NULL ) {
if (temp -> info == x)
return 1;
else
{
if (temp -> info > x)
temp = temp -> Left;
else
temp = temp -> Right;
}
}
return 0;
}
//Chuong trinh chinh
void main() {
Tree T = NULL; //Khoi tao cay ban day
int n;
clrscr();
InputTree(&T);
printf("\nGia tri cua cay khi duyet NLR.\n");
NLR(T);
printf("\nGia tri cua cay khi duyet LNR.\n");
LNR(T);
printf("\nGia tri cua cay khi duyet LRN.\n");
LRN(T);
printf("\nBan muon tim phan tu gi trong cay? ");
scanf("%d",&n);
if ( Search(T,n) == 0 )
printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
else
printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);
getch();
}Được sửa bởi Admin ngày Mon Apr 19, 2010 8:22 am; sửa lần 3.