Binary Search Ttree

chipid1989 Thu May 12, 2011 11:33 pm

#include
#include
#include
#include
#include
//*-------Khai bao cay tim kiem nhi phan----------*
typedef struct Node
{
Node* left;
Node* right;
int data;
};
typedef Node* TTree;
char s[10];
//*--------Tao cay nhi phan rong---------*
void MakeNull_Tree(TTree *T)
{
(*T)=NULL;
}
//*--------Kiem tra cay rong-------------*
int EmptyTree(TTree T)
{
return T==NULL;
}
//*--------Xac dinh con trai-------------*
TTree LeftChild(TTree T)
{
if(T!=NULL)
return T->left;
else return NULL;
}
//*--------Xac dinh con phai------------*
TTree RightChild(TTree T)
{
if(T!=NULL)
return T->right;
else return NULL;
}
//*--------Xax dinh nut la-------------*
int isLeaf(TTree T)
{
if((T!=NULL)&&(T->left==NULL)&&(T->right==NULL))
return 1;
else return 0;
}
//*---------Diem so nut cua cay--------*
int Nb_Node(TTree T)
{
if(T==NULL)
return 0;
else return (Nb_Node(T->left)+ Nb_Node(T->right)+1);
}
//*---------Diem so nut la cua cay-------*
int Nb_Leaf(TTree T)
{
if(T==NULL)
return 0;
else if(isLeaf(T)) return 1;
else return Nb_Leaf(T->left)+Nb_Leaf(T->right);
}
//*----------Duyet cay tim kiem nhi phan-------*
//*--------Duyet tien tu---------*
void NLR(TTree T)
{
if(!EmptyTree(T))
{

printf(" %d",T->data);
NLR(T->left);
NLR(T->right);
}
}
//*---------Duyet trung tu--------*
void LNR(TTree T)
{
if(!EmptyTree(T))
{
LNR(T->left);
printf(" %d",T->data);
LNR(T->right);
}
}
//*---------Duyet hau tu--------*
void LRN(TTree T)
{
if(!EmptyTree(T))
{
LNR(T->left);
LNR(T->right);
printf(" %d",T->data);
}
}
int InsertTree(TTree *T,int x){
if((*T)!=NULL){
if((*T)->data==x) printf("Da ton tai khoa X");
if((*T)->data>x) InsertTree(&(*T)->left,x);
else InsertTree(&(*T)->right,x);}
else if((*T)==NULL){
(*T) = (Node*)malloc(sizeof(Node));
(*T)->data = x;
(*T)->left = NULL;
(*T)->right = NULL;}
}

int getDepth(TTree T){
if(T==NULL)return 0;
int l=getDepth(T->left),r=getDepth(T->right);
return l>r?l+1:r+1;
}
int random(int num){
return (int)(((long)rand()*num)/(RAND_MAX+1));
}
void randomize(){
srand(time(NULL));
}

void autoCreateTree(TTree *T){
randomize();
for(int i=0;i<10;i++)
while(InsertTree(T,random(100))!=1);
}

void drawNode(TTree *T,int x,int y,int dx){
if((*T)==NULL) ;
printf("Cay rong");
else if((*T)!=NULL){
sprintf(s,"%d",(*T)->data);
outtextxy(x,y,s);
int dy=30;
if((*T)->left){
line(x,y,x-dx,y+dy);
drawNode(&(*T)->left,x-dx,y+dy,dx/2);
}
if((*T)->right){
line(x,y,x+dx,y+dy);
drawNode(&(*T)->right,x+dx,y+dy,dx/2);
}}
}
void drawTree(TTree *T){
clearviewport();
setviewport(0,0,getmaxx(),getmaxy()-150,1);
int xroot=getmaxx()/2;
int yroot=10;
int dx=getDepth(*T)*20;

settextjustify(CENTER_TEXT,CENTER_TEXT);
drawNode(T,xroot,yroot,dx);
}
/*--------------------Ham nhap cay------------------------------*/
void ReadTree(TTree *T)
{
int i,x,n=0;
do{
moveto(1,26);
printf("\nNhap vao so nut: ");
fflush(stdin); scanf("%d",&n);
}while(n==0);
printf("\nNhap vao nut goc:");
fflush(stdin); scanf("%d",&x);
InsertTree(X,T);
drawTree(T);
for(i=1;iprintf("\nNhap vao nut thu %d: ",i);
fflush(stdin);scanf("%d",&X);
InsertNode(X,T);
drawTree(T);
}
}
void manualCreateTree(TTree *T){
int x;
printf("Nhap gia tri cac phan tu cua cay, nhap gia tri 0 de thoat !\n");
do{
moveto(1,26);//chuyen con tro toi toa do 1,26
printf("Nhap x = ");// \b-phim lui
fflush(stdin);
scanf("%d",&x);
if(x){
InsertTree(T,x);
drawTree(T);
}
while(x!=0);
}
int main(){
int mh=0,mode;
int x,y;
TTree T;
initgraph(&mh,&mode,"c:\\tc\\bgi");
autoCreateTree(&T);
// drawTree(&T);
// ReadTree(&T);
manualCreateTree(&T);
getch();
closegraph();
}