Assignment 8
The exercise
Consider a binary tree with each node carrying a (unique) label. In-order and pre-order listings of these labels are defined by the following recursive procedures:
inorder ( node )
{
if (node != NULL) {
inorder(left child of node);
print(label of node);
inorder(right child of node);
}
}
preorder ( node )
{
if (node != NULL) {
print(label of node);
preorder(left child of node);
preorder(right child of node);
}
}
A binary tree and the in-order and pre-order listings of the labels of
its nodes are shown in the following figure:
Given the in-order and pre-order listings for a binary tree, the tree can be uniquely reconstructed using the following recursive algorithm:
construct ( inlist , prelist )
{
if (inlist and prelist are both non-empty) {
create a new node;
set the label of the new node to be the first label of prelist;
locate this label in inlist;
let m be the number of labels in inlist before this location;
let n be the number of labels in inlist after this location;
let leftinlist be the first m labels of inlist;
let rightinlist be the last n labels of inlist;
let leftprelist be the second through (m+1)st labels of prelist;
let rightprelist be the last n labels of prelist;
left child of new node = construct (leftinlist, leftprelist);
right child of new node = construct (rightinlist, rightprelist);
return(new node);
}
return(NULL);
}
Implement this construct procedure. Read the inlist and prelist from the user, construct the tree and print it.
Sample output
Inorder listing : bfdgaehc Preorder listing : abdfgceh Node : a, Left child : b, Right child : c. Node : b, Left child : NULL, Right child : d. Node : d, Left child : f, Right child : g. Node : f, Left child : NULL, Right child : NULL. Node : g, Left child : NULL, Right child : NULL. Node : c, Left child : e, Right child : NULL. Node : e, Left child : NULL, Right child : h. Node : h, Left child : NULL, Right child : NULL.
Test input
Show the output of your program on the following inputs:Inorder listing : GDHBAECF Preorder listing : ABDGHCEF Inorder listing : abcdefghijkl Preorder listing : abcdefghijkl Inorder listing : abcdefghijkl Preorder listing : lkjihgfedcba Inorder listing : abcdefghijkl Preorder listing : badcfehgjilk Inorder listing : cbafedihglkj Preorder listing : abcdefghijkl Inorder listing : abcdefghijkl Preorder listing : bcdefghijkla Inorder listing : bcdefghijkla Preorder listing : abcdefghijkl Inorder listing : hdibjekalfmcngo Preorder listing : abdhiejkcflmgno Inorder listing : ABCDEFGHIJKLMN Preorder listing : HGFEDCBAIJKLMN Inorder listing : ABCDEFGHIJKLMN Preorder listing : GABCDEFNMLKJIH