Question

一只一棵二叉树的先序遍历结果为abcdefghi,中序遍历结果为cbafegdhi,请写出后序遍历结果并画出这棵二叉树

一只一棵二叉树的先序遍历结果为abcdefghi；中序遍历结果为cbafegdhi，请写出后序遍历结果并画出这棵二叉树。
（1）问此类题做法。。。。。
（2）追问：该二叉树是否为
a
/ \
b d
/ / \
c e h
/ \ \
f g i

Answer 1

左一定优先于右 ，所以根的位置有三种。

 根 左 右、左 根 右、左 右 根。

分别称为先序遍历、中序遍历、后续遍历，子树也一样，到一个子树就遍历一次，按照遍历顺序写下去就好，尤其注意根特殊对待（只有一个所以只写一个）。

后续遍历是：CBEFDA

依据前序遍历序列可确定根结点为A；再依据中序遍历序列可知其左子树由DBE构成，右子树为FC；又由左子树的前序遍历序列可知其根结点为B，由中序遍历序列可知其左子树为D，同理推算FC的排列顺序。

扩展资料：

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前驱结点和一个后继结点。为了区别于树形结构中前驱（即双亲）结点和后继（即孩子）结点的概念，对上述三种线性序列，要在某结点的前驱和后继之前冠以其遍历次序名称。

参考资料来源：百度百科-二叉树遍历

Answer 2

这类题的推导方法见：http://zhidao.baidu.com/question/199520462615190205.html?oldq=1