为什么森林的中序是等于森林的后根的?

enliven 2026-07-01 11:13 1

为什么森林的中序是等于森林的后根的?中序访问根不应该是在中间步骤的时候访问,后根应该根节点是在最后的时候访问啊?

最新回复 (3)
  • 卡里姆•汗 07-01 11:30
    1

    这种事情应该问ai的,佬友没有这个水平(

  • cwxiaos 07-01 12:15
    2


    忘干净了,不过应该能给个参考


    因为森林和树转为二叉树都遵循:


    一个节点的兄弟都转为这个节点的右child

    一个节点的第一个child转为这个节点的左child


    因此如果先根,一个节点先于child遍历,在二叉树中就是先序


    如果后根,一个节点晚于所有child,但在对应二叉树中,这个节点的child都在其左child中,因此使用inorder让这个节点在最后

  • Vincent X 07-01 12:52
    3

    这里森林的【中序遍历】指的是由该森林转化而来的二叉树的中序遍历。中序遍历本身是在二叉树中定义的概念,树和森林定义的是【先根遍历】和【后根遍历】(这也和原题描述一致)。所以森林的后根遍历和中序遍历(按照前述定义)是一致的。另外可以参考数据结构教材上森林的中序遍历是怎么回事?。

* 帖子来源Linux.do
返回