二叉树前序、中序、后序遍历相互求法,即如果知道两个的遍历,如何求第三种遍历方法:
前序、中序、后序遍历的特性:
前序遍历:
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树
中序遍历:
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
后序遍历:
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点
前序、中序、后序遍历的特性:
前序遍历: 序列第一个节点是根节点,最后一个节点为最右边节点(根,左,右)
中序遍历: 序列第一个节点是最左边节点,最后一个节点为最右边节点(左,根,右)
后序遍历: 序列第一个节点是最左边节点,序列最后一个节点是根节点(左,右,根)
当前序遍历与中序遍历序列相同时,该树无左子树,当后序遍历与中序遍历序列相同时,该树无右子树
已知前序、中序遍历,求后序遍历
前序遍历: ABCDEFG
中序遍历: DCBAEFG
画树求法:
第一步,根据前序遍历的特点,我们知道根节点为A,中序遍历的特点,最左边节点为D,后序遍历最后一个节点是A,则后序遍历结果为D...A。
第二步,观察中序遍历DCBAEFG。其中root节点A左侧的ABCD必然是root的左子树,A右侧的EFG必然是root的右子树。
第三步,观察左子树ABCD,左子树的中的根节点必然是大树的root的左孩子。在前序遍历中,大树的root的左孩子位于root之后,所以左子树的根节点为B。
第四步,同样的道理,root的右子树节点EFG中的根节点也可以通过前序遍历求得。在前序遍历中,一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树,并且遍历的左子树的第一个节点就是左子树的根节点。同理,遍历的右子树的第一个节点就是右子树的根节点。
第五步,观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下:
1 确定根,确定左子树,确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 保存当前根。
那么,我们可以画出这个二叉树的形状:DCBGFEA,树的形状如下:
某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为( )
A. EFGDCBA
B. DCBEFGA
C. BCDGFEA
D. DCBGFEA
答案:D
解析:前序序列是中左右,根结点为A;中序序列是左中右,左子树BCD,右子树EFG;遵循遍历序列的规则排列出二叉树,得出后序遍历为DCBGFEA。所以选择D。