Tuesday, 12 December 2017

Binary Tree Implementation and Operations in C

C program to implement binary tree and its three operations:

 1. Preorder traversal
 2. Inorder traversal
 3. Postorder traversal

Source Code

binarytree.c

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

// Defines a tree node as a structure
struct node { 
     struct node * left;
     char data; 
     struct node * right;
 };

// Function declaration
struct node * buildTree ( int ); 
void preorder(struct node *); 
void inorder(struct node *); 
void postorder( struct node *root ); 

// Tree node data
char array[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' }; 

// Indices of left children
int leftcount[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 }; 

// Indices of right children
int rightcount[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 }; 


int main() { 
      struct node *root; 
      int ch;
      root = buildTree ( 0 );
   
      do{
           printf("\n1: Preorder Traversal\n");
           printf("2: Inorder Traversal\n");
           printf("3: Postorder Traversal\n");
           printf("\tEnter your choice: ");
           scanf("%d",&ch);

           switch(ch) {
                case 1:
                     printf("\nPre-order Traversal: \n");
                     preorder(root);
                     break;
                case 2:
                     printf("\nIn-order Traversal: \n");
                     inorder(root);
                     break;
                case 3:
                     printf("\nPost-order Traversal: \n");
                     postorder(root); 
                     break;
                default:
                     printf("\nExiting.....\n");
           }
      }while(ch>0 && ch<4);
 } 

// Function to build tree using above data
struct node * buildTree ( int index ) { 
      struct node *temp = NULL;
      if (index != -1) {
           temp = (struct node *) malloc( sizeof ( struct node ) );
           temp->left = buildTree ( leftcount[index] );
           temp->data = array[index];
           temp->right = buildTree ( rightcount[index] );
      }
      return temp;
}

// Function to print tree data using inoder traversal 
void inorder( struct node *root ) {
      if (root != NULL) {
           inorder(root->left);
           printf("%c\t", root->data);
           inorder(root->right);
      }
}

// Function to print tree data using preorder traversal 
 void preorder( struct node *root ) {
      if (root != NULL) {
           printf("%c\t", root->data);
           preorder(root->left);
           preorder(root->right);
      }
}

// Function to print tree data using postorder traversal 
void postorder( struct node *root ) {
      if (root != NULL) {
           postorder(root->left);
           postorder(root->right);
           printf("%c\t", root->data);
      }
}






No comments:

Post a comment