JABIR PATHAN: Create in-order threaded binary tree and perform traversals

/****************************************************

NAME :- Jabir Daud Pathan

PROGRAM :- Create in-order threaded binary tree and

perform traversals

*****************************************************/

/*---------------<< Header File >>------------------*/

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

struct node

{

int data;

node *lchild,*rchild;

int lbit,rbit,flag;

};

/*-------<< Declaration of TB-TREE Class >>--------*/

class tbtree

{

node *root;

node *presuc(node*t);

node *insuc(node*t);

node *postsuc(node*t);

node * father(node*t);

void tbtree::create1(node*,int);

public:

tbtree()

{

root=new node;

root->lbit=0;

root->rbit=1;

root->lchild=root->rchild=root;

}

void create();

void preorder();

void inorder();

void postorder();

};

/*-------<< Function Defination For create tbtree >>-------*/

void tbtree::create1(node *fatherof,int lchildorrchild)

{

node *p;

int x;

cout<<"\nEnter a data(-1 for no data) : ";

cin >> x;

if(x==-1)

return ;

p=new node;

p->data=x;

if(lchildorrchild==0)

{

p->flag=0;

p->lbit=fatherof->lbit;

p->lchild=fatherof->lchild;

fatherof->lchild=p;

fatherof->lbit=1;

p->rbit=0;

p->rchild=fatherof;

}

else

{

p->flag=1;

p->rbit=fatherof->rbit;

p->rchild=fatherof->rchild;

fatherof->rchild=p;

fatherof->rbit=1;

p->lbit=0;

p->lchild=fatherof;

}

cout<<"\nEnter lchild child of "<<x ;

create1(p,0);

cout<<"\nEnter rchild child of "<<x;

create1(p,1);

}

void tbtree:: create()

{

create1(root,0);

}

/*--<< Function defination for Preorder successor >>--*/

node * tbtree::presuc(node *t)

{

if(t->lbit==1)

return(t->lchild);

if(t->rbit==1)

return(t->rchild);

while(t->rbit==0)

t=t->rchild;

return(t->rchild);

}

/*--<< Function defination for Preorder Traversal >>--*/

void tbtree::preorder()

{

node *t;

t=root->lchild;

while(t!=root)

{

cout<<" "<<t->data;

t=presuc(t);

}

/*--<< Function defination for Inorder successor >>--*/

node * tbtree::insuc(node *t)

{

if(t->rbit==1)

{

t=t->rchild;

while(t->lbit==1)

t=t->lchild;

return(t);

}

else

return(t->rchild);

}

/*--<< Function defination for Inorder Traversal >>--*/

void tbtree::inorder()

{

node *t;

t=root->lchild;

while(t->lbit==1)

t=t->lchild;

while(t!=root)

{

cout<<" "<<t->data;

t=insuc(t);

}

/*--<< Function defination for Postorder successor >>--*/

node * tbtree::postsuc(node *t)

{

if(t->flag==0)

{

t=father(t);

if(t->rbit==0)

return(t);

else

{

if(t==t->rchild)

return(t);

t=t->rchild;

while(t->lbit==1 || t->rbit==1)

if(t->lbit==1)

t=t->lchild;

else

t=t->rchild;

return(t);

}

else

return(father(t));

}

/*--<< Function defination for Postorder Traversal >>--*/

void tbtree::postorder()

{

node *t;

t=root->lchild;

while(t->lbit==1 || t->rbit==1)

if(t->lbit==1)

t=t->lchild;

else

t=t->rchild;

while(t!=root)

{

cout<<" "<<t->data;

t=postsuc(t);

}

node * tbtree::father(node *t)

{

if(t->flag==0)

{

while(t->rbit==1)

t=t->rchild;

return(t->rchild);

}

else

{

while(t->lbit==1)

t=t->lchild;

return(t->lchild);

}

/*-------------<< Main Function Starts >>------------*/

void main()

{

tbtree t;

int ch;

clrscr();

{

cout<<"\n\n\t\t\t-----<< MENU >>-----";

cout<<"\n\n\t\t\t1.Create TB-Tree";

cout<<"\n\t\t\t2.Preorder Traversal";

cout<<"\n\t\t\t3.Inorder Traversal";

cout<<"\n\t\t\t4.Postorder Traversal";

cout<<"\n\t\t\t5.Exit";

cout<<"\n\n\t\t\t--------------------";

cout <<"\n\n\t\t\tEnter Your Choice :";

cin>>ch;

switch(ch)

{

case 1:

t.create();

break;

case 2:

cout<<"\nPreorder Traversal :";

t.preorder();

break;

case 3:

cout<<"\nInorder Traversal :";

t.inorder();

break;

case 4:

cout<<"\nPostorder Traversal :";

t.postorder();

break;

}

}while(ch!=5);

getch();

}

/*-------------<< End Of Main Function >>---------------*/

/*-----------------<< OUTPUT SCREEN >>-------------------*/

-----<< MENU >>-----

1.Create TB-Tree

2.Preorder Traversal

3.Inorder Traversal

4.Postorder Traversal

5.Exit

--------------------

Enter Your Choice :1

Enter a data(-1 for no data) : 10

Enter lchild child of 10

Enter a data(-1 for no data) : 20

Enter lchild child of 20

Enter a data(-1 for no data) : 40

Enter lchild child of 40