Archive for the ‘BST’ 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_SEARCH_TREE

March 27, 2008

BINARY SEARCH TREE

HOME
/*PROGRAM
TO IMPLEMENT BINARY SEARCH TREE*/


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

class
tree;

class
stack  //CLASS
DECLARATION

{
  
 tree* pointer;

  
 stack *top;

public:
  
 stack()

  
 {

  
     top=NULL;

  
 }

  
 void push(tree* i)

  
 {

  
     stack *p;

  
     p= new stack;

  
     p->pointer =i;

  
     p->top = top;

  
     top = p;

  
 }

  
 tree* pop()

  
 {

  
     tree* temp;

  
     stack *tempp;

  
     temp  =
top->pointer;

  
     tempp = top->top;

  
     delete top;

  
     top = tempp;

  
     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 in_order()

  
 {

  
 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;

  
 }

       
}

  
 }

  
 void pre_order()

  
 {

  
 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 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;

  
 }

  
 }

  
 

  
 void deletion(int i)

  
 {

  
 int flag=0;

  
 tree *p,*q;

  
 p = this;

  
 while( p!= NULL)

  
 {

  
  if(i < p->data)

  
 {

  
 q=p;

  
 p= p->left;

  
 }

       
else if(i > p->data)

  
 {

  
 q=p;

  
 p=p->right;

  
 }

  
  else if(i== p->data)

  
 {

  
 flag=1;

  
 break;

  
 }

       
}

  
 if(flag == 0)

  
 {

  
 cout<<endl<<i<<”
not in the list.

          &nb

sp;           &n

bsp; 
no deletion performed.”;
  
 return;

  
 }

          &nb

sp;   // if deleting
element is root

  
 if(i == data)    

  
 {

  
 if(p->right == NULL)

  
 {//replace
with in-order predecessor

  
 int temp;

  
 temp =p->left->max();

  
 p->deletion(temp);

  
 p->data = temp;

  
 return;

  
 }

  
 else if(p->left == NULL)

  
 {//replace
with in-order successor

  
 int temp;

  
 temp = p->right->min();

  
 p->deletion(temp);

  
 p->data = temp;

  
 return;

  
 }

  
 }

  
 // p has no
children.

  
 if(p->right == NULL && p->left
== NULL)

  
 {

  
 if(q->right == p)

  
 q->right = NULL;

  
 else

  
 q->left  = NULL;

  
 delete p;

  
 }

  
 //p has
only one child.

  
 else if( p->right == NULL)

  
 {

  
 if(q->right == p)

  
 q->right = p->left;

  
 else

  
 q->left  = p->left;

  
 delete p;

  
 }

  
 else if( p->left == NULL)

  
 {

  
 if(q->right == p)

  
 q->right = p->right;

  
 else

  
 q->left  = p->right;

  
 delete p;

  
 }

  
 //p have
both children.

  
 else

  
 {

  
  int temp;

  
  temp = p->left->max();

  
  p->deletion(temp);

  
  p->data = temp;

  
 }

  
 }

  
 int max()

  
 {

  
 tree *p = this;

  
 while(p->right != NULL)

  
       
 p = p->right;

  
 return p->data;

  
 }

  
 int min()

  
 {

  
 tree *p = this;

  
     

  
 while(p->left != NULL)

  
       
 p = p->left;

  
 return p->data;

  
 }

  
 void insert(int i)

  
 {

  
 if(data == 0)//null
tree checking

  
 {

  
 data = i;

  
 return;

  
 }

  
 tree *p = this;

  
 tree *q = this;

  
 tree *temp;

  
 while(p != NULL)

  
 {

  
 q = p;

  
 if(i < p->data )

  
 p = p->left;

  
 else if(i > p->data)

  
 p = p->right;

  
 else

  
 return;

  
 }

  
 temp = new tree;

  
 temp->data = i;

  
 if(i < q->data)

  
 q->left = temp;

  
 else

  
 q->right = temp;

  
 }

};
void
main()

{
  
 tree t;

  
 int i,n,num;

cout<<endl<<“ENTER
THE NO OF  ELEMENTS

          &nb

sp; 
IN THE BINARY SEARCH TREE: “;
  
 cin >>n;

cout<<“ENTER
THE ELEMENTS:\t”;

  
 for(i=0; i<n; i++)

  
 {

  
     cin>>num;

  
     t.insert(num);

  
 }

cout<<“THE
ELEMENTS IN

          &nb

sp;
THE INORDER TRAVERSAL”;
  
 t.in_order();

cout<<“THE
ELEMENTS IN

          
THE POSTORDER TRAVERSAL\n”;

  
 t.post_order();

cout<<“THE
ELEMENTS IN

         
THE PREORDER TRAVERSAL”;

  
 t.pre_order();

  
 

cout<<“ENTER
THE

          &nb

sp;
ELEMENT TO BE DELETE: “;
  
 cin >>num;

  
 t.deletion(num);

cout<<endl<<“AFTER
DELETION: “;

  
 t.in_order();

}
//program ends
/* output:

ENTER
THE NO OF ELEMENTS IN THE BINARY SEARCH TREE: 5

ENTER
THE ELEMENTS:     1

45
2
67
9

THE
ELEMENTS IN THE INORDER TRAVERSAL

1
2 9 45 67

THE
ELEMENTS IN THE POSTORDER TRAVERSAL

9
2 67 45 1

THE
ELEMENTS IN THE PREORDER TRAVERSAL

1
45 2 9 67 ENTER THE ELEMENT TO BE DELETE: 1

AFTER
DELETION:

2
9 45 67 Press any key to continue

*/

HOME