一:二叉树遍历题
后序序列为gdbehfca
过程是首先还原二叉树,再求出后序遍历序列,过程如下:
首先从前序第一个得到根,回到中序来将其分割为左子树dgb、根a、右子储echf
再分别按照左右子树的结点回到各自的前序来再次求出左右子树的根,依然是回到刚才已经切分出左右子树的中序序列来分割
重复这个过程,就可以还原出二叉树了
问题的二叉树如下:
二:二叉树遍历举例
前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
三:已知二叉树后序遍历是dabec,中序遍历是debac,求该二叉树的先序遍历。(这种类型的题目又怎么
思路是:首先看后序遍历,后序遍历是先左再右最后根,所以后序遍历最后一个肯定是根结点。所以这里根结点是c,然后看一下c这个结点在中序中的问题,中序遍历是先左再最后右,所以中序序列中,c左边的为c的左子树这边,右边有右子树这边。这里中序debac,所以该树没有右子树,只有左子树。
然后针对c的左子树递归上述过程,构建完树。
下面是我的创建过程,首先确定了c
c
/ \
未知树 无
后序倒数第二个e,确定e未知树的根,然后看中序,d在e左边,ba在右边,d是左子树确定,ba还需要进一步判断
c
/
e
/ \
d 未知数
看后序倒数第三个b,所以未知树的根是b,确定b,然后看b中序中的位置,左边无,右边a,所以最终该二叉树如下
c
/
e
/ \
d b
\
a
最后根据该树核对一下后序和中序,没有问题,所以根据该树先序遍历是cedba