Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, "a" is the root of the tree; "gdhbei" are in the left subtree; "fjc" are in the right subtree. "b" is the next root; "gdh" are in the left subtree; "ei" are in the right subtree. "d" is the next root; "g" is in the left subtree; "h" is in the right subtree.
For Inorder and Postorder traversals
Scan postorder from right to left using inorder to separate left and right subtrees.
inorder = g d h b e i a f j c
postorder = g h d i e b j f c a
Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.
For Inorder and Levelorder traversals
Scan level order from left to right using inorder to separate left and right subtrees.
inorder = g d h b e i a f j c
level order = a b c d e f g h i j
Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.
Here is some working code which creates a tree out of the Inorder and Postorder
traversals. Note that here the tree has been represented as an array. This really simplifies the whole implementation.
Converting a tree to an array is very easy
Suppose we have a tree like this
A
B C
D E F G
The array representation would be
a[1] a[2] a[3] a[4] a[5] a[6] a[7]
A B C D E F G
That is, for every node at position j in the array, its left child will be stored at position (2*j) and right child at (2*j + 1). The root starts at position 1.
// CONSTRUCTING A TREE GIVEN THE INORDER AND PREORDER SEQUENCE
#include
#include
#include
/*-------------------------------------------------------------
* Algorithm
*
* Inorder And Preorder
* inorder = g d h b e i a f j c
* preorder = a b d g h e i c f j
* Scan the preorder left to right using the inorder to separate left
* and right subtrees. a is the root of the tree; gdhbei are in the
* left subtree; fjc are in the right subtree.
*------------------------------------------------------------*/
static char io[]="gdhbeiafjc";
static char po[]="abdgheicfj";
static char t[100][100]={'\0'}; //This is where the final tree will be stored
static int hpos=0;
void copy_str(char dest[], char src[], int pos, int start, int end);
void print_t();
int main(int argc, char* argv[])
{
int i,j,k;
char *pos;
int posn;
// Start the tree with the root and its
// left and right elements to start off
for(i=0;i
