Data Structures, Algorithms, & Applications in C++
Chapter 11, Exercise 33
Suppose we are told that the preorder and inorder listings of
a binary tree are preList[0:6] =
[0, 1, 3, 5, 2, 4, 6] and inList[0:6] =
[3, 5, 1, 0, 2, 6, 4].
From the definition of preorder we know that prelist[0]
= 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.
To implement the above strategy efficiently it is useful
to construct an array inMap[]
with the property that inMap[i]
gives the location of preList[i] in
inList[i]. For the example above
inMap[0:6] = [3, 2, 0, 1, 4, 6, 5].
This mapping array enables us to quickly find the location of
preList[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[preList[i]];
When we cannot make this assumption we can construct
inMap by sorting both
inList and
preList. 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).