#include<iostream.h>

struct tree{

int info;

tree *left,*right;

};

int tim(int x, tree *root)

{

if(root==NULL) return 0;

else if(root->info==x) return 1;

else if(root->info<x) return tim(x,root->right);

else return tim(x,root->left);

}

void chen(int x, tree *&root)

{

if(root==NULL)

{

root=new tree;

root->info=x;

root->left=root->right=NULL;

}

else

if(root->info<x)

chen(x,root->right);

else

if(root->info>x)

chen(x,root->left);

else

cout<<x<<" da co trong cay"<<"

";

}

void taocay(tree *&root)

{ int n,x;

root=NULL;

cout<<"Nhap so node trong cay: ";cin>>n;

for(int i=1;i<=n;i++)

{

cout<<"Nhap gia tri "<<i<<" :";cin>>x;

if(tim(x,root))

{i--;

cout<<x<<" da co trong cay"<<"

";

}

else chen(x,root);

}

}

void trungtu(tree *root)

{

if(root!=NULL)

{

trungtu(root->left);

cout<<root->info<<"\t";

trungtu(root->right);

}

}

int max(int a,int b)

{

if(a>b) return a;

return b;

}

int chieucao(tree *root)

{

if(root==NULL) return 0;

else return 1+max(chieucao(root->left),chieucao(root->right));

}

void xoa(tree *&root, int x)

{

if(root!=NULL)

{

if(root->info>x) xoa(root->left,x);

else if(root->info<x) xoa(root->right,x);

else if(root->right==NULL&&root->left==NULL)

{

delete(root);

root=NULL;

}

else if(root->left==NULL)

{

tree *p=root;

root=p->right;

delete(p);

}

else

{

tree *p=root->left;

while(p->right!=NULL)

p=p->right;

root->info=p->info;

xoa(root->left,p->info);

}

}

else cout<<"Khong co x";

}

//Kiem tra cay BST

void trungtu1(tree *root, int m[30], int &n)

{

if(root!=NULL)

{

trungtu1(root->left,m,n);

cout<<root->info<<"\t";

m[++n]=root->info;

trungtu1(root->right,m,n);

}

}

int ktbst(int m[30],int n)

{

for(int i=1;i<n;i++)

if(m[i]>m[i+1]) return 0;

return 1;

}

void main()

{

int x,tx,h,kt;

tree *root;

taocay(root);

trungtu1(root,m,n);

cout<<endl;

kt=ktbst(m,n);

cout<<kt;

//h=chieucao(root);

// cout<<"chieu cao cua cay :"<<h<<"

";

//cout<<"Tim gia tri: ";cin>>x;

/* if(tim(x,root)==1)

cout<<x<<" co trong BST";

else cout<<x<<" khong co trong BST";

xoa(root,x);

cout<<endl;

trungtu(root); */

}