C LANGUAGE BOOK |
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:- A binary tree consisting of a single vertex is balanced.
- A vertex with a single subtree is balanced iff that subtree is a leaf.
- A binary tree is balanced iff its left and right subtrees are balanced and their depths differ by at most 1.
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
(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
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