Wednesday, August 17, 2011

QUES 30 BINARY TREE


C LANGUAGE BOOK










 BINARY TREE

A binary tree is a tree all of whose vertices have out-degree < 2. Furthermore,
the subtrees of a binary tree are ordered in the sense that there is a left child and a right child.
If a vertex has only one child, it must be clearly identified as left or right.

The “beginning” of the tree is a unique starting node called the root.


the tree on the left of root is called left subtree.
the tree on the right of root is called right subtree.
























Here are two important properties of binary trees. 

Strictly Binary

T is a strictly binary tree iff each of its vertices has out-degree = 0 or out-degree = 2. Vertices with out-degree = 1 are not allowed in strictly binary trees.

Balanced

The definition of balance can also be stated recursively:
  1. A binary tree consisting of a single vertex is balanced.
  2. A vertex with a single subtree is balanced iff that subtree is a leaf.
  3. A binary tree is balanced iff its left and right subtrees are balanced and their depths differ by at most 1.
Balance is an important property of binary search trees.

Intuitively, a binary tree is balanced if it is not “heavy” on either side. There are several alternative balance conditions, each with its areas of application. For our purposes here, we will say that T is a balanced

(sometimes called height-balanced) binary tree iff for each vertex v in T, the depths of v’s right and left subtrees differ by at most one. If one subtree is null, the other subtree must either be null or be a leaf.

                   Figure . Balanced (or Height-Balanced) Binary Trees



 (a) These binary trees are height-balanced
  

 












(b) These binary trees are not height-balanced



 Complete Binary Tree:-
 A binary tree is to be complete if

each node have two sub node.
nodeleft and noderight 

  as you see in figure each node have two sub node.
1 is root node.
2 is the left .3 is on right

 

It is important to understand that for a tree to be balanced, the property must hold for every vertex in the tree, not just its root. For all the trees in Figure , make sure you know why each is either balanced or not balanced.
 

Expression Trees

One common application of binary trees is in interpreters or compilers for programming languages, where the statements of a source program are converted into trees so that the structure of the statements is apparent. As a simple case of this type, we will consider expression trees, which are transformations of arithmetic expressions into binary trees. We will use, for simplicity, a restricted expressions that consists of single-letter identifiers or variable names, one-digit integer constants, the four arithmetic operators +, -, *, and /, and parentheses.

We consider first only fully parenthesized expressions. An expression tree always has an operator at its root and identifiers or constants at its leaves. (The exception is an expression consisting only of a single identifier or constant; here, there is just one vertex, both root and leaf.) The root operator is the “main” operator of the expression—that is, the operator that is performed last as the expression is evaluated. Interior vertices are the operators of subexpressions

To give a few examples, Figure  shows the expression trees for A, A-B, (A-B)+C, A-(B+C), and (A+B)*(C-D). Notice carefully how these trees are constructed  and make sure you understand well how (A-B)+C and A-(B+C) give rise to different trees. In (A-B)+C, the + is the main operation, since it is performed last; in A-(B+C), it is the - that is the main operation.
  




































Binary search tree(BST):-
The important thing about BST to keep in mind is that in a BST:1.The left sub-tree of a node contains only nodes with keys less than the node’s key.
2.The right sub-tree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.


each node have two sub node.
nodeleft and noderight 

the nodeleft  have less data than the node 's data.
the noderight  have greater data than the node 's data.
as you see in figure 3 less than 8.so  it is left of 8
 6 is greater than 3.so it is on right of 3.
















 Traversals of Binary Trees:-
 it can be done in three way.
1.Inorder
2.Preorder
3.PostOrder

InOrder:-it :is also sorted order.
it traverse in left root right.

 In above figure
the inorder is 
1 3 4 6 7 8 10 13 14


PreOrder:-
 it traverse in root left right.

In above figure
the Preorder is 
8 3 1 6 4 7 10 14 13


PostOrder:-
it traverse in left  right root.

 In above figure
the Postorder is 
1  4 7 6 3 13 14 10 8


here below figure with examples.

























/*WAP to Create A Binary Search Tree Display Traversal Using Inorder,PostOrder and Preorder.*/

#include<alloc.h>
#include<stdio.h>

struct mytree
{
int data;
struct mytree *right;
struct mytree *left;
};

main()
{

struct mytree *p;
int i, m, n;

do
{

printf("  BinaryTree  ");
printf("\n1.Insert Any number");
printf("\n2.Delete Root");
printf("\n3.Delete Any Number");
printf("\n4.Display Using Inorder");
printf("\n5.Display Using Preorder");
printf("\n6.Display Using Postorder");
printf("\n7.Exit\n");

scanf("%d", &i);

switch(i)
{
case 1: printf("\nEnter the Number : ");
    scanf("%d",&n);
    Insert(&p, n);
    printf("\n");
    break;
case 2: Rootcancel(&p);
    printf("\n");
    break;
case 3: printf("\nEnter the Number : ");
    scanf("%d",&m);
    Delete(&p, m);
    printf("\n");
    break;
case 4: printf("\n\n");
    InDisp(p);
    printf("\n\n");
    break;
case 5: printf("\n\n");
    PreDisp(p);
    printf("\n\n");
    break;
case 6: printf("\n\n");
    PostDisp(p);
    printf("\n");
    break;
case 7: exit(1);
default:printf("Wrong Choice\n");
}

}
while(i>=1 && i<=7);

}


maketree(struct mytree **b,int c)
{
 (*b)->left = NULL;
 (*b)->data = c;
 (*b)->right = NULL;
return;
}

checktree(struct mytree *q,int t)
{
struct mytree *x,*y;
x = q;
if(x == NULL)
{

 y->left = NULL;
 y->data = t;
 y->right = NULL;

 q = y;
 }
}

Insert(struct mytree **q,int b)
{
struct mytree *x,*y,*z;

if((*q) == NULL)
{
 (*q) = malloc(sizeof(struct mytree));
 maketree(&(*q),b);
 err_msg(4);
}
else
if((*q) != NULL)
{

 if(b < (*q)->data)
  {
    Insert( &( (*q)->left ),b);
  }
  else
  if(b > (*q)->data)
  {
    Insert( &( (*q)->right ),b);
  }

}
return;
}

Rootcancel(struct mytree **q)
{

struct mytree *x, *z, *w,*y,*p;

x = *q;

if(x == NULL)
{
  err_msg(1);
}
else
if(x->left == NULL)
{
w = x;
x = x->right;
*q = x;
 free(w);
}
else
if(x->right == NULL)
{
w = x;
x = x->left;
*q = x;
free(w);
}
else
if(x->left == NULL && x->right == NULL)
{
 w = x;
 x = NULL;
 *q = x;
 free(w);
}
else
if(x->left != NULL && x->right != NULL)
{
 w = *q;
 y = (*q)->left;
 z = (*q)->right;
 if(z->left == NULL)
 {
   z->left = y;
   *q = z;
   free(w);
  }
 else
 if(z->left != NULL)
 {
  *q = (*q)->right;
 while( (*q)->left != NULL)
 {
   *q =(*q)->left;
  }

  x = w->right;
  p=x;
  while( x->left != NULL)
 {
   x =x->left;
  }

  x->left = *q;
  (*q)->left = y;
  *q = p;
 free(w);
 }
}

return;
}

Delete(struct mytree **q, int t)
{
struct mytree *w,*y,*z,*p,*x;

if((*q)->data == t)
{

  if((*q)->left == NULL)
  {

   w = *q;
   *q = (*q)->right;
   free(w);
   return;
  }
  else
  if((*q)->right == NULL)
  {
   w = *q;
   *q = (*q)->left;
   free(w);
   return;
   }
  else
  if((*q)->left == NULL && (*q)->right == NULL)
  {
   w = *q;
   *q = NULL;
   free(w);
   return;
  }
  else
  if((*q)->left != NULL && (*q)->right != NULL)
  {

     w = *q;
     y = (*q)->left;
     z = (*q)->right;
     if(z->left == NULL)
     {
     z->left = y;
      *q = z;
      free(w);
     }
     else
     if(z->left != NULL)
     {
      *q = (*q)->right;
 while( (*q)->left != NULL)
 {
   *q =(*q)->left;
  }
  p = w->right;
  x = p;
  while( p->left != NULL)
 {
   p =p->left;
  }

  p->left = *q;
  (*q)->left = y;
  *q = x;
 free(w);
 }
  }

}
  else
  {
      if(t < (*q)->data)
    Delete( &( (*q)->left ), t);
      else
      if(t > (*q)->data)
    Delete( &( (*q)->right ), t);
      else
      {
      err_msg(3);
      return;
      }
   }

}

dsearch( struct mytree **p, int c )
{

 struct mytree *w;
 if((*p)->data == c)
 {
    w = *p;
   *p = (*p)->right;
   while((*p)->left != NULL)
   {
    *p =  (*p)->left;
    }
   (*p)->left = w->left;
   free(w);
   return;
  }
  else
   {
     dsearch( &((*p)->left), c );
     dsearch( &((*p)->right), c );
     return;
    }
}

InDisp(struct mytree *q)
{
 if(q != NULL)
 {

  InDisp( q->left );

  printf("-> %d", q->data);

  InDisp( q->right );

 return;
}
}

PreDisp(struct mytree *q)
{
 if(q != NULL)
 {

  printf("-> %d", q->data);

  PreDisp( q->left );

  PreDisp( q->right );
   return;

}
}

PostDisp(struct mytree *q)
{
 if(q != NULL)
 {

  PostDisp( q->left );

  PostDisp( q->right );

  printf("-> %d", q->data);


return;
}
}

err_msg(int p)
{

if(p == 1)
{
printf("The Tree is Empty");
}
else
if(p==2)
{
printf("Wrong Choice");
}
else
if(p==3)
{
printf("Number Not Found");
}
else
if(p==4)
{
printf("hello");
}
else
if(p==5)
{
printf(" Empty b");
}


}














C LANGUAGE BOOK

No comments:

Post a Comment