前序:abdgcefh
中序:dgbaecfh
后序:gdbehfca
如何分析前序中序后序的结果的方法就比较容易了吧,每个人或许有自己的方法,呵呵,我的方法得益于高手指导。这不是本题的难点,本题问题在于
如何根据给定的前序中序结果画出二叉树,从而来确定后序的问题。
分析过程如下:
(1)前序顺序为根左右,根据前序知道:a 为根节点,然后观察 a 在中序遍历中的结果得到:dgb 为 a 的左子树的中序遍历结果,echf 为 a 的右子数的
中序遍历结果。
(2)紧接着上面的分析,回到前序遍历来观察 dgb(左子数的中序)对应的前序为:bdg,所以左子数的根节点为 b,同样的道理,回到中序结果
dgb,知道 dg 为左子树,b 没有右子树。依照这种规律分析下去,可以完整的分析出这棵树的结构,然后就可以得到后序结果了。
仔细回顾一下,这题并不难,但是,由于没有真正思考过这个题的思路,于是,考试的时候依然是不会,所以,考试(笔试就是考试)重要的是要多做
题,多积累往年试题。
继续探索,加油!
树中已知先序和中序求后序。
如先序为:abdc,中序为:bdac .
则程序可以求出后序为:dbca 。此种题型也为数据结构常考题型。
算法思想:先序遍历树的规则为中左右,则说明第一个元素必为树的根节点,比如上例
中的 a 就为根节点,由于中序遍历为:左中右,再根据根节点 a,我们就可以知道,左子树包含
元素为:db,右子树包含元素:c,再把后序进行分解为 db 和 c(根被消去了),然后递归的
进行左子树的求解(左子树的中序为:db,后序为:db),递归的进行右子树的求解(即右
子树的中序为:c,后序为:c)。如此递归到没有左右子树为止。
关于“已知先序和后序求中序”的思考:该问题不可解,因为对于先序和后序不能唯一的确定
中序,比如先序为 ab,后序为 ba,我只能知道根节点为 a,而并不能知道 b 是左子树还是右子树
评论0