Binary Tree Traversals


#include<iostream.h>

class tree

{

int data;

tree* lptr;

tree* rptr;

public:

tree* build_root(tree* root,int key);

tree* build_tree(tree* root);

void display(tree*);

void inorder(tree*);

void preorder(tree*);

void postorder(tree*);

void levelorder(tree*);

}*root;

class Queue

{

public:

tree* queue[50];

int first;

int end;

Queue()

{

first=end=0;

}

void enqueue(tree* root);

tree* dequeue();

bool isempty();

};

void Queue::enqueue(tree* root)

{

if(first==0)

queue[first]=root;

else

queue[end]=root;

end++;

}

tree* Queue::dequeue()

{

if(end==first)

return NULL;

else

return queue[first++];

}

bool Queue::isempty()

{

if(first==end)

return true;

else

return false;

}

tree* tree::build_root(tree* root,int key)

{

tree* temp;

temp=new tree;

temp->data=key;

temp->lptr=temp->rptr=NULL;

if(key!=-1)

root=temp;

return root;

}

tree* tree::build_tree(tree* root)

{

cout<<“\n———————————————————————\n”;

tree* temp;

temp=root;

int key;

char ch;

root->lptr=NULL;

root->rptr=NULL;

cout<<“\nis there any left subtree for “<<root->data<<” ,if yes enter ‘s’ else enter ‘n’\n”;

cin>>ch;

if(ch==’s’||ch==’S’)

{

root->lptr=new tree;

cout<<“\nenter the data for the left subtree of “<<root->data<<endl;

cin>>key;

root->lptr->data=key;

root->lptr=build_tree(root->lptr);

}

else

root->lptr=NULL;

cout<<“\nis there any right subtree for “<<root->data<<” ,if yes enter ‘s’ else enter ‘n’\n”;

cin>>ch;

if(ch==’s’||ch==’S’)

{

root->rptr=new tree;

cout<<“\nenter the data for the right subtree of “<<root->data<<endl;

cin>>key;

root->rptr->data=key;

root->rptr=build_tree(root->rptr);

}

else

root->rptr=NULL;

cout<<“\n———————————————————————\n”;

root=temp;

return root;

}

void tree::display(tree* root)

{

if(root!=NULL)

inorder(root);

else

cout<<“\nthe tree is empty\n”;

}

void tree::inorder(tree* root)

{

if(root!=NULL)

{

inorder(root->lptr);

cout<<root->data<<“->”;

inorder(root->rptr);

}

}

void tree::preorder(tree* root)

{

if(root!=NULL)

{

cout<<root->data<<“->”;

preorder(root->lptr);

preorder(root->rptr);

}

}

void tree::postorder(tree* root)

{

if(root!=NULL)

{

postorder(root->lptr);

postorder(root->rptr);

cout<<root->data<<“->”;

}

}

void tree::levelorder(tree* root)

{

Queue q;

q.enqueue(root);

while(q.isempty()!=true)

{

root=q.dequeue();

if(root!=NULL)

{

cout<<root->data<<“->”;

if(root->lptr!=NULL)

q.enqueue(root->lptr);

if(root->rptr!=NULL)

q.enqueue(root->rptr);

}

}

}

void choice(tree* root)

{

tree object;

int ch;

cout<<“\nchoose the operation to be performed\n”;

cout<<“\n1.PREORDER TRAVERSAL\t2.INORDER TRAVERSAL\t3.POSTORDER TRAVERSAL\n”;

cout<<“\n4.LEVEL ORDER TRAVERSAL\t5.EXIT\n”;

cin>>ch;

while(ch!=5)

{

switch(ch)

{

case 1:

cout<<“\npreorder traversal of the tree is \n\n”;

object.preorder(root);

cout<<“\n\n”;

break;

case 2:

cout<<“\ninorder traversal of the tree is \n\n”;

object.inorder(root);

cout<<“\n\n”;

break;

case 3:

cout<<“\npostorder traversal of the tree is \n\n”;

object.postorder(root);

cout<<“\n\n”;

break;

case 4:

cout<<“\nlevel order traversal of the tree is \n\n”;

object.levelorder(root);

cout<<“\n\n”;

break;

case 5:

break;

default:

cout<<“\nenter correct choice\n”;

break;

}

cout<<“\nchoose the operation to be performed\n”;

cout<<“\n1.PREORDER TRAVERSAL\t2.INORDER TRAVERSAL\t3.POSTORDER TRAVERSAL\n”;

cout<<“\n4.LEVEL ORDER TRAVERSAL\t5.EXIT\n”;

cin>>ch;

}

}

void main()

{

tree object;

int key;

cout<<“\nenter the data for the root,if the tree is empty enter -1\n”;

cin>>key;

root=object.build_root(root,key);

if(root!=NULL)

root=object.build_tree(root);

if(root!=NULL)

{

choice(root);

}

else

cout<<“\nthe tree is empty,hence we can’t perform any type of traversal\n”;

}

3 thoughts on “Binary Tree Traversals”

  1. Pingback: lodine
  2. Pingback: foradil

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s