TAOCP 2.3.3 Exercise 6
Let the nodes be linked initially by the arbitrary linear list \text{FIRST} \to x_1 \to x_2 \to \cdots \to x_n \to \Lambda, through their present `RLINK` fields.
Section 2.3.3: Other Representations of Trees
Exercise 6. [24] Suppose that the nodes of an oriented forest have three link fields, PARENT, LCHILD, and RLINK, but only the PARENT link has been set up to indicate the tree structure. The LCHILD field of each node is Λ and the RLINK fields are set as a linear list that simply links the nodes together in some order. The link variable FIRST points to the first node, and the last node has RLINK = Λ.
Design an algorithm that goes through these nodes and fills in the LCHILD and RLINK fields compatible with the PARENT links, so that a triply linked tree representation like that in Fig. 26 is obtained. Also, reset FIRST so that it now points to the root of the first tree in this representation.
Verified: yes
Solve time: 1m20s
Solution
Let the nodes be linked initially by the arbitrary linear list
$$ \text{FIRST} \to x_1 \to x_2 \to \cdots \to x_n \to \Lambda, $$
through their present RLINK fields. The PARENT fields already define the oriented forest. The task is to replace the temporary linear-list links by the proper triply linked tree structure.
The essential fact is that, for every node $y$,
$$ \text{LCHILD}(y) $$
must point to the leftmost child of $y$, and for children of the same parent,
$$ c_1,c_2,\ldots,c_k, $$
listed from left to right, we must have
$$ \text{RLINK}(c_i)=c_{i+1}\qquad(1\le i<k), $$
and
$$ \text{RLINK}(c_k)=\Lambda. $$
Since only the PARENT links are available, we first collect the children of each parent into a list. The existing RLINK fields may be used temporarily for this purpose.
The following algorithm requires no auxiliary storage beyond a few link variables.
A1. [Initialize.] Let
$$ P\leftarrow \text{FIRST}. $$
A2. [Clear child lists.] Traverse the linear list. For each node $P$ set
$$ \text{LCHILD}(P)\leftarrow\Lambda, $$
then advance to the next node by the old linear-list link. When the end of the list is reached, proceed to A3.
After A2 every LCHILD field is null.
A3. [Build lists of children.] Set
$$ P\leftarrow \text{FIRST}. $$
Process the nodes in the original linear-list order. For each node let
$$ Q\leftarrow \text{PARENT}(P). $$
If $Q\ne\Lambda$, perform
$$ \text{RLINK}(P)\leftarrow \text{LCHILD}(Q), $$
$$ \text{LCHILD}(Q)\leftarrow P. $$
Then advance to the next node of the original linear list. Continue until all nodes have been processed.
At the end of A3, for every parent $Q$, the field LCHILD(Q) points to a chain of all children of $Q$. Because each new child is inserted at the front, this chain contains the children in reverse order of their appearance in the original list.
A4. [Reverse each child list.] Traverse all nodes again. For each node $Q$, reverse the linked list beginning at LCHILD(Q) in the usual manner, using the RLINK field as the link. Replace LCHILD(Q) by the first node of the reversed list.
After A4, for every node $Q$, LCHILD(Q) points to its leftmost child and successive RLINKs connect siblings from left to right.
A5. [Find the first root.] Set
$$ P\leftarrow \text{FIRST}. $$
Scan the original node sequence until the first node with
$$ \text{PARENT}(P)=\Lambda $$
is encountered. Set
$$ \text{FIRST}\leftarrow P. $$
Terminate.
It remains to prove correctness.
During A3, every node $P$ with parent $Q$ is inserted exactly once into the list headed by LCHILD(Q). Hence, after A3, the nodes appearing in the list headed by LCHILD(Q) are precisely the children of $Q$, and no node appears in the child list of any other parent.
During A4, each such list is reversed. Therefore the children of every parent are arranged in the same relative order in which they were encountered in the original node sequence. The resulting links satisfy the definition of the triply linked tree representation: LCHILD(Q) points to the leftmost child of $Q$, and the RLINK fields connect successive siblings from left to right, ending with $\Lambda$.
The PARENT fields are never altered, so the parent-child relation remains exactly the one originally specified.
A root is characterized by
$$ \text{PARENT}=\Lambda. $$
Step A5 selects the first root encountered in the node sequence and makes FIRST point to it. This is precisely the required root of the first tree.
Each node is processed a constant number of times, and every reversal step handles each sibling link exactly once. Therefore the total running time is linear in the number of nodes,
$$ \Theta(n). $$
The algorithm produces a triply linked tree representation compatible with the given PARENT links and resets FIRST to the root of the first tree. ∎