DSPS Practical :Threaded Binary Tree

#include <iostream>
using namespace std;
struct tbtnode
{ int data;
tbtnode *left,*right;
int lbit,rbit,flag;
};
class TBT
{ tbtnode *root;
tbtnode *presuc(tbtnode *t);
tbtnode *insuc(tbtnode *t);
tbtnode *postsuc(tbtnode *t);
tbtnode * father(tbtnode *t);
public:
TBT()
{ root=NULL;
}
void preorder();
void inorder();
void postorder();
void create();
};
int main()
{ TBT tbt;
int op;
do
{ cout<<"\n\n1)Create\n2)Preorder\n3)Inorder
\n4)Postorder\n5)Quit";
cout<<"\nEnter your choice : ";
cin>>op;
switch(op)
{ case 1: tbt.create();break;
case 2: tbt.preorder();break;
case 3: tbt.inorder();break;
case 4: tbt.postorder();break;
}
}while(op!=5);
return 0;
}
void TBT:: create()
{ tbtnode *b[31];
int x,i;
root=new tbtnode;
root->left=root->right=root;
root->lbit=1;root->rbit=0;
for(i=1;i<10;i++)
b[i]=NULL;
cout<<"\nPlease Enter data of root node(-1 for does not
exist): ";
cin>>x;
if(x==-1)
  return;
b[1]=new tbtnode;
b[1]->flag=0;
b[1]->data=x;
b[1]->lbit=root->lbit;
root->lbit=0;
root->left=b[1];
b[1]->rbit=1;
b[1]->right=root;
for(i=1;i<=5;i++)
if(b[i]!=NULL)
  { cout<<"\nEnter Left child of "<< b[i]->data<< " (-1 for does
not
exist): ";
cin>>x;
if(x!=-1)
{
b[2*i]=new tbtnode;
b[2*i]->flag=0;
b[2*i]->data=x;
b[2*i]->lbit=b[i]->lbit;
b[2*i]->left=b[i]->left;
b[i]->lbit=0;
b[i]->left=b[2*i];
b[2*i]->rbit=1;
b[2*i]->right=b[i];
}
cout<<"\nEnter Right child of "<< b[i]->data<< " (-1 for
does not
exist): ";
cin>>x;
if(x!=-1)
{b[2*i+1]=new tbtnode;
b[2*i+1]->flag=1;
b[2*i+1]->data=x;
b[2*i+1]->rbit=b[i]->rbit;
b[2*i+1]->right=b[i]->right;
b[i]->rbit=0;
b[i]->right=b[2*i+1];
b[2*i+1]->lbit=1;
b[2*i+1]->left=b[i];
}
}
}
tbtnode * TBT::presuc(tbtnode *t)
{ if(t->lbit==0)
return(t->left);
if(t->rbit==0)
  return(t->right);
while(t->rbit==1)
  t=t->right;
return(t->right);
}
void TBT::preorder()
{ tbtnode *t;
t=root->left;
cout <<"\n";
while(t!=root)
{ cout<<" "<<t->data;
t=presuc(t);
}
}
tbtnode * TBT::insuc(tbtnode *t)
{ if(t->rbit==0)
{ t=t->right;
while(t->lbit==0)
t=t->left;
return(t);
}
else
return(t->right);
}
void TBT::inorder()
{ tbtnode *t;
t=root->left;
cout<<"\n";
while(t->lbit==0)
t=t->left;
while(t!=root)
{cout<<" "<<t->data;
t=insuc(t);
}
}
tbtnode * TBT::postsuc(tbtnode *t)
{ if(t->flag==0)
{ t=father(t);
if(t->rbit==1)
return(t);
else
{ if(t==t->right)
return(t);
t=t->right;
while(t->lbit==0 || t->rbit==0)
if(t->lbit==0)
   t=t->left;
else
   t=t->right;
return(t);
}
}
else
return(father(t));
}
void TBT::postorder()
{ tbtnode *t;
t=root->left;
while(t->lbit==0 || t->rbit==0)
if(t->lbit==0)
t=t->left;
else
t=t->right;
while(t!=root)
{ cout<<" "<<t->data;
t=postsuc(t);
}
}
tbtnode * TBT::father(tbtnode *t)
{ if(t->flag==0)
{ while(t->rbit==0)
t=t->right;
return(t->right);
}
else
{while(t->lbit==0)
t=t->left;
return(t->left);
}
}
DSPS Practical :Threaded Binary Tree

RELATED POSTS
