TAOCP 2.3.2 Exercise 3

Let the Dewey decimal notation of a node be d_1.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 3. [22] What is the relation between Dewey decimal notation for the nodes of a forest and the preorder and postorder of those nodes?

Verified: yes
Solve time: 1m35s

Solution

Let the Dewey decimal notation of a node be

$$ d_1.d_2.\cdots.d_k, $$

where $d_1$ gives the position of the node among the trees of the forest, $d_2$ gives its position among the children of that tree's root, and so on.

The definitions of preorder and postorder in this section imply simple ordering rules for these Dewey numbers.

For preorder, the root of a tree is visited before all of its descendants, and the descendants are traversed from left to right. Hence a node is visited before every node whose Dewey notation has its notation as a proper prefix. Furthermore, among nodes that are not in an ancestor-descendant relation, the left-to-right traversal visits first the node whose Dewey notation is lexicographically smaller.

Therefore the preorder sequence of the nodes of a forest is obtained by arranging the Dewey decimal notations in lexicographic order. More precisely,

$$ d_1.d_2\ldots d_k $$

precedes

$$ e_1.e_2\ldots e_m $$

in preorder if, at the first position where they differ,

$$ d_i<e_i, $$

or if one notation is a proper prefix of the other and the shorter notation is

$$ d_1.d_2\ldots d_k. $$

For example, the preorder sequence of the forest $(1)$ is

$$ 1,; 1.1,; 1.2,; 1.2.1,; 2,; 2.1,; 2.1.1,; 2.2,; 2.2.1,; 2.3, $$

corresponding to

$$ A,; B,; C,; K,; D,; E,; H,; F,; J,; G. $$

For postorder, all descendants of a node are visited before the node itself. Thus the same left-to-right ordering applies, but every node follows all nodes whose Dewey notations have it as a proper prefix. Consequently the postorder sequence is obtained by the same lexicographic comparison as above, except that when one Dewey notation is a proper prefix of the other, the longer notation comes first.

Equivalently,

$$ d_1.d_2\ldots d_k $$

precedes

$$ e_1.e_2\ldots e_m $$

in postorder if, at the first position where they differ,

$$ d_i<e_i, $$

or if one notation is a proper prefix of the other and the longer notation is

$$ d_1.d_2\ldots d_k. $$

For the forest $(1)$ this gives

$$ 1.1,; 1.2.1,; 1.2,; 1,; 2.1.1,; 2.1,; 2.2.1,; 2.2,; 2.3,; 2, $$

corresponding to

$$ B,; K,; C,; A,; H,; E,; J,; F,; G,; D. $$

Hence the relation is:

  • Preorder corresponds to ordinary lexicographic ordering of Dewey decimal notations.
  • Postorder corresponds to lexicographic ordering with the prefix rule reversed, so that a longer notation precedes any of its proper prefixes.

$$ \boxed{\text{Preorder = lexicographic order; Postorder = lexicographic order with prefixes ordered after their extensions.}} $$