CayBST
#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); */
}
Bạn đang đọc truyện trên: Truyen247.Pro