C Programming Code Examples C > Beginners Lab Assignments Code Examples Program to Build Binary Tree if Inorder or Postorder Traversal as Input Program to Build Binary Tree if Inorder or Postorder Traversal as Input /* * * 40 * / \ * 20 60 * / \ \ * 10 30 80 * \ * 90 * (Given Binary Search Tree) */ #include <stdio.h> #include <stdlib.h> struct btnode { int value; struct btnode *l; struct btnode *r; }*root = NULL, *temp = NULL; typedef struct btnode N; void insert(); N* bt(int arr[],int,int); N* new(int); void inorder(N *t); void create(); void search(N *t); void preorder(N *t); void postorder(N *t); void main() { int ch, j, n; int arr[] = {10, 20, 30, 40, 60, 80, 90}; n = sizeof(arr) / sizeof(arr[0]); printf("\n1- Inorder\n"); printf("2 - postorder\n"); printf("\nEnter choice : "); scanf("%d", &ch); switch (ch) { case 1: root = bt(arr, 0, n-1); printf("Given inorder traversal as input\n"); for (j = 0;j< = 6;j++) printf("%d->", arr[j]); printf("\npreorder traversal of tree\n"); preorder(root); printf("\ninorder traversal of tree\n"); inorder(root); printf("\npostorder traversal of tree\n"); postorder(root); break; case 2: insert(); printf("\npreorder traversal of tree\n"); preorder(root); printf("\nInorder traversal of tree\n"); inorder(root); printf("\npostorder traversal of tree\n"); postorder(root); break; default:printf("enter correct choice"); } } /* To create a new node */ N* new(int val) { N* node = (N*)malloc(sizeof(N)); node->value = val; node->l = NULL; node->r = NULL; return node; } /* To create a balanced binary search tree */ N* bt(int arr[], int first, int last) { int mid; N* root = (N*)malloc(sizeof(N)); if (first > last) return NULL; mid = (first + last) / 2; root = new(arr[mid]); root->l = bt(arr, first, mid - 1); root->r = bt(arr, mid + 1, last); return root; } /* Insert a node in the tree */ void insert() { int arr1[] = {10, 30, 20, 90, 80, 60, 40}, j; printf("Given post order traversal array\n"); for (j = 0;j <= 6;j++) { printf("%d->", arr1[j]); } for (j = 6;j >= 0;j--) { create(arr1[j]); if (root = = NULL) root = temp; else search(root); } } /*Create a node */ void create(int data) { temp = (N *)malloc(1*sizeof(N)); temp->value = data; temp->l = temp->r = NULL; } /* Search for the appropriate position to insert the new node */ void search(N *t) { if ((temp->value>t->value)&&(t->r != NULL)) search(t->r); else if ((temp->value>t->value)&&(t->r == NULL)) t->r = temp; else if ((temp->value<t->value)&&(t->l != NULL)) search(t->l); else if ((temp->value<t->value)&&(t->l == NULL)) t->l = temp; } /* to display inorder of tree */ void inorder(N *t) { if (t->l != NULL) inorder(t->l); printf("%d->", t->value); if (t->r != NULL) inorder(t->r); } /* to display preorder traversal of tree */ void preorder(N *t) { printf("%d->", t->value); if (t->l != NULL) inorder(t->l); if (t->r != NULL) inorder(t->r); } /* to display postorder traversal of tree */ void postorder(N *t) { if (t->l != NULL) inorder(t->l); if (t->r != NULL) inorder(t->r); printf("%d->", t->value); }
