|
6.6.4 森林和二叉树的转换
假设森林
F = { ,,
…,
},
其中第一棵树由根结点
ROOT()
和子树森林 {,
,
…, }
构成。
则可按如下规则转换成一棵二叉树
B =( LBT, Node(root), RBT ):
若森林 F 为空集,则二叉树 B 为空树;否则,由森林中第一棵树的根结点 ROOT()
复制得二叉树的根 Node(root),由森林中第一棵树的子树森林 {,
,
…, }
转换得到二叉树中的左子树LBT,由森林中删去第一棵树之后由其余树构成的森林 {,,…,
} 转换得到二叉树中的右子树RBT。
反之,对于任意一棵二叉树
B =( LBT, Node(root), RBT ),
可按如下规则转换得到由n 棵树构成的森林
F = { ,
,
…,
},
其中第一棵树
由根结点 ROOT()
和子树森林 {,
,
…, }
构成:
若二叉树 B 为空树, 则与其对应的森林 F 为空集;否则,由二叉树的根结点 Node(root) 复制得森林中第一棵树的根结点 ROOT(),由二叉树中的左子树
LBT 转换构造森林中第一棵树的子树森林 {,
,
…, },由二叉树中的右子树
RBT 转换构造森林中其余树构成的森林 {,,…,}。
由此,对树和森林进行的各种操作均可通过对"二叉树"进行相应的操作来完成,但同时也必须注意,此时的"二叉树",其左、右子树和根结点之间的关系不再是它的"左、右孩子",而是左子树是根的"孩子们",右子树是根的"兄弟们"。 |
|
|
|