Binary trees are the special trees because, when sorted, they lend themselves to rapid searches, insertions, and deletions. Since each item in a tree consists of information along with a link to the left member and a link to the right member. Here this figure shows a small tree.
The root is the first item in the tree. Each item is called a node of tree, and any piece of tree is called a subtree. A node that has no subtrees attached to it is called a terminal node or leaf. The height of the tree is equal to the number of layers deep that its roots grow.
Note - A tree is only a way to logically organize the data in the memory, and the memory is linear.
The binary tree is a special form of linked list. Items can be inserted, deleted, and accessed in any order.
Most functions that uses the trees are recursive, because the tree itself a recursive data structure. That is, each subtree is itself a tree.
How a tree is ordered depends on how it is going to be accessed. The process of accessing each node in a tree is called a tree traversal. See the following tree.
There are the following three ways to traverse a tree:
Using each method, the order of access for the tree is show here :
inorder a b c d e f g preorder d b a c f e g postorder a c b e g f d
Even though, a tree need not be sorted, most uses require this. Of course, what constitutes a sorted tree depends on how you will be traversing the tree.
The following function, stree(), builds a sorted binary tree:
struct tree
{
char info;
struct tree *left;
struct tree *right;
};
struct tree *stree(struct tree *root,struct tree *r,char info)
{
if(!r)
{
r = (struct tree *)
malloc(sizeof(struct tree));
if(!r)
{
printf("Out of Memory..!!\n");
exit(1);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root)
return r; /* first entry */
if(info < root->info)
root->left = r;
else
root->right = r;
return r;
}
if(info < r->info)
stree(r, r->left, info);
else
stree(r, r->right, info);
return root;
}
Here is the complete example demonstrating binary tree in C. This program construct a binary tree in C language.
/* C Binary Tree - Binary Tree Program Example
* This program demonstrates the concept of
* binary tree in C programming
*/
#include<stdio.h>
#include<conio.h>
#include<assert.h>
#include<stdlib.h>
#define ARRAY_SIZE 10
typedef char DATA;
struct node
{
DATA d;
struct node *left;
struct node *right;
};
typedef struct node NODE;
typedef NODE *BINARY_TREE;
BINARY_TREE newnode(void);
BINARY_TREE init_node(DATA d, BINARY_TREE p1, BINARY_TREE p2);
BINARY_TREE create_tree(DATA a[], int i, int size);
void preorder (BINARY_TREE root);
void inorder (BINARY_TREE root);
void postorder (BINARY_TREE root);
BINARY_TREE new_node()
{
return((BINARY_TREE)malloc(sizeof(NODE)));
}
BINARY_TREE init_node(DATA d1, BINARY_TREE p1, BINARY_TREE p2)
{
BINARY_TREE temp;
temp = new_node();
temp->d = d1;
temp->left = p1;
temp->right = p2;
return temp;
}
BINARY_TREE create_tree(DATA a[], int i, int size)
{
if(i >= size)
{
return NULL;
}
else
{
return(init_node(a[i], create_tree(a, 2*i+1, size), create_tree(a, 2*i+2, size)));
}
}
void preorder(BINARY_TREE root)
{
if(root != NULL)
{
printf("%c ", root->d);
preorder(root->left);
preorder(root->right);
}
}
void inorder(BINARY_TREE root)
{
if(root != NULL)
{
inorder(root->left);
printf("%c ", root->d);
inorder(root->right);
}
}
void postorder(BINARY_TREE root)
{
if(root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%c ", root->d);
}
}
void main()
{
char arr[ARRAY_SIZE];
BINARY_TREE root;
int lop;
clrscr();
printf("Enter %d characters: ", ARRAY_SIZE);
for(lop=0; lop<ARRAY_SIZE; lop++)
{
scanf("%c", &arr[lop]);
fflush(stdin);
}
root = create_tree(arr, 0, ARRAY_SIZE);
assert(root != NULL);
printf("\n");
printf("Inorder:\t");
inorder(root);
printf("\n");
printf("Preorder:\t");
preorder(root);
printf("\n");
printf("Postorder:\t");
postorder(root);
printf("\n");
getch();
}
Here is the sample run of the above C program:
