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 cài đặt theo phương pháp của CTU.
Code:
/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int TData;
//Cau truc cua Node
typedef struct TNode{
TData Data;
TNode*Left;
TNode*Right;
};
//Cau truc cay
typedef TNode * TTree;
//Khoi tao cay rong
void MakeNullTree(TTree *T)
{
(*T) = NULL;
}
//Xac dinh con trai
TTree LeftChild(TTree n)
{
if (n!=NULL)
return n->Left;
else
return NULL;
}
//Xac dinh con phai
TTree RightChild(TTree n)
{
if (n!=NULL)
return n->Right;
else return NULL;
}
//Duyet tien to
void PreOrder(TTree T)
{
printf("%d ",T->Data);
if (LeftChild(T)!=NULL)
PreOrder(LeftChild(T));
if(RightChild(T)!=NULL)
PreOrder(RightChild(T));
}
//Duyet trung to
void InOrder(TTree T)
{
if(LeftChild(T)!=NULL)
InOrder(LeftChild(T));
printf("%d ",T->Data);
if(RightChild(T)!=NULL)
InOrder(RightChild(T));
}
//Duyet hau to
void PosOrder(TTree T)
{
if(LeftChild(T)!=NULL)
PosOrder(LeftChild(T));
if(RightChild(T)!=NULL)
PosOrder(RightChild(T));
printf("%d ",T->Data);
}
//Thu tuc them 1 khoa vao cay tim kiem nhi phan
void InsertNode(TTree *Root,TData x)
{
if (*Root == NULL){ /* them nut moi chua khoa x */
(*Root)=(TNode*)malloc(sizeof(TNode));
(*Root)->Data = x;
(*Root)->Left = NULL;
(*Root)->Right = NULL;
}
else
if (x < (*Root)->Data)
InsertNode(&(*Root)->Left,x);
else
if (x>(*Root)->Data)
InsertNode(&(*Root)->Right,x);
}
//Nhap cac Node vao cay
void Tree(TTree*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)
InsertNode(&*k,x);
} while(x != 0);
}
//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
int Search(TTree Root,TData x){
if (Root == NULL)
return 0; //khong tim thay khoa x
else
if (Root->Data == x) /* tim thay khoa x */
return 1;
else
if (Root->Data < x) //tim thay tren cay nhi phan
return Search(Root->Right,x); //tim ben phai
else
return Search(Root->Left,x); //tim ben trai
}
//Chuong trinh chinh
void main() {
TTree T; //Khoi tao cay ban day
int n;
MakeNullTree(&T);
clrscr();
Tree(&T);
printf("\nGia tri cua cay khi duyet NLR.\n");
PreOrder(T);
printf("\nGia tri cua cay khi duyet LNR.\n");
InOrder(T);
printf("\nGia tri cua cay khi duyet LRN.\n");
PosOrder(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();
}