BINARY_TREE

BINARY TREE OPERATIONS

HOME
 
/*….PROGRAM
TO IMPLEMENT OPERATIONS

         
           
    ON THE BINARY TREE…*/

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

class
tree;

class
stack //CLASS

NAME
{
  
 tree* pointer;

  
 stack *top;

public:
  
 stack()     

  
 {

  
 top=NULL;

  
 }

  
 void push(tree* i) //FUNCTION
TO PUSH

  
 {

  
 stack *p;

  
 p= new stack;

  
 p->pointer =i;

  
 p->top = top;

  
 top = p;

  
 }

  
 tree* pop() //FUNCTION
TO POP

  
 {

  
 tree* temp;

  
 stack *tempp;

  
 temp  = top->pointer;

  
 tempp = top->top;

  
 delete top;

  
 top = temp;

  
 return temp;

  
 }

  
 int empty();

};

int
stack::empty()

{
  
 if(top == NULL)

  
     return 1;

  
 return 0;

}

class
tree

{
  
 int data;

  
 tree* left;

  
 tree* right;

public:
  
 tree()

  
 {

  
 left = NULL;

  
 right = NULL;

  
 data =0;

  
 }

  
 

void
build_tree()//FUNCTION
TO BUILD BINARY TREE

{
  
 char option;

  
 cout<<“ENTER THE ELEMENT: “;

  
 cin >> data;

  
 cout<<“DO YOU WANT TO ADD LEFT
 SUBTREE =>”<<data<<”
(y/n)”;

  
 cin >>option;

  
 if(option ==’y’||option==’Y’)

  
 {

  
 cout<<“enter left tree: “<<endl;

  
 left = new tree;

  
 left->build_tree();//RECURSIVE CALLING

  
 }

cout<<“DO
YOU WANT TO ADD RIGHT
 SUBTREE =>”<<data<<” (y/n)
“;
  
 cin >>option;

if(option
==’y’||option==’Y’)

  
 {

  
 cout<<“enter right tree: “<<endl;

  
 right = new tree;

  
 right->build_tree();

  
 }

  
 }

void
pre_order()//FUNCTION
FOR PREORDER TRAVERSAL

{
 stack
s;

 tree
*p;

 cout<<endl;
 s.push(this);

 while(!s.empty())
 {
 p
= s.pop();

 while(p
!= NULL)

 {
 cout<<p->data<<
” “;

 if(p->right
!= NULL)

 s.push(p->right);
 p
= p->left;

 }
 }
 }
void
in_order()//FUNCTION
FOR THE INORDER TRAVERSAL

{
  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

while(p
!= NULL || !s.empty())

{
  
 while( p!= NULL)

  
 {

  
 s.push(p);

  
 p = p->left;

  
 }

if(!s.empty())
  
 {

  
 p = s.pop();

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

  
 p = p->right;

  
 }

}
  
 }

//FUNCTION
FOR POSTORDER TRAVERSAL

void
post_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

  
 while(1)

  
 {

  
 while( p != NULL)

  
 {

  
     p->data =
-p->data;

  
     s.push(p);

  
     p = p->left;

  
 }

  
 if(s.empty())

  
     return;

  
 p = s.pop();

  
 while(p->data > 0)

  
 {

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

  
 if(s.empty())

  
 return;

  
 p= s.pop();

  
 }

  
 p->data = -p->data;

  
 s.push(p);

  
 p = p->right;

  
 }

  
 }

};

//main()
FUNCTION STARTS

void
main()

{
  
 tree t;//OBJECT
CREATION

  
 cout<<” (ROOT)  “;

  
 

  
 t.build_tree();

cout<<endl<<“PRE-ORDER
TRAVERSAL

          
OF GIVEN TREE: “;

  
 t.pre_order();

cout<<endl<<“IN-ORDER
TRAVERSAL

          &nbs

p; 
OF GIVEN TREE: “;
  
 t.in_order();

cout<<endl<<“POST-ORDER
TRAVERAL

          &nbs

p; 
OF GIVEN TREE: “;
  
 t.post_order();

}
//PROGRAM
ENDS

/*   
 

 OUTPUT:

(ROOT)  ENTER THE
ELEMENT: 100

DO
YOU WANT TO ADD LEFT

        
SUBTREE =>100 (y/n)Y

enter
left tree:

ENTER
THE ELEMENT: 70

DO
YOU WANT TO ADD LEFT

          
SUBTREE =>70 (y/n)N

DO
YOU WANT TO ADD RIGHT

          
SUBTREE =>70 (y/n) Y

enter
right tree:

ENTER
THE ELEMENT: 35

DO
YOU WANT TO ADD LEFT

           
SUBTREE =>35 (y/n)N

DO
YOU WANT TO ADD RIGHT

          
SUBTREE =>35 (y/n) n

DO
YOU WANT TO ADD RIGHT

        
SUBTREE =>100 (y/n) y

enter
right tree:

ENTER
THE ELEMENT: 125

DO
YOU WANT TO ADD LEFT

        
SUBTREE =>125 (y/n)Y

enter
left tree:

ENTER
THE ELEMENT: 56

DO
YOU WANT TO ADD LEFT

       
SUBTREE =>56 (y/n)N

DO
YOU WANT TO ADD RIGHT

        
SUBTREE =>56 (y/n) N

DO
YOU WANT TO ADD RIGHT

           
SUBTREE =>125 (y/n) Y

enter
right tree:

ENTER
THE ELEMENT: 78

DO
YOU WANT TO ADD LEFT

       
SUBTREE =>78 (y/n)N

DO
YOU WANT TO ADD RIGHT

        
SUBTREE =>78 (y/n) N

PRE-ORDER
TRAVERSAL OF

         
GIVEN TREE:

100
70 35 125 56 78

IN-ORDER
TRAVERSAL OF

         
GIVEN TREE:

70
35 100 56 125 78

POST-ORDER
TRAVERAL OF

        
GIVEN TREE:

35
70 56 78 125 100

 Press
any key to continue  */

HOME

Advertisements

1 Comment »

  1. 1
    varaprasad Says:

    This is nice.
    But All topics need to be covered
    eg AVL ,Red Black,Splay trees,Hashing etc.
    not only code but puzzles and discussions your ideas etc.


RSS Feed for this entry

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

%d bloggers like this: