Question

设二叉树的前序序列为ABCDEF,中序序列为BDFECA ,则该二叉树的后序序列为？要过程谢谢

Answer 1

此类题目由前序、中序依次分析

由前序可知 此二叉树根节点为A

则由中序序列知 BCDEF 为左子树

注意：由前序确定根节点及父节点，由中序序列确定左右子树！！！

此时二叉树为

再将 BCDEF 作为新序列分析，此时由前序知父（根）节点为B

由中序知 DFEC 为右子树

此时二叉树为

继续再将 CDEF 作为新序列，由前序知父节点为C

由中序知 DFE 为左子树

此时二叉树为

以此类推，依次得到二叉树为

此时便得到此二叉树，再由后序序列遍历顺序为 左右根 ，知后序序列为 FEDCBA

纯手打，希望有所帮助

Answer 2

首先根据前序序列确定根节点为A，看到在中序序列中A在最后的位置，说明A只有左子树，没有右子树。因而A的左节点为B，剩余中序序列为BDFEC，看到在中序序列中B在最前的位置，说明A只有右子树，没有左子树。因而B的右节点为C，剩余中序序列为DFEC，看到在中序序列中C在最后的位置，说明C只有左子树，没有右子树。因而C的左节点为D，剩余中序序列为DFE，看到在中序序列中D在最前的位置，说明D只有右子树，没有左子树。因而D的右节点为E，剩余中序序列为FE，看到在中序序列中E在最后的位置，说明E只有左子树，没有右子树。因而E的左节点为F.