为什么说森林的中序遍历对应的是二叉树的中序遍历。按照图中不是应该对应森林的后序遍历吗？

Question

如题所述

Answer 1

首先，需要明确一点，森林和二叉树是两种不同的数据结构。森林是一种由多个树组成的数据结构，而二叉树是一种特定的树结构，其中每个节点最多有两个子节点。
在讨论中序遍历时，我们通常指的是二叉树的中序遍历。中序遍历的顺序是先遍历左子树，然后遍历根节点，最后遍历右子树。
对于森林来说，由于它包含多个树，因此不能直接应用二叉树的中序遍历。但是，如果我们把森林中的每一棵树都看作是一个二叉树，那么森林的中序遍历就可以对应到二叉树的中序遍历。
换句话说，当我们对森林进行中序遍历时，我们实际上是先遍历每一棵树的左子树（对应二叉树左子树的遍历），然后遍历根节点（对应二叉树的根节点的遍历），最后遍历每一棵树的右子树（对应二叉树右子树的遍历）。
因此，说森林的中序遍历对应的是二叉树的中序遍历是有一定道理的。
至于你提到的图中对应的后序遍历，我不太清楚你指的是哪个图。但是，无论是在二叉树还是森林中，后序遍历的顺序都是先遍历左子树，然后遍历右子树，最后遍历根节点。这与中序遍历的顺序是不同的。

Answer 2

你得到的树其实已经是把之前得到的二叉树转化为一个普通的树了，虽然刚好这棵树也是二叉树。准确的表述是二叉树森林的中序遍历与完整二叉树中序遍历对应。追问

图左边不是完整二叉树吗 右边是不是二叉树森林吗 为啥他俩中序遍历不一样 你这个表述是啥意思？

追答

直接拆掉右孩子的连线得到的就已经是一个完备的二叉树森林了，后面的转化是为了将森林中的二叉树转化为树。完整二叉树的中序遍历与二叉树森林的中序遍历相同，也与森林的后根遍历相同

本回答被网友采纳

Answer 3

看看树的非递归算法，你就明白了

Answer 4