Bintree

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>

 

class node{
private:
int data;
node *left;
node *right;
public:
friend class bintree;
node(){
data=0;
left=NULL;
right=NULL;
}

 

};

 

class bintree{
private:
node *root;
node *currnode;

void intrav(node *);
void pretrav(node *);
void posttrav(node *);
void freetree(node *);
public:
bintree(){ //constructor
root=NULL;
currnode=NULL;
}
~bintree();//destructor
void maketree(void){
root=new node;
cout<<"Enter data for the root node.\n";
cin>>root->data;
root->left=NULL;
root->right=NULL;
currnode=root;
}
void setleft(void);
void setright(void);
void trav(void);
void tracetree(void);
void display(void);

};

 

// ----function definitions-------------------------------------------

void bintree::setleft(void){
node *p1;
p1=new node;
cout<<"Enter the data for the left child of the present node...\n";
cin>>p1->data;
p1->left=NULL;
p1->right=NULL;
currnode->left=p1;
return;
}

 

void bintree::setright(void){
node *p1;
p1=new node;
cout<<"Enter the data for the right child of the present node...\n";
cin>>p1->data;
p1->left=NULL;
p1->right=NULL;
currnode->right=p1;
return;
}

 

void bintree::intrav(node* r){
if(r!=NULL){
intrav(r->left);
if(r==root)
textcolor(RED);
if(currnode==r)
textbackground(BLUE);
cprintf(" %d ",r->data);
textbackground(BLACK);
textcolor(WHITE);
cout<<" ";
intrav(r->right);
}
return ;
}

 

void bintree::pretrav(node *r){
if(r!=NULL){
if(r==root)
textcolor(RED);
if(currnode==r)
textbackground(BLUE);
cprintf(" %d ",r->data);
textbackground(BLACK);
textcolor(WHITE);
cout<<" ";
pretrav(r->left);
pretrav(r->right);
}

return;
}

 

void bintree::posttrav(node *r){
if(r!=NULL){
posttrav(r->left);
posttrav(r->right);
if(r==root)
textcolor(RED);
if(currnode==r)
textbackground(BLUE);
cprintf(" %d ",r->data);
textbackground(BLACK);
textcolor(WHITE);
cout<<" ";
}
return;
}

 

 

void bintree::tracetree(void){
int ans=1;

while(ans!=0){
clrscr();
cout<<"\tTRACING THE TREE\n\n\n";
display();

cout<<"\n\n\n\n\tMENU\n";
cout<<"0...Finished.Return to main menu.\n";
cout<<"1...move to left child\n";
cout<<"2...move to right child\n";
cout<<"3...move to the root\n";
cout<<"4...add a left child to the current node\n";
cout<<"5...add a right child to the current node\n";

cout<<"\n\tEnter choice...";
cin>>ans;
switch(ans){
case 0:
cout<<"\tExiting to main menu...\n";
break;
case 1:
if(currnode->left!=NULL)
currnode=currnode->left;
else{
cout<<"No left child.Press any key to try again.\n";
getch();
}
break;
case 2:
if(currnode->right!=NULL)
currnode=currnode->right;
else{
cout<<"No right child.Press any key to try again.\n";
getch();
}
break;
case 3:
currnode=root;
break;
case 4:
setleft();
break;
case 5:
setright();
break;
default:
cout<<"Erroneous entry.Press any key to try again.\n";
getch();
}

}
}

 

void bintree::trav(void){
int ans=1;
node *pn;
clrscr();
while(1){
cout<<"\n\n MENU\n";
cout<<"1....traverse from the current node.\n";
cout<<"2....traverse from the Root node.\n";
cout<<"\n\t Enter choice...";
cin>>ans;
switch (ans){
case 1:
pn=currnode;
ans=-1;
break;
case 2:
pn=root;
ans=-1;
break;
default:
cout<<"Erroneous entry .Retry.\n";
ans=1;
break;
}
if(ans==-1)
break;
}

ans=1;
while(ans!=0){
clrscr();
cout<<"\n\n MENU\n";
cout<<"0...exit to main menu.\n";
cout<<"1...inorder traversal\n";
cout<<"2...postorder traversal\n";
cout<<"3...preorder traversal\n";
cout<<"\n(The RED node is the Root node.\n"
<<" The BLUE node is the current node.)\n";
cout<<"\n\tEnter choice...";
cin>>ans;
switch(ans){
case 0:
cout<<"\treturning to main menu.\n";
break;
case 1:
cout<<"Inorder traversal...\n";
intrav(pn);
break;
case 2:
cout<<"Postorder traversal...\n";
posttrav(pn);
break;
case 3:
cout<<"Preorder traversal...\n";
pretrav(pn);
break;
default:
cout<<"Erroneous entry.Retry.\n";
break;
}
if(ans!=0){
cout<<"\n\n\tPress any key ...\n";
getch();
}
}
return;

}

 

void bintree::freetree (node *r){
if(r!=NULL){
freetree(r->left);
freetree(r->right);
delete r;
cout<<"freed,";
}
}

 

 

bintree::~bintree(void){
freetree(root);
cout<<"tree freed.\n";
return;
}

 

void bintree::display(void){
node* stack[40];
int i,top=-1,ndent[40];
int tabcnt=0,flag=1,dir=0;

node *p,*q,*r;
p=root;

 

clrscr();
cout<<"Printing the binary tree...\n";
cout<<" (RED....rootnode.\n";
cout<<" BLUE...current node.)\n\n\n\n";
while(p!=NULL){
for(i=1;i<=tabcnt;i++)
cout<<" ";
if(p==root)
textcolor(RED);

if(p==currnode)
textbackground(BLUE);
cprintf("%d ",p->data);
textcolor(WHITE);
textbackground(BLACK);
switch(dir){
case 0:
cout<<"rt\n";
break;
case 1:
cout<<"L\n";
break;
case 2:
cout<<"R\n";
break;
}

q=p->left;
r=p->right;
if(q!=NULL){
stack[++top]=p;
p=p->left;
ndent[top]=tabcnt;
tabcnt++;
dir=1;
}
else
if(r!=NULL){
tabcnt++;
p=p->right;
dir=2;
}
else{//left=right=null...
while(p->right==NULL){
if(top==-1){
flag=0;
break;
}
p=stack[top];
tabcnt=ndent[top];
top--;
}
if(flag==1){
p=p->right;
tabcnt++;
dir=2;
}
else
break;
}

}
}

 

 

 

 

 

 

 

 

 

//=========================================================================

 

 

 

int main (void){
bintree tr;
int ans=1;

while (ans!=0){
clrscr();
textcolor(WHITE);
cout<<"\n\n\tMAIN MENU\n";
cout<<"0....Exit\n";
cout<<"1....Maketree\n";
cout<<"2....Set the node pointer to a node in the tree\n";
cout<<"3....Set a node left to the current node\n";
cout<<"4....Set a node to the right of the current node\n";
cout<<"5....Traverse the tree (inorder,postorder or preorder)\n";
cout<<"6....Print the tree on screen\n";
cout<<"\n\tEnter choice...\n\n";
cin>>ans;
switch(ans){
case 0:
cout<<"Exiting program...\n";
break;
case 1:
tr.maketree();
cout<<"\n\tTree created...";
break;
case 2:
tr.tracetree();
break;
case 3:
tr.setleft();
break;
case 4:
tr.setright();
break;
case 5:
tr.trav();
break;
case 6:
tr.display();
break;

default:
cout<<"Wrong choice entered.Try again.\n";
break;
}
cout<<"\n\n\tPress any key to continue...\n";
getch();
}
return 0;
}

 

 

/*
void display(node *r){
int blk=0;
node *p,*hold;
struct stack s;
s.top=-1;
p=r;
hold=r;

do{
while(p!=NULL){
blk=blk+5*(ndent(r,p,hold));
blanks(blk);
printf("%d\n",p->k);
push(&s,p);
hold=p;
p=p->left;
if(p==NULL){
blanks(blk+5);
printf("nl\n");
}
}
if(s.top!=-1){
p=pop(&s);
p=p->right;
if(p==NULL){
blanks(blk+5);
printf("nr\n");
}
}
}while(s.top!=-1 || p!=NULL);
blanks(blk+5);
printf("_e_\n");
return;
}

*/