C++ Codes
C++ > Data Structures sample source codes

Code to create binary tree, find mirror image of it, find height,

Code to create binary tree, find mirror image of it, find height,
print original tree and mirrot image tree level wise, display leaf
nodes

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>    //header for standard library function  exit();
typedef class bin_tree
{
	public:
		int data,status;
		class bin_tree *lchild,*rchild; //pointers to class bin_tree
		bin_tree():data(0),lchild(NULL),rchild(NULL),status(0){}//constructor
		class bin_tree* createbt(class bin_tree*,int data);  //create 
function
		void leafnodes(class bin_tree*);
		void display(class bin_tree*);
		class bin_tree* mirrorimage(class bin_tree*,class bin_tree*);
		void levelprint(class bin_tree*,int&);
}nodebt;//typedef for simplicity
typedef class queue
{
	public:
	nodebt *data;
	class queue *next;
	queue():data(NULL),next(NULL){}
	nodebt* deletefront(queue **front,queue **rear);
	queue *insertrear(queue **front,queue **rear,nodebt *data);
}que;
void nodebt::levelprint(class bin_tree* r,int &height)
{
	que q1;
	nodebt *check=NULL,*pt=r;
	que *front=NULL,*rear=NULL;
	q1.insertrear(&front,&rear,r);
	q1.insertrear(&front,&rear,check);
	while(front!=NULL)//q not empty
	{
		while(pt!=NULL)
		{
			pt=q1.deletefront(&front,&rear);
			if(pt==NULL)
			{
				cout<<endl;
				height++;
				q1.insertrear(&front,&rear,check);
				pt=q1.deletefront(&front,&rear);
			}
			if(front==NULL)
			return;
			cout<<pt->data<<" ";
			if(pt->lchild!=NULL)
			q1.insertrear(&front,&rear,pt->lchild);
			if(pt->rchild!=NULL)
			q1.insertrear(&front,&rear,pt->rchild);
		 }
	}
}
nodebt* que::deletefront(que **front,que **rear)
{
	nodebt *temp=NULL;
		if(*front==NULL)
		{
			cout<<"
 queue is empty";
		}
		else
		{       temp=(*front)->data;
			(*front)=(*front)->next;
			if((*front)==NULL)
			{
			       *rear=NULL;
			}
		}
	return temp;
}
que *que::insertrear(que **front,que **rear,nodebt *data)
{
	que *temp=NULL;
		temp=new queue;
		temp->data=data;
		temp->next=NULL;
		if(*front==NULL)
		{
			*front=temp;
			*rear=temp;
		}
		else
		{
			(*rear)->next=temp;
			*rear=(*rear)->next;
		}
	return *front;
}
nodebt* nodebt::mirrorimage(class bin_tree *r,class bin_tree* m)
{
	nodebt *ret=NULL;
	if(r==NULL)
	return r;
	if(r->status==2)
	{
		nodebt *temp=new nodebt;
		temp->data=r->data;
		temp->status=2;
		m=temp;
		ret=temp;
	}
	if(r->status==0)
	{
		nodebt *temp=new nodebt;
		temp->data=r->data;
		temp->status=1;
		m->rchild=temp;
		m=m->rchild;
	}
	if(r->status==1)
	{
		nodebt *temp=new nodebt;
		temp->data=r->data;
		temp->status=0;
		m->lchild=temp;
		m=m->lchild;
	}

	mirrorimage(r->lchild,m);
	mirrorimage(r->rchild,m);
	return ret;
}
void nodebt::leafnodes(class bin_tree* r)
{
	if(r==NULL)
	return;
	if(r->lchild==NULL && r->lchild==NULL)
	cout<<r->data<<" ";
	leafnodes(r->lchild);
	leafnodes(r->rchild);
}
void nodebt::display(class bin_tree* r)
{
	if(r==NULL)
	return;
	cout<<" "<<r->data<<" ";
	display(r->lchild);
	display(r->rchild);
}
nodebt* nodebt::createbt(nodebt *r,int data)
{
	int ch=0;
	if(r==NULL)
	{
		nodebt *temp=new nodebt;
		temp->data=data;
		temp->status=2;
		r=temp;
	}
	else
	{
		cout<<"
	1.INSERT AT LEFT OF"<<" "<<r->data;
		cout<<"
	2.INSERT AT RIGHT OF"<<" "<<r->data;
		cout<<"
	ENTER YOUR CHOICE=";
		cin>>ch;
		switch(ch)
		{
			case 1:if(r->lchild==NULL)
				{
					nodebt *temp=new nodebt;
					temp->data=data;
					temp->status=0;
					r->lchild=temp;
				}
				else
				createbt(r->lchild,data);
				break;
			case 2:if(r->rchild==NULL)
				{
					nodebt *temp=new nodebt;
					temp->data=data;
					temp->status=1;
					r->rchild=temp;
				}
				else
				createbt(r->rchild,data);
				break;
		}
	}
	return r;
}
int main()
{       int ch=0,data=0,height=0;
	nodebt *head=NULL,*m=NULL;
	nodebt t2;
	do
	{       clrscr();
		cout<<"
		MENU";
		cout<<"
	1.CREATE OR INSERT BINARY TREE";
		cout<<"
	2.PRINT LEAF NODES";
		cout<<"
	3.FIND MIRROR IMAGE OF THE TREE";
		cout<<"
	4.PRINT ORIGINAL AND MIRROR IMAGE LEVELWISE";
		cout<<"
	5.HEIGHT OF TREE";
		cout<<"
	6.EXIT";
		cout<<"
	ENTER YOUR CHOICE=";
		cin>>ch;
		switch(ch)
		{
			case 1: nodebt t1;
				do
				{
					cout<<"
ENTER THE DATA=";cin>>data;
					head=t1.createbt(head,data);
					cout<<"
 DO U WANT TO ADD MORE NODES(1.YES/2.NO)";
					cout<<"
 ENTER YOUR CHOICE";
					cin>>ch;
				}while(ch!=2);
				t1.display(head);
			       break;
			case 2:t1.leafnodes(head);
			       break;
			case 3:m=t2.mirrorimage(head,m);
			       cout<<"
	MIRRORIMAGE TREE LEVELWISE
";
			       height=0;
			       t2.levelprint(m,height);
			       break;
			case 4: cout<<"
	ORIGINAL TREE LEVELWISE
";
				t1.levelprint(head,height);
				m=t2.mirrorimage(head,m);
				cout<<"
	MIRRORIMAGE TREE LEVELWISE
";
				height=0;
				t2.levelprint(m,height);
				cout<<"
	HEIGHT OF BINARY TREE="<<height-1;
				break;
			case 5:cout<<"
	HEIGHT OF BINARY TREE="<<height-1;
			       break;
			case 6:exit(1);
		}
		getch();
	}while(ch!=6);
	return 1;
}