What are the changes in the connections between different nodes during the process of restoring a tree into a binary tree?
The right descendants of the left child of a node x were all originally the siblings of this left child. For example, F and G in →Fig. 1.23 are both descendants of E, while E, F, G were all originally children of B. Therefore, adding line is to restore the relations between a node and its original children; removing line is to remove the connections between the original siblings. In this way, we can restore the original tree structure.
The storage relation between tree and binary tree
In fact, the storage structure established by a tree using child– sibling representation method is exactly the same as the binary linked list storage structure of the corresponding binary tree. We just give different names and meanings to the two pointer fields. →Figure 1.24 straightforwardly shows the correspondence and mutual conversion between tree and binary tree. The tree structure in →Fig. 1.24(a) corresponds to →Fig. 1.24(b), and the form of the corresponding binary linked list is →Fig. 1.24(d). →Figure 1.24(c) and →(e) shows different explanations of →Fig. 1.24(d). For example, in →Fig. 1.24(c), node C is the right sibling of node B, while in →Fig. 1.24(e), node C is the right sibling of node B. Therefore, the related algorithms on binary linked lists can be easily converted to algorithms on child–sibling linked lists of trees.
The relation between tree and binary tree.