From the blow figure , it is clear that a binary tree is a tree of nodes where each node contains a left pointer, a right pointer and a data. The “root” pointer points to the topmost node in the tree. The left pointer points to left side of sub-trees while right pointer points to right side of sub-trees.

biatryThe above figure represents generalized form of binary tree where each node has up to two leaves ( children ). It is simply representation of tree data structure.A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent node, is called Binary search tree.

The figure can be converted to Binary search tree as below.

bsearchBinary search trees are used in many search applications.

How to represents binary tree in c/c++

struct node {
struct node* left;
int data;
struct node* right;
}

Now let us implement following operations on binary search tree. ( duplicate data is allowed )

  • insert()
  • In_order_traverse()
  • Pre_order_order_traverse()
  • post_order_traverse()

/* binary search tree */

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    struct Node *left;        /* left child */
    int data;  /* data to be stored*/
    struct Node *right;        /* right child */
} Node;

Node* insert (Node * node,int a);
void In_order_traverse (Node * node);
void Pre_order_order_traverse ();
void Post_order_traverse (Node * node);

int main ()
{

     Node *root = NULL;        /* root of binary tree */
     root =  insert(root,5);
     insert(root,3);
     insert(root,6);
     insert(root,5);

             /* in order traverse*/
             In_order_traverse(root);
             printf("\n");

/* pre order */
Pre_order_order_traverse(root);
printf("\n");

             /* post order */
             Post_order_traverse(root);
             printf("\n");

return 0;
}

Node* insert(Node* node, int a)
{
     /* create first node */
     if( node == NULL)
     {
        Node* tmp = (Node*)malloc(sizeof(Node));
        tmp->left = NULL;
        tmp->right = NULL;
        tmp->data = a;  // initialize with zero
        return tmp;
     }

      if( a < node->data) /* go to left */
         node->left = insert( node->left, a);
      else // go to right
         node->right = insert(node->right, a);
return node;
}

void In_order_traverse(Node *node)
{
    if (node != NULL)
    {
      In_order_traverse(node->left);
      printf("%d ", node->data);
      In_order_traverse(node->right);
    }
}

void Pre_order_order_traverse(Node* node)
{
   if( node != NULL)
   {
      printf("%d ", node->data);
      Pre_order_order_traverse(node->left);
      Pre_order_order_traverse(node->right);
   }

}
void Post_order_traverse(Node* node)
{
if( node != NULL)
{
     Pre_order_order_traverse(node->left);
     Pre_order_order_traverse(node->right);
     printf("%d ",node->data);
}

}

Ref: http://en.wikipedia.org/wiki/Binary_tree



Related Contents to follow