facebook like button

14 October, 2011

Inorder, Preorder and Post-Order traversal of tree

The need:
     This program is written to show the program implementation of the concept explained in the previous post. This program is the implementation of 2 + 3 example given there.
The code:
----------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
struct tree
{
    char num;
    struct tree *left, *right, *parent;
};
typedef struct tree node;

void in_print(node *p);
void pre_print(node *p);
void post_print(node *p);
node * create_node(char c);
int main()
{
    int i;
    node *root=NULL;
    root = create_node('+');
    root->left = create_node('a');
    root->right = create_node('b');
    printf("Pre order print\t\t");
    pre_print(root);
    printf("\nIn order print\t\t");
    in_print(root);
    printf("\nPost order print\t");
    post_print(root);
    putchar('\n');
    return 0;
}

node * create_node(char c)
{
    node *new_node;
    new_node = (node *)malloc(sizeof(node));
    new_node->num = c;
    new_node->parent = NULL;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void pre_print(node *p)
{
    if(p==NULL)
    return;
    else
    printf("%c ",p->num);
    pre_print(p->left);
    pre_print(p->right);
}

void in_print(node *p)
{
    if(p==NULL)
    return;
    else
    in_print(p->left);
    printf("%c ",p->num);
    in_print(p->right);
}

void post_print(node *p)
{
    if(p==NULL)
    return;
    else
    post_print(p->left);
    post_print(p->right);
    printf("%c ",p->num);
}
----------------------------------------------------------
Approach:
    This program is just to show the printing of a tree in pre-order, inorder and post order. For that first we have to make the tree. Here I have not created a bigger tree. Here we have the simplest tree with 3 nodes only. So we need not make a function to construct the tree. Here simply I have created 3 nodes and put them to make a small tree. create_node() function creates a node with given data/value ans returns it address. we create first node, make it root. After that we create 2 more nodes and make them left and right children of root. Then there are 3 functions in_print(), pre_print() and post_print() which print the expression in infix, prefix and postfix form respectively.
Remarks:
1. Here this program is shown to print the simplest expression in prefix, infix and post-fix form but this program can be used to print any binary tree in pre-order, inorder and post order.
2. This program is the base of all the tree programs related to trees.

4 comments:

  1. thank you very much...and i still confuse

    ReplyDelete
  2. In which function is the elements added to tree ??
    can u give Output example of this program

    ReplyDelete
    Replies
    1. This program is intended to traverse and print a tree. So I didn't create a bigger tree. The tree used in this demonstration is small and has been constructed manually on lines 18,19,20 of the above program.

      Delete

feel free to ask your doubts... if any
you can post your doubts on
www.facebook.com/programsimply