Monday 16 January 2012

How to create binary tree

#include<iostream>
#include<stdio.h>
#include<time.h>
#include<iomanip>
#include<conio.h>
#define dimension 11
using namespace std;

struct tree{
 int value;
 tree *leftptr;
 tree *rightptr;
};
typedef tree Tree;
typedef Tree *treePtr;
void create(treePtr *,int);
void silme(treePtr *);
void remove(treePtr);
void inorder(treePtr);
void postorder(treePtr);
void preorder(treePtr);
void go_array(treePtr,int[],int *);
void main(){
 srand(time(NULL));
 int val,i,key;  //val means value, i means counter , key is keyboard input
 int counter=0;
 int arrayx[dimension]={0};
 treePtr root = NULL;
 for(i=0;i<11;i++){

  val = rand()%999+1;
  create(&root,val);
 }

 go_array(root,arrayx,&counter);
 cout << "inorder scanning..." << endl;
 inorder(root);
 cout <<endl<<"Preorder scanning..."<<endl;
 preorder(root);
 cout <<endl<<"Postorder scanning..."<<endl;
 postorder(root);
 cout<<endl;
 cout << "Array : "<<endl;
 for(i=0;i<11;i++)
  cout <<arrayx[i] <<"  ";
 cout<<endl;
 cout <<"Sayac = "<<counter<<endl;
 cout <<endl<< "Press 1 to delete a node from to tree or 0 to pass and exit : ";
 cin.ignore(0,'\n');
 cin>>key;
 cout << key<<endl;
 if(key==1)
 remove(root);
 inorder(root);
 getch();
}
void create(treePtr *proot,int qvalue){
 treePtr tara,yeni;
 yeni = new Tree;
 tara = *proot;
 yeni->value=qvalue;
 yeni->leftptr = NULL;
 yeni->rightptr = NULL;
 bool bulundu = false;
 if((*proot)==NULL){//ilk düğüm ekleniyor
  *proot = yeni;
 }
 while(tara!=NULL && bulundu!=true){
  if(qvalue<tara->value){
   if(tara->leftptr!=NULL)
    tara=tara->leftptr;
   else{
    tara->leftptr = yeni;
    bulundu = true;
   }     
  }
  else if(qvalue>tara->value){
    if(tara->rightptr!=NULL)
     tara=tara->rightptr;
    else{
     tara->rightptr = yeni;
     bulundu = true;
    }
  }
  else 
   break;
 }
}
void inorder(treePtr p){
 if(p){
  inorder(p->leftptr);
  cout << p->value <<"  ";
  inorder(p->rightptr);
 }
}
void postorder(treePtr p){
 if(p){
  inorder(p->leftptr);
  inorder(p->rightptr);
  cout << p->value <<"  ";
  
 }
}
void preorder(treePtr p){
 if(p){
  cout << p->value <<"  ";
  inorder(p->leftptr);
  inorder(p->rightptr);
 }
}
void go_array(treePtr p,int q[dimension],int *s){

 if(p){
  
  go_array(p->leftptr,q,s);
  q[*s]=p->value;
  (*s)++;
  go_array(p->rightptr,q,s);
  
  
 }
}
void remove(treePtr p){
 
 int sil;
 cout << "NE SILMEK ISTIYORSUN : ";
 cin.ignore(2,'\n');
 cin >> sil;
 char yon;
 treePtr tara,ust;
 tara = p;
 bool var = false;
 while(tara && var!=true){
  if(sil<tara->value){
    ust=tara;
    yon = 'l';
    tara=tara->leftptr;
  }else if(sil>tara->value){
    ust=tara;
    yon = 'r';
    tara=tara->rightptr;
  }else
   var = true;
 }
 if(var==true){
  if(yon=='l')
   silme(&(ust->leftptr));
  else if(yon=='r')
   silme(&(ust->rightptr));
  else 
   silme(&p);
 }
 else
  cout << "HATA" <<endl;

}
void silme(treePtr *s){
 treePtr r,q;
 r=*s;
 if(r==NULL)
  return;
 else if(r->rightptr==NULL){
  *s=r->leftptr;
  delete r;
 }
 else if(r->leftptr==NULL){
  *s=r->rightptr;
  delete r;
 }
 else {
  for(q=r->rightptr;q->leftptr;q=q->leftptr);
  q=r->leftptr;
  *s=r->rightptr;
  delete r;
 }

}

No comments:

Post a Comment