Saturday, 10 October 2015

Finding Preorder, Inorder and Postorder of binary tree in C Language

                  In this post, we will see sample program in C language to find preorder, inorder and postorder traversal of binary tree.
                  Preorder, inorder, postorder traversal follows the following traversal.
Preorder Traversal: Root-Left-Right
Inorder Traversal: Left-Root-Right
Postorder Traversal: Left-Right-Root 

                  Go through the following program:



Program: (treetraversal.c)
#include<stdlib.h>
#include<stdio.h>

/* We will consider Strict Binary Tree where each node has zero or two children */

struct binarytree
{
char data;
struct binarytree *left, *right;
};
typedef struct binarytree node;

/* insertnode() and insert() functions are for adding nodes to tree */

void insertnode(node **tree,char val)
{
node *temp = NULL;

if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
    }
}

void insert(node **tree,char val)
{
    char l,r;
    int numofchildren;

    insertnode(tree, val);

    printf("\nEnter number of children of %c:",val);
    scanf("%d",&numofchildren);

  if(numofchildren==2)
   {
    printf("\nEnter Left Child of %c:",val);
    scanf("%s",&l);
    insertnode(&(*tree)->left,l);

    printf("\nEnter Right Child of %c:",val);
    scanf("%s",&r);
    insertnode(&(*tree)->right,r);
 
    insert(&(*tree)->left,l);
    insert(&(*tree)->right,r);
   }
}

/* function preorder() will print preorder of nodes. */

void preorder(node * tree)
{
    if (tree)
    {
        printf("%c  ",tree->data);
    preorder(tree->left);
        preorder(tree->right);
    }
}

/* function inorder() will print inorder of nodes. */

void inorder(node * tree)
{
    if (tree)
    {
        inorder(tree->left);
        printf("%c  ",tree->data);
        inorder(tree->right);
    }
}

/* function postorder() will print inorder of nodes. */

void postorder(node * tree)
{
    if (tree)
    {
        postorder(tree->left);
        postorder(tree->right);
    printf("%c  ",tree->data);
    }
}


/* deletetree() will free the memory allocated for tree */

void deletetree(node * tree)
{
    if (tree)
    {
        deletetree(tree->left);
        deletetree(tree->right);
        free(tree);
    }
}

/* Program execution will start from main() function */

void main()
{
    node *root;
    root = NULL;
    node *tmp;
    char val;
    int i,temp;
  
    /* Inserting nodes into tree(DAG) */

    printf("\nEnter root of tree:");
    scanf("%c",&val);

    insert(&root,val);

    /* Printing preorder of nodes of tree(DAG) */
    printf("\nPreorder Display:\n");
    preorder(root);

    /* Printing inorder of nodes of tree(DAG) */
    printf("\nInorder Display:\n");
    inorder(root);

    /* Printing postorder of nodes of tree(DAG) */
    printf("\nPostorder Display:\n");
    postorder(root);

    printf("\n");
        
    /* Deleting all nodes of tree */
    deletetree(root);
}



How To Run:
To Compile:
>>>gcc treetraversal.c

To Run:
>>>./a.out

Output:
For above tree, Preorder, Inorder and Postorder will be found out as follows:

Next: Finding Prime Numbers Between 1 to n in Optimized Way

Previous: How to reverse a Linked List in C Language




No comments:

Post a comment