Users Online
· Guests Online: 96
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Newest Threads
No Threads created
Hottest Threads
No Threads created
Latest Articles
Articles Hierarchy
C Program to Build Binary Tree if Inorder or Postorder Traversal as Input
Here is source code of the C Program to Build Binary Tree if Inorder or Postorder Traversal as Input. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C 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, i, 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 (i = 0;i< = 6;i++)
printf("%d->", arr[i]);
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}, i;
printf("Given post order traversal array\n");
for (i = 0;i <= 6;i++)
{
printf("%d->", arr1[i]);
}
for (i = 6;i >= 0;i--)
{
create(arr1[i]);
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->valuevalue)&&(t->l != NULL))
search(t->l);
else if ((temp->valuevalue)&&(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);
}
$ cc trees.c
$ a.out
1- Inorder
2 - postorder
Enter choice : 1
Given inorder traversal as input
10->20->30->40->60->80->90
preorder traversal of tree
40->10->20->30->60->80->90
inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40
$ a.out
1 - Inorder
2 - postorder
Enter choice : 2
Given post order traversal array
10->30->20->90->80->60->40
preorder traversal of tree
40->10->20->30->60->80->90
Inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40
/*
* C 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, i, 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 (i = 0;i< = 6;i++)
printf("%d->", arr[i]);
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}, i;
printf("Given post order traversal array\n");
for (i = 0;i <= 6;i++)
{
printf("%d->", arr1[i]);
}
for (i = 6;i >= 0;i--)
{
create(arr1[i]);
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
search(t->l);
else if ((temp->value
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);
}
$ cc trees.c
$ a.out
1- Inorder
2 - postorder
Enter choice : 1
Given inorder traversal as input
10->20->30->40->60->80->90
preorder traversal of tree
40->10->20->30->60->80->90
inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40
$ a.out
1 - Inorder
2 - postorder
Enter choice : 2
Given post order traversal array
10->30->20->90->80->60->40
preorder traversal of tree
40->10->20->30->60->80->90
Inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40
Comments
No Comments have been Posted.
Post Comment
Please Login to Post a Comment.