C Binary Tree

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:

inorder - using inorder, you visit the left subtree, the root, and then the right subtree
preorder - using preorder, you visit the root, the subtree and then the right subtree
postorder - using postorder, you visit the left subtree, the right subtree, and then the root

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;
}

C Binary Tree Example

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: