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 转换构造森林中其余树构成的森林 {,,…,}。

  由此,对树和森林进行的各种操作均可通过对"二叉树"进行相应的操作来完成,但同时也必须注意,此时的"二叉树",其左、右子树和根结点之间的关系不再是它的"左、右孩子",而是左子树是根的"孩子们",右子树是根的"兄弟们"。
 


 动画