PROGRAM BST
#include <iostream>
#include <conio>
class tree
{
public:
int value;
tree *left;
tree *right;
tree *parent;
tree(int v)
{
value=v;
left=NULL;
right=NULL;
}
tree()
{
}
};
tree *root;
class BST
{
public:
BST()
{
root=NULL;
}
void cekroot();
int isempty();
void insert(int i);
void searching(int i);
void deletion(int i);
void findmin();
void findmax();
void urut();
void display(tree *val, int i);
private:
void insertx(int i, tree *temp);
void uruttree(tree *n);
void transplanted(tree *del, tree *reply);
void minvalue(tree *n);
};
int BST::isempty()
{
if(root==NULL)
return 1;
else
return 0;
}
void BST::findmin()
{
tree *temp;
temp=root;
if(isempty()==1)
{
cout<<"No Data"<<endl;
}else
{
while((temp->left!=NULL))
{
temp=temp->left;
}
cout<<"Nilai terkecil adalah :"<<temp->value<<endl;
cout<<endl;
}
}
void BST::findmax()
{
tree *temp;
temp=root;
if(isempty()==1)
{
cout<<"No Data"<<endl;
}else
{
while(temp->right!=NULL)
{
temp=temp->right;
}
cout<<"Nilai terbesar adalah :"<<temp->value<<endl;
cout<<endl;
}
}
void BST::searching(int i)
{
tree *temp;
temp=root;
int n=0;
while(temp!=NULL)
{
if(temp->value==i)
{
n=1;
break;
}
if(i<(temp->value))
{
temp=temp->left;
}else
{
temp=temp->right;
}
}
if(n==1)
cout<<"data ditemukan"<<endl;
else
cout<<"data tidak ditemukan"<<endl;
}
void BST::urut()
{
tree *temp;
temp=root; //// penugasan variabel temp sebagai root.
uruttree(temp); /// pemanggilan fungsi utama untuk pengurutan.
}
void BST::uruttree(tree *temp)
{
if(temp!=NULL)
{
uruttree(temp->left);
cout<<"value :"<<temp->value<<endl;
uruttree(temp->right);
}
}
void BST::insert(int i)
{
tree *temp=new tree();
temp=root;
if(root==NULL)
{
root=new tree(i);
cout<<"nilai "<<i<<" menjadi root"<<endl;
}else
{
insertx(i,temp);
}
}
void BST::insertx(int i,tree *temp)
{
tree *kiri=new tree();
tree *kanan=new tree();
if(i<=(temp->value))
{
kiri=temp;
if(kiri->left!=NULL)
{
insertx(i,kiri->left);
}else
{
kiri->left=new tree(i);
cout<<"nilai "<<i<<" masuk ke sebelah kiri "<<(kiri->value)<<endl;
kiri->left->left=NULL;
kiri->left->right=NULL;
}
}else
{
kanan=temp;
if(kanan->right!=NULL)
{
insertx(i,kanan->right);
}else
{
kanan->right=new tree(i);
cout<<"nilai "<<i<<" masuk ke sebelah kanan "<<(kanan->value)<<endl;
kanan->right->left=NULL;
kanan->right->right=NULL;
}
}
}
void BST::transplanted(tree *del, tree *reply)
{
if(del->parent==NULL)
{
root=reply;
}else if(del==del->parent->left)
{
del->parent->left=reply;
}else
{
del->parent->right=reply;
}
if(reply!=NULL)
{
reply->parent=del->parent;
}
}
void BST::minvalue(tree *temp)
{
while(temp->left!=NULL)
{
temp=temp->left;
}
//temp;
}
void BST::deletion(int i)
{
tree *y=NULL;
tree *x;
x=root;
while((x!=NULL)&&(x->value!=i))
{
y=x;
if(i<x->value)
{
x=x->left;
}else
{
x=x->right;
}
}
if(x==NULL)
{
cout<<"Nilai yang akan dihapus tidak ditemukan "<<endl;
}else
{
x->parent=y;
if(x->left==NULL)
{
transplanted(x,x->right); /// case 2
}else if(x->right==NULL)
{
transplanted(x,x->left); /// case 3
}else
{
tree *min=x->right;
min->parent=x;
tree *coba;
while(min->left!=NULL)
{
coba=min;
min=min->left;
}
tree *temp=min;
temp->parent=coba;
if(x->right!=min)
{
transplanted(min,min->right); /// case 4.b
temp->right=x->right;
temp->right->parent=temp;
}
transplanted(x,temp); /// case 4.a
temp->left=x->left;
temp->left->parent=temp;
}
}
}
void BST::display(tree *disp,int i)
{
int k;
if(disp !=NULL)
{
display(disp->right,i+1);
cout<<endl;
if(disp==root)
cout<<"root->: ";
else
{
for(k=0;k<i;k++)
cout<<" ";
}
cout<<disp->value;
display(disp->left, i+1);
}
}
void main()
{
BST *st;
st=new BST();
int n;
char pilih;
cout<<"Operasi BST "<<endl;
cout<<"1. Input data"<<endl;
cout<<"2. cari data"<<endl;
cout<<"3. nilai terkecil"<<endl;
cout<<"4. nilai terbesar"<<endl;
cout<<"5. Urut Tree"<<endl;
cout<<"6. Hapus Node"<<endl;
cout<<"7. Display"<<endl;
cout<<"8. Exit"<<endl;
do{
cout<<"Pilihan :";
cin>>pilih;
switch(pilih){
case '1':
cout<<"Masukkan angka :";
cin>>n;
st->insert(n);
break;
case '2':
cout<<"Masukkan angka :";
cin>>n;
st->searching(n);
break;
case '3':
st->findmin();
break;
case '4':
st->findmax();
break;
case '5':
st->urut();
break;
case '6':
cout<<"Masukkan angka :";
cin>>n;
st->deletion(n);
break;
case '7':
cout<<"Display BST :"<<endl;
st->display(root,1);
cout<<endl;
break;
default:
cout<<"salah pilih atau keluar";
break;
}
} while(pilih!='8');
getch();
}
