This blog is under construction

Sunday, 3 March 2013

C Program To Implement Binary Tree Traversals - In-order, Pre-order and Post-order

Tree traversal is the process of visiting all the nodes in a tree in a specific order.  There are three types of tree traversals.
  • Pre-Order Traversal
  • Post Order Traversal
  • In-order Traversal

Pre-order Traversal:
  • Visit the root node.
  • Recursively traverse left sub-tree(in pre-order).
  • Recursively traverse right sub-tree(in pre-order).

Algorithm for Pre-Order tree traversal:
void preorder(Treenode T) {
          if (T == NULL)
               return;
           printData(T->data);
           preorder(T->left);
           preorder(T->right);
           return;
}


Example:
                                   *
                                /      \
                              +         -
                            /   \      /  \
                           A    B    C   D

Step 1: Visit root node and store the key '*' to output.
Output: *

Step 2: Recursively traverse left subtree of '*'

                        +
                       /  \
                      A   B     Preorder traversal: + A B

Output: * + A B

Step 3: Recursively traverse right subtree of '*'

                         -
                       /  \
                      C   D     Preorder traversal: - C D

Output: * + A B - CD

Preorder:  * + A B - C D

Post Order Traversal:
  • Recursively traverse left subtree(in post order).
  • Recursively traverse right subtree(in post order).
  • Visit the root node.

Algorithm for Post order tree traversal:
void postorder(Treenode T) {
          if (T == NULL)
               return;
           postorder(T->left);
           postorder(T->right);
           printData(T->data);
           return;
}

Example:
                                   *
                                /      \
                              +         -
                            /   \      /  \
                           A    B    C   D

Preorder: A B + C D - *



Inorder Traversal:
  • Recursively traverse left subtree(inorder).
  • Visit the root node.
  • Recursively traverse right subtree(inorder).

Algorithm for Inorder tree traversal:
void inorder(Treenode T) {
          if (T == NULL)
               return;
           inorder(T->left);
           printData(T->data);
           inorder(T->right);
           return;
}



Example:
                                   *
                                /      \
                              +         -
                            /   \      /  \
                           A    B    C   D

Inorder: A + B * C - D

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs


Example Program For Binary Tree Traversals - Post-order, Pre-order, In-order):



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

  struct tnode {
        int data;
        struct tnode *left, *right;
  };

  struct tnode *root = NULL;

  /* creating node of the tree  and fill the given data */
  struct tnode * createNode(int data) {
        struct tnode *newNode;
        newNode  = (struct tnode *) malloc(sizeof(struct tnode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return (newNode);
  }

  /* inserting a new node into the tree */
  void insertion(struct tnode **node, int data) {
        if (!*node) {
                *node = createNode(data);
        } else if (data < (*node)->data) {
                insertion(&(*node)->left, data);
        } else if (data > (*node)->data) {
                insertion(&(*node)->right, data);
        }
  }

  /* post order tree traversal */
  void postOrder(struct tnode *node) {
        if (node) {
                postOrder(node->left);
                postOrder(node->right);
                printf("%d  ", node->data);
        }
        return;
  }

  /* pre order tree traversal */
  void preOrder(struct tnode *node) {
        if (node) {
                printf("%d  ", node->data);
                preOrder(node->left);
                preOrder(node->right);
        }
        return;
  }

  /* inorder tree traversal */
  void inOrder(struct tnode *node) {
        if (node) {
                inOrder(node->left);
                printf("%d  ", node->data);
                inOrder(node->right);
        }
        return;
  }

  int main() {
        int data, ch;
        while (1) {
                printf("\n1. Insertion\n2. Pre-order\n");
                printf("3. Post-order\n4. In-order\n");
                printf("5. Exit\nEnter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter ur data:");
                                scanf("%d", &data);
                                insertion(&root, data);
                                break;
                        case 2:
                                preOrder(root);
                                break;
                        case 3:
                                postOrder(root);
                                break;
                        case 4:
                                inOrder(root);
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("U've entered wrong opetion\n");
                                break;
                }
        }
        return 0;
  }


Input Tree:
                                                     20
                                                   /      \
                                                  15     30
                                                /       /   \
                                               8       25   40
                                                             \
                                                 10


  Output: (Binary Tree Traversal - Inorder, Postorder & Preorder)
  jp@jp-VirtualBox:$ ./a.out
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:20
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:15
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:8
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:10
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:30
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:25
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:1
  Enter ur data:40
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:2
  20  15  8  10  30  25  40  
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:3
  10  8  15  25  40  30  20  
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:4
  8  10  15  20  25  30  40  
  1. Insertion
  2. Pre-order
  3. Post-order
  4. In-order
  5. Exit
  Enter your choice:5




No comments:

Post a Comment