The tree is a data structure, and the binary tree is the most important one of the tree. All trees can find a two-fork tree. From physical storage structures, their two-stranded tables are the same, but they are different from the perspective of explanation.
First, the forest is converted to the tree
If f = {t
1, T
2, ..., t
N} is a forest, converted to a binary tree B = {root, lb, rb} as follows.
(1) If f is empty, ie M = 0, then B is empty tree.
(2) If f is fly empty, 即 m ≠ 0, then the root root of B is root root of the first tree of the forest (T
1); the left subtree LB of B is from T
1 Submerged forest f
1 = {T
11, T
12, ..., t
1M1} converted the binary tree; its right tree RB is from the forest f
'= {T
2, T
3, ..., t
Two-fork trees converted by M}.
Second, the binary tree is converted to the forest
If b = (root, lb, rb) is a binary tree, you can press rule to convert to the forest.
(1) If B is empty, f is empty
(2) If b is non-empty, the first tree T in F
1 root root (t
1) is a binary root root; T
Sub forest f
1 is converted from the left sub-LB of B to the forest; in addition to T
1 Outside the remaining tree, forest f
'= {T
2, T
3, ..., t
M} is a forest converted from the right sub-tree RB of B.
