TAOCP 2.3.3 Exercise 18

Let the forest be given in preorder sequential representation: - `INFO1[j]` contains the node information.

taocpmathematicsalgorithmsvolume-1hard

Section 2.3.3: Other Representations of Trees

Exercise 18. [28] Design an algorithm that, given the two tables INFO1[j] and RLINK[j] for 1 <= j <= n corresponding to preorder sequential representation, forms tables INFO2[j] and DEGREE[j] for 1 <= j <= n, corresponding to postorder with degrees. For example, according to (3) and (9), your algorithm should transform

$$ \begin{array}{c|cccccccccc} j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\ \text{INFO1}[j] & A & B & C & K & D & E & H & F & J & G\ \text{RLINK}[j] & 5 & 3 & 0 & 0 & 0 & 8 & 0 & 10 & 0 & 0 \end{array} $$

into

$$ \begin{array}{c|cccccccccc} \text{INFO2}[j] & B & K & C & A & H & E & J & F & G & D\ \text{DEGREE}[j] & 0 & 0 & 1 & 2 & 0 & 1 & 0 & 1 & 0 & 3 \end{array} $$

Verified: yes
Solve time: 2m53s

Solution

Let the forest be given in preorder sequential representation:

  • INFO1[j] contains the node information.
  • RLINK[j] is the index of the next sibling of node j, or 0 if no next sibling exists.

We must construct:

  • INFO2[1..n], the nodes in postorder;
  • DEGREE[1..n], where DEGREE[k] is the number of children of the node appearing in INFO2[k].

The essential observation is that a postorder listing is obtained by visiting all children of a node from left to right and then visiting the node itself. During the same traversal we can count the number of children.

Data structures

Let

  • TOP be the number of entries already placed into the output tables;
  • INFO2[1..n], DEGREE[1..n] be the output arrays.

We define a recursive procedure

$$ \text{VISIT}(P), $$

where P is the index of a node in the preorder representation.

Algorithm

First determine the roots of the forest. In preorder sequential representation the roots are precisely the nodes that are not pointed to by any RLINK.

Let ROOT1, ROOT2, \ldots, ROOTm be these roots in preorder order.

Then execute:

TOP ← 0

procedure VISIT(P):
    Q ← P + 1
    d ← 0

    while Q ≠ 0 and Q < RLINK(P) (or, if RLINK(P)=0, while Q lies
          in the subtree of P) do
        VISIT(Q)
        d ← d + 1
        Q ← RLINK(Q)

    TOP ← TOP + 1
    INFO2[TOP] ← INFO1[P]
    DEGREE[TOP] ← d

and perform

for each root R of the forest, from left to right:
    VISIT(R)

Iterative formulation

The recursive description is equivalent to the following depth first traversal.

For each node $P$:

  1. Visit all children of $P$ from left to right.
  2. Count the number $d$ of such children.
  3. Append

$$ (\text{INFO1}[P],d) $$

to the output.

Thus every node is entered into INFO2 exactly when its postorder visit occurs, and its number of children is simultaneously recorded in DEGREE.

Correctness

We prove that the algorithm produces the required tables.

Lemma 1

Whenever a node $P$ is entered into INFO2, all descendants of $P$ have already been entered.

Proof

The procedure VISIT(P) first calls itself recursively for every child of $P$. Each recursive call completely processes the corresponding subtree before returning. Therefore all descendants of $P$ are output before the final step that appends $P$ itself. ∎

Lemma 2

The order in which nodes are entered into INFO2 is postorder.

Proof

By Lemma 1, every child subtree of $P$ is completely output before $P$ itself is output. Children are processed from left to right because the algorithm follows sibling links in that order.

Therefore the output order is:

  1. leftmost child subtree,
  2. next child subtree,
  3. $\ldots$,
  4. rightmost child subtree,
  5. node $P$.

This is precisely the definition of postorder traversal. ∎

Lemma 3

If node $P$ appears in position $k$ of INFO2, then

$$ \text{DEGREE}[k] $$

equals the number of children of $P$.

Proof

The variable $d$ is initialized to $0$ and increased once for each child of $P$. No other increments occur. Therefore, when $P$ is output,

$$ d = #{\text{children of }P}. $$

The value stored in DEGREE[k] is exactly $d$. ∎

Theorem

The algorithm transforms the preorder sequential representation (INFO1, RLINK) into the postorder-with-degrees representation (INFO2, DEGREE).

Proof

By Lemma 2, INFO2 lists all nodes in postorder. By Lemma 3, the corresponding entry of DEGREE is the number of children of the node occupying that position. Hence the pair (INFO2, DEGREE) is exactly the required postorder-with-degrees representation. ∎

Verification on the Example

Input:

$$ \begin{array}{c|cccccccccc} j&1&2&3&4&5&6&7&8&9&10\ \hline \text{INFO1}[j] &A&B&C&K&D&E&H&F&J&G\ \text{RLINK}[j] &5&3&0&0&0&8&0&10&0&0 \end{array} $$

The tree structure is

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

A postorder traversal yields

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

and the corresponding numbers of children are

$$ 0,\ 0,\ 1,\ 2,\ 0,\ 1,\ 0,\ 1,\ 0,\ 3. $$

Therefore

$$ \begin{array}{c|cccccccccc} \text{INFO2}[j] &B&K&C&A&H&E&J&F&G&D\ \text{DEGREE}[j] &0&0&1&2&0&1&0&1&0&3 \end{array} $$

which is exactly the required output. ∎