一棵二叉树的前序遍历为1234?
前序:abdgcefh
中序:dgbaecfh
本题问题在于如何根据给定的前序中序结果画出二叉树,从而来确定后序的问题。
分析过程如下:
(1)前序顺序为根左右,根据前序知道:a为根节点,然后观察a在中序遍历中的结果得到:dgb为a的左子树的中序遍历结果,echf为a的右子数的中序遍历结果。
(2)紧接着上面的分析,回到前序遍历来观察dgb(左子数的中序)对应的前序为:bdg,所以左子数的根节点为b,同样的道理,回到中序结果dgb,知道dg为左子树,b没有右子树。依照这种规律分析下去,可以完整的分析出这棵树的结构,然后就可以得到后序结果了。