We have already seen several data structures like linked list , stack and queue.In linked list we have seen that method of traversing the list , from one node to the other.Let us see a better way of doing the same thing using Tree.Like linked lists, trees are made of nodes which contains both information part and address pointers.In linked list , an address pointer of a node holds the address of just another node, while in tree the address pointers can hold the address of more than one node of the same type.
A binary tree can thus be defined as a finite set of elements that is either empty or is partitioned into three disjoint subsets.The first subset contains a single element called the root of the tree.The other subsets are themselves binary trees , called the left and right subtree of the original tree.So while adding elements into a tree , we can add them category wise in left and right subfreezing case of searching the values , it will take less time.
A, B, C, D, E, F, G and I are all nodes. If A is the root of the binary tree then B is the root of the left sub tree and C is the root of right subtree.A is said to be the father of B and C while B is said to be the left son of A and C is said to be the right son of A. If a node doesn’t have any son then the node is called a leaf. Here D, G, H and I are leafs. The absence of a branch indicates an empty subtree.Here in the above diagram E and C are empty subtree.Two nodes are called brother is they are left and right son of the same father. In binary tree root is at the top and the leafs are at the bottom. So traversing from the leafs to the root is called climbing the tree and the reverse is called descending the tree. If every nonlife node in a binary tree has nonempty left and right sub tree then it is called a strictly binary tree. The above diagram is not a strictly binary tree.
The root of a tree has level 0 and the level of any other node in a tree is one more than the level of its father. The depth of a binary tree is the maximum level of a leaf in the tree. This equals to the longest path from the root to the leaf. A strictly binary tree is called a complete binary treewhen all the leafs of the tree have the same depth.
Now we will create a tree of linked list in such a manner that the nodes of the linked list will have one information part and two address pointers. In the info part numeric value will be stored while one address pointer will point to the right branch of the tree and the other will point to the left branch of the tree. The first value will be the root of the tree. After that whenever a value is read it will be compared with the contents of the tree (starting from root) and a left branch will be created if the value is found less than or equal to the content of a node otherwise the value will be inserted in the right branch.
# include< stdio.h>
# include< stdlib.h>
#include< conio.h>
struct node
{
int info;
struct node *left;
struct node *right;
};
struct node * create()
{
struct node *node;
int x;
node=(struct node *)malloc(sizeof(struct node));
printf("\nEnter the value:-");
scanf("%d",&x);
node->info=x;
node->left=NULL;
node->right=NULL;
return node;
}
/*The above function creates a node for the tree and set value in the node */
struct node *add(struct node *t,struct node *root)
{
if(root==NULL)
{
root=t;
return root;
}
else
{
if(t->info<=root->info)
{
root->left=add(t,root->left);
printf("\nAdded to left of node %d",root->info);
}
else
{
root->right=add(t,root->right);
printf("\nAdded to right of node %d",root->info);
}
return root;
}
}
/* Function add () adds the current created node in the specified location of the tree. If the tree passed as a parameter ( here root ) is empty , the current node is added ( here t ) and becomes the root of the tree. Otherwise , the program decides whether to continue it’s search down the left or the right sub tree. If the data member of the new node is less than or equal to the root node value then the function will continue along the left sub tree , otherwise the search continues along the right sub tree. If the searching process needs to be continued , the function calls itself with new root parameter ( it depends whether the function is searching through the left or right sub tree ).Ultimately the recursive calls will come to a point where the most recent local tree is empty and at that point the new node will be added.*/
void output (struct node *t, int level)
{
int i;
if (t)
{
output(t->right, level+1);
printf("\n");
for (i = 0; i < level; i++)
printf(" ");
printf("%d,%d (level)", t->info,level);
printf("\n");
output(t->left, level+1);
}
}
void main()
{
int info,xx=0;
char choice='y';
struct node *t,*root=NULL,*rr;
clrscr();
while(choice != 'n')
{
t=create ();
/* This function will create a linked list node and the node will be returned.*/
if(xx==0)
rr=t;
/* pointer rr will store the address of the first node of the tree.*/
xx++;
printf("\n Tree is ");
root=add(t,root);
/* add () function takes two arguments, the current created node address t and the pointer root to add the current created node in the tree (value small than the root or equal to the root will be inserted at the left branch of the tree root otherwise will be inserted at the right of the root).So after execution of this statement root will point the last inserted node of the tree.*/
output(rr,0);
/* To display the tree output () function is called with the root of the tree as the first argument and zero
level as the second argument*/
fflush(stdin);
printf("\n Enter choice--'n' to break:");
scanf("%c",&choice);
}
}
No comments:
Post a Comment