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)
How To Run:
To Compile:
>>>gcc treetraversal.c
To Run:
>>>./a.out
Output:
Next: Finding Prime Numbers Between 1 to n in Optimized Way
Previous: How to reverse a Linked List in C Language
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