Data Structures, Algorithms, & Applications in C++
Chapter 11, Exercise 35
Suppose we are told that the postorder and inorder listings of
a binary tree are postList[0:6] =
[5, 3, 1, 6, 4, 2, 0] and inList[0:6] =
[3, 5, 1, 0, 2, 6, 4].
From the definition of postorder we know that postlist[6] = 0
is the root. From the definition of inorder we know that in inorder the
root is preceded by its left subtree and followed by its right subtree.
So inList[0:2] is the inorder listing of the
left subtree and
inList[4:6] is the inorder listing of the
right subtree. The left and right subtrees can now be constructed
recursively using this information.
It is convenient to construct the right subtree first because
when we scan the postorder listing from right to left, we
first encounter the nodes in the right subtree and then the nodes in
the left subtree.
To implement the above strategy efficiently it is useful
to construct an array inMap[]
with the property that inMap[i]
gives the location of postList[i] in
inList[i]. For the example above
inMap[0:6] = [1, 0, 2, 5, , 4, 3].
This mapping array enables us to quickly find the location of
postList[i] in
inList[].
If we make the assumption that the data elements of an
n node binary tree are 0, 1, ...,
n-1, we can construct inMap
in linear time as below.
// construct inMap
// first construct inverse of InList
int *inverse = new int [n];
for (int i = 0; i < n; i++)
inverse[inList[i]] = i;
// now construct inMap
for (int i = 0; i < n; i++)
inMap[i] = inverse[postList[i]];
When we cannot make this assumption we can construct
inMap by sorting both
inList and
postList. This sort will take linear time
if the range of data values is small (in this case bin sort
(see Chapter 6) can be used) and the sort will take
O(n log n) time
when we must sort using the general purpose sorts of Chapters 12 (heap
sort) and 18 (merge sort).