5.9 森林

  • 「森林 forest」n0n \geq 0 个互不相交的树的集合。
  • 『森林转换为二叉树』 如图,将森林转换为二叉树。首先得到森林中每一棵树的二叉树表示(左子结点为儿子结点,右子结点为兄弟结点),然后把每一棵二叉树通过其根结点的兄弟域连接起来。

三棵树的森林

森林的二叉树存储表示

  • 『森林的遍历』
    • 森林 FF 的前序遍历等价于其对应的二叉树 TT 的前序遍历:
      1. 如果 FF 为空,则返回。
      2. 访问 FF 的第一棵树的根结点。
      3. 按前序顺序遍历第一棵树的全部子树。
      4. 按前序顺序遍历 FF 的其余的树。
    • 森林 FF 的中序遍历等价于其对应的二叉树 TT 的中序遍历:
      1. 如果 FF 为空,则返回。
      2. 按中序顺序遍历第一棵树的全部子树。
      3. 访问第一棵树的根结点。
      4. 按中序顺序遍历其余的树。
    • 森林 FF 的后序遍历:(不等价与对应二叉树的后序遍历)
      1. 如果 FF 为空,则返回。
      2. 按后序顺序遍历 FF 的第一棵树的全部子树。
      3. 按后序顺序遍历 FF 的其余的树。
      4. 访问 FF 的第一棵树的根结点。

results matching ""

    No results matching ""