Binary Tree programing.
Like it on Facebook, Tweet it or share this article on other bookmarking websites.
A binary tree is a special case of tree, in which no node of a tree can have a degree of more than 2. Therefore, a binary tree is a set of zero or more nodes T such that:
1. there is a specially designated node called the root of the tree
2. the remaining nodes are partitioned into two disjointed sets, T1 and T2, each of which is a binary tree. T1 is called the ‘left subtree’ and T2 is called ‘right subtree’.
Below there is a programming in C language on the concept of Binary tree. So we have initialize a recursive structure each have two link part struct bt *lc and struct bt *rc and a data part. Like this …….…….. The left and right child contains either the same structure link or its NULL. Every time we create a node we call getnode() function where use malloc to allocate the space of the structure. Then the program will ask user to enter a data. And then whose left or right child do the user want to be the latest node is been asked. Now for print the tree we have use the concept of B.F.S. where we use a array whose data type is the same as the data type of the tree. We put the root node at the front of the array. Then we took the node at the front of the array and add its children to the rear of the array and print those with respect to the parent node’s data.
There is an advantage of using binary tree over normal tree. That is in case of Tree we don’t know the number of children to be define in the structure as Tree can have different number children in every node. So it is tuff to initialize the number of children in the structure. But a Binary tree can’t have more than 2 children. So we can just put two children link in the structure. One more thing I would like to add that we can also implement a tree using a array and not using Linked list. In that type of representation we can easily obtain the parent and child node. But the problem is some time there are too many unused space in array type representation of Binary tree.
Prograing Code…………
#include
#include
#include
struct bt
{
struct bt *lc;
int data;
struct bt *rc;
};
struct bt *getnode() /*allocate space for new node.*/
{
struct bt *newnode;
newnode = (struct bt *) malloc(sizeof(struct bt));
return(newnode);
}
struct bt *inorder(struct bt *tr, int z) /*searching a node with inorder traversal*/
{
inorder(tr->lc,z);
if(tr->data==z)
{
return tr;
}
inorder(tr->rc,z);
}
void data(struct bt*);
void display(struct bt *);
void main()
{
char ch;
struct bt *t;
t->data = 0;
t-> rc = ' ';
t-> lc = ' ';
do /*do-while loop starts */
{
printf("enter chicen 1. datan 2. printn 3. up.n 4. exit.n");
scanf("%c", & ch);
printf("u choose %c", ch);
switch(ch) /* switch case*/
{
case '1':printf(" u choose to enter data.");
data(t);
break;
case 2: display(t);
break;
case 3: break;
case 4: break;
}
}while(ch!=4);
}
void data(struct bt *t1)
{
int x,y,c;
struct bt *tre;
struct bt *temp;
printf("n enter the value under whose u want a child");
scanf("%d", & x);
tre= inorder(t1,x);
temp=getnode();
printf("enter data");
scanf("%d", & y);
temp->data = y; /* putting data in new node*/
temp -> lc = ' ';
temp -> rc = ' ';
printf("u want this node as 1. left child or 2. right child?");
scanf("%d", & c);
if(c==1)
{
temp->lc = tre->lc;
tre -> lc = temp;
}
else
{
temp->rc = tre->rc;
tre -> rc = temp;
}
}
void display(struct bt *t3)
{
struct bt *ar[100]; /* initialize structure type array*/
int fr,re;
ar[1]=t3;
fr=1;
re=1;
while(frlc != ' ')
{
ar[++re]= ar[fr]->lc;
}
if(ar[fr]->rc != ' ')
{
ar[++re]= ar[fr]->rc;
}
printf("n node is=%d", ar[fr]->data);
printf("l child is=%d", ar[fr]->lc->data);
printf("r child is=%d", ar[fr]->rc->data);
fr++;
}
}