Archive for the ‘BINARY_TREE’ Category

TREES

April 1, 2008

HOME


Definition of a Tree:

A tree is a set of one or more nodes T such that:
(i).There is a specially designated node called a root
(ii).The remaining nodes are partitioned into n disjointed
set of nodes T1, T2,…,Tn, each of which is a tree.

Degree of a Node of a Tree:
The degree of a node of a tree is the number of subtrees having this node as a root. In other words,the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.

Degree of a Tree:
The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max(degree(node i) for I = 1 to n)

Level of a Node:
We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees.We then define the depth of the tree to be the maximum value of the level of the node of the tree.

Binary tree:
A tree T is finite set of nodes, such that
(i).T is empty(called Empty binary tree),
(ii).T contains specially designed node called the root
of T,and the remaining nodes of T form T1 and T2
which are called as left subtree and right subtree.

Binary Search Tree:
Def:
A Binary Tree is said to be Binary Search Tree, the values in the left subtree should be less than that of root element and the values in the right subtree should be greater than that of root element.


Tree Traversals:
Traversing is nothing but visiting all the nodes of a Tree exactly once.
In-order Traversal:
•visit left sub tree of the Root node using In-order traversal
•visit Root node
•visit right sub tree of the Root node using In-order traversal

Pre-order Traversal:
•visit Root node
•visit left sub tree of the Root node using Pre-order Traversal
•visit right sub tree of the Root node using Pre-order Traversal

Post-order Traversal:
•visit left sub tree of the Root node using Post-order Traversal
•visit right sub tree of the Root node using Post-order Traversal
•visit Root node

HOME

BINARY_TREE

March 29, 2008

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