Question

c语言，二叉树的后中序相同，为什么是没有右子树

Answer 1

二叉树后序排列是“左右根”，中序是“左根右”，根就是父节点肯定是有的。如果有右子树，由于两种排序“右”和“根”的顺序不一样，所以一定不同。若后序和中序相同就一定没有右子树

追问

根怎么不是中间？

追答

二叉树排序的规则就是这样的啊，前序是“根左右”，中序是“左根右”，后序是“左右根”

追问

后序是左右根，中后序相同，怎么判右和根的

追答

举个例子，比如如下这棵树

后序是564231    中序是546213

       我们可以通过后序和中序还原这棵树，分如下几步：

      1. 找到后序中最后一个数，这里是1；

      2. 在中序中找到这个数，并通过这个数分成左右两个子树。在这个例子中将中序通过1分成两部分，所以5462是左子树，13是右子树；

      3. 将左右子树的序号分别代入后序中查找那个是最后的序号，比如5642这个子树在后序中也是5642，所以，2是根节点。把2放回中序的5462中发现2节点有左子树546，没有右子树

      4.重复上述步骤。

追问

后中序不是相同，才没右子树吗，你举得例子，不相同

追答

这棵树没有右子树，中序和后序都是4321

后序的最后一个肯定是最上层的根节点，也就是1肯定是根节点

把1代入中序，左子树是432，右子树没有

对于左子树432代入后序中，2是最后一个，所以2是左子树的根节点

以此类推