//Cai dat cay nhi phan tim kiem

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <ctype.h>

#include <stdlib.h>

#include <assert.h>

#define true 1

#define false 0

struct node {int info;node *left,*right;};

void init(node* &);

int empty(node *);

void clear(node*&); //Xoa cay

node* makenode(int);//Tao nut la

void pretrav(node*); //Duyet cay theo thu tu truoc (de quy)

void intrav(node*); //Duyet cay theo thu tu giua (de quy)

void posttrav(node*); //Duyet cay theo thu tu sau (de quy)

node* search(node*,int);//Tim de quy va tra ve nut tim duoc

node* search2(node *&fp,int x);//Tim kiem khong dung de quy

void insert(node*&,int);//Chen nut moi bang de quy

void insert2(node* &,int);//Chen nut moi khong dung de quy

void remove(node*&,int);//Xoa nut co noi dung x

//==================================================

void init(node *&proot)

{proot=NULL;

};

//==================================================

//Dung phuong phap de quy de xoa cay co nut goc la proot

void clear(node* &proot)

{//Dieu kien dung

if(proot!=NULL)

{clear(proot->left);

clear(proot->right);

delete proot;proot=NULL;

}

};

//==================================================

int empty(node *proot)

{return proot==NULL;

}

//==================================================

//Tao mot nut la chua thong tin x

node* makenode(int x)

{node* p = new node;

p->info=x;

p->left=NULL;

p->right=NULL;

return p;

};

//==================================================

//Duyet cay theo thu tu truoc (NLR)

void pretrav(node* proot)

{if(proot!=NULL)

{printf("%5d",proot->info);

pretrav(proot->left);

pretrav(proot->right);

}

}

//==================================================

//Duyet cay theo thu tu giua (LNR)

void intrav(node* proot)

{if(proot!=NULL)

{intrav(proot->left);

printf("%5d",proot->info);

intrav(proot->right);

}

}

//==================================================

//Duyet cay theo thu tu sau (LRN)

void posttrav(node* proot)

{if(proot!=NULL)

{posttrav(proot->left);

posttrav(proot->right);

printf("%5d",proot->info);

}

}

//==================================================

//Dung phuong phap de quy de tim nut co noi dung x tren cay

node* search(node* proot,int x)

{//Dieu kien dung

node* p;

if(proot==NULL) return NULL;

if(proot->info==x) return proot;

//Buoc de quy

if(x<proot->info) p=search(proot->left,x);

else p=search(proot->right,x);

return p;

};

//==================================================

void insert(node* &proot,int x)

{if(proot==NULL) {proot=makenode(x); return;}

if(search(proot,x))

{cout<<endl<<"Nut da co, khong them duoc!";return;}

if(x<proot->info) insert(proot->left,x);

else insert(proot->right,x);

}

//==================================================

/* Tac vu insert2: them nut co noi dung x vao cay nhi phan tim kiem:

Them nut theo giai thuat binh thuong, nut them vao la nut la

duoc bo tri o vi tri phu hop tren cay*/

void insert2(node* &proot,int x)

{if(proot==NULL) {proot=makenode(x);return;}

if(search(proot,x)) {cout<<endl<<"Nut da co, khong them duoc!";return;}

node *fp, *p, *q; // fp la nut cha cua p, q la nut them vao

// Khoi dong cac gia tri

fp = NULL;

p = proot;

//tim nut fp, ya va fya, nut moi them vao la nut la con cua nut fp

while(p!=NULL)

{if(x<p->info)

{fp=p;p=p->left;} else {fp=p;p=p->right;}

} //end of while(p!=NULL)

/*Sau vong lap tren day thi nut p bi rong, con nut fp la nut can them

nut co noi dung x.*/

//Them nut q co noi dung x la con cua fp.

q = makenode(x);

if(x < fp->info) fp->left = q; else fp->right = q;

//Tao nut la moi co noi dung x

}

//==================================================

node* search2(node *proot,node *&fp,int x)

{node* p=proot;fp=NULL;

while(p!=NULL)

{if(x == p->info) return(p);// tim thay

if(x < p->info) {fp=p;p = p->left;}

else

{fp=p;p = p->right;}

}

return(NULL);// khong tim thay

}

//==================================================

/*Khi xoa mot nut P trong cay nhi phan tim kiem ta tim mot nut de thay the

nut do. Neu P la nut la thi nut thay the la nut NULL. Neu P chi co mot

cay con thi nut thay the la nut con cua no. Neu P co 2 cay con thi nut

thay the la nut trai nhat cua cay con ben phai hoac nut phai nhat cua

cay con ben trai.Ta quy uoc chon nut phai nhat cua cay con ben trai*/

void remove(node *&proot, int x)

{node *fp,*p,*f,*rp,*q; /*rp la nut thay the cho nut p co noi dung x,

f la nut cha cua nut thay the rp*/

p=search2(proot,fp,x); //fp la nut cha cua nut p

if(p==NULL) {cout<<"Khong tim thay nut x";return;}

//Nut la

if(p->right==NULL && p->left==NULL)

{if(p==proot) {delete proot;proot=NULL;return;}

if(fp->left==p) {fp->left=NULL;delete p;return;}

if(fp->right==p) {fp->right=NULL;delete p;return;}

};

//Nut chi co mot cay con trai

if(p->left!=NULL && p->right==NULL)

{if(fp->left==p) {fp->left=p->left;delete p;return;}

if(fp->right==p) {fp->right=p->left;delete p;return;}

}

//Nut chi co mot cay con phai

if(p->left==NULL && p->right!=NULL)

{if(fp->left==p) {fp->left=p->right;delete p;return;}

if(fp->right==p) {fp->right=p->right;delete p;return;}

};

//Nut p co 2 nut con

//Tim nut thay the, la nut phai nhat cua cay con trai

f=p;

rp=p->left;

while(rp->right!=NULL) {f=rp;rp=rp->right;}

f->right=rp->left;/*rp la phai nhat, do do khong co con phai

vi khong con rp nen nut cha phai chi den nut sau do*/

p->info=rp->info;

//doi noi dung cua p va rp, roi xoa rp

delete rp;

}

//==================================================

void main()

{clrscr();

int x,y;node* p, *proot,*fp;

while(true)

{clrscr();

//Tao menu

cout<<endl<<" 1.Khoi tao";

cout<<endl<<" 2.Them nut chua thong tin x";

cout<<endl<<" 3.Xoa nut co noi dung x";

cout<<endl<<" 4.Tim nut co noi dung x bang de quy";

cout<<endl<<" 5.Duyet cay theo thu tu truoc (NLR)";

cout<<endl<<" 6.Duyet cay theo thu tu giua (LNR)";

cout<<endl<<" 7.Duyet cay theo thu tu sau (LRN)";

cout<<endl<<" z. Ket thuc";

cout<<endl<<endl<<"Hay nhan phim tu 1 -> z de chon: ";

char chon=toupper(getch());

if(chon=='Z') break;

switch(chon)

{case '1':init(proot);break;

case '2':cout<<endl<<"Them nut co noi dung: ";cin>>x;

insert(proot,x);break;

case '3':cout<<endl<<"Xoa nut co noi dung la: ";cin>>x;

remove(proot,x);break;

case '4':cout<<endl<<"Tim nut co noi dung la: ";cin>>x;

p=search(proot,x);if(p!=NULL)

{cout<<endl<<"Nut tim thay co noi dung la: ";cout<<p->info;}

else cout<<"Khong tim thay ";break;

case '5':if(!empty(proot)) {cout<<endl<<"Nut goc la: ";cout<<proot->info<<endl;}

pretrav(proot);break;

case '6':if(!empty(proot)) {cout<<endl<<"Nut goc la: ";cout<<proot->info<<endl;}

intrav(proot);break;

case '7':if(!empty(proot)) {cout<<endl<<"Nut goc la: ";cout<<proot->info<<endl;}

posttrav(proot);break;

}

cout<<endl<<endl<<"Nhan phim bat ky de tiep tuc";

getch();

}

}