Bai tap cay ne cac ban oi.Lam xong het phan cay luon do nha

huynhthao.hc11th2a 24/3/2012, 13:24

#include
using namespace std;
struct Node
{
int key;
Node * left;
Node * right;
Node * p;
};
struct Tree
{
Node * root;
};
void khoitao(Tree & T)
{
T.root=NULL;
}
void Tree_insert(Tree & T,Node * z)
{
Node * y=NULL;
Node * x=T.root;
while(x!=NULL)
{
y=x;
if(z->key < x->key)
x=x->left;
else
x=x->right;
z->p=y;
}
if(y==NULL)
T.root=z;
else if(z->keykey)
y->left=z;
else y->right=z;
}
void NLR(Node *T)
{
if(T!=NULL)
{
cout<key<<"\t";
NLR(T->left);
NLR(T->right);

}
}
void duyetNLR(Tree T)
{
NLR(T.root);
}
Node * Tree_search(Node * x,int k)
{
if(x==NULL ||k==x->key)
return x;
if(kkey)
return Tree_search(x->left,k);
else return Tree_search(x->right,k);
}
//tim ptu nho nhat
Node * Tree_minimun(Node * x)
{
while(x->left!=NULL)
x=x->left;
return x;
}
//tim phan tu lon nhat
Node * Tree_maximun(Node * x)
{
while(x->right!=NULL)
x=x->right;
return x;
}
//tim phan tu di sau 1 phan tu
Node * Tree_successor(Node *x)
{
if(x->right!=NULL)
return Tree_minimun(x->right);
Node * y=x->p;
while(y!=NULL && x==y->right)
{
x=y;
y=y->right;
}
return y;
}
//Tim ptu the mang
void Transplant(Tree &T,Node *u,Node *v)
{
if(u->p==NULL)
T.root=v;
else if(u==u->p->left)
u->p->left=v;
else
u->p->right=v;
if(v!=NULL)
v->p=u->p;
}
//Xoa phan tu can xoa
void Tree_delete(Tree &T, Node *z)
{
if(z->left==NULL)
Transplant(T,z,z->right);
else if(z->right==NULL)
Transplant(T,z,z->left);
else
{
Node * y=Tree_minimun(z->right);
if(y->p!=z)
{
Transplant(T,y,y->right);
y->right=z->right;
y->right->p=y;
}
Transplant(T,z,y);
y->left=z->left;
y->left->p=y;

}
}
//ham main
void main()
{

Tree T;
khoitao(T);
int n;
cout<<"Nhap so luong nut cho cay: ";
cin>>n;
cout<cout<<"Nhap cay "<cout<for(int i=1;i<=n;i++)
{
cout<<"nhap gia tri thu "< Node*x=new Node;
cin>> x->key;
x->left=NULL;
x->right=NULL;
Tree_insert(T,x);
}
//DUYET CAY THEO NLR
cout<<"Duyet cay theo NLR";
cout<duyetNLR(T);
cout<//Tim cay
cout<<"Tim k:";
int k;
cin>>k;
Node*j=Tree_search(T.root,k);
if(j!=NULL)
{
cout<<"Tim thay k = ";
cout<key<}
else cout<<"K tim thay"<//tim phan tu nho nhat
cout <<"Tim phan tu nho nhat la ";
Node * z=Tree_minimun(T.root);
cout <key<//tim phan tu lon nhat
cout <<"Tim phan tu nho nhat la ";
Node * l=Tree_maximun(T.root);
cout <key<//Tim phan tu di sau pt
cout<<"Tree_successor la ";
Node * e=Tree_successor(T.root);
cout<key<//xoa phan tu;
cout<<"nhap ptu can xoa la ";
int f;
cin>>f;
cout<Node* w=Tree_search(T.root,f);
if(w!=NULL)
{
cout<<"Tim thay"< cout<<"Delete"<key< Tree_delete(T,w);
duyetNLR(T);
cout<}
}[code]