二叉树的遍历题目及答案.docx

二叉树的遍历题目及答案

1.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也称对称序法，即按LNR次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是FEGHDCB。

解：法1：先由已知条件画图，再后序遍历得到结果；

法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。

法3：递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。

2.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

3、当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EGBDHFAC时，其后序序列必是

A.BDEAGFHC

B.EBDGACFH

C.HGFEDCBA

D.HFGDEABC

答案：B

4.已知一棵二叉树的前序遍历为ABDECF，中序遍历为DBEAFC，则

对该树进行后序遍历得到的序列为______。

A．DEBAFC

B．DEFBCA

C．DEBCFA

D．DEBFCA

[解析]由二叉树前序遍历序列和中序遍历序列可以唯一确定一棵二叉树。由前序遍历为ABDECF，可以确定二叉树的根为A，这样二叉树的左子树的前序遍历为BDE、中序遍历为DBE。在左子树中，可以确定B为根，D为左子树，E为右子树。同样的方法可以确定右子树。答案：D

5.已知一颗二叉树的前序（后序）遍历序列和中序遍历序列，如何构建这棵二叉树？

前序遍历序列：ABCDEF中序遍历序列：CBDAEF

前序遍历先访问根节点，因此前序遍历序列的第一个字母肯定就是根节点，即A是根节点；然后，由于中序遍历先访问左子树，再访问根节点，最后访问右子树，所以我们找到中序遍历中A的位置，然后A左边的字母就是左子树了，也就是CBD是根节点的左子树；同样的，得到EF为根节点的右子树。

6.以下面的例题为例进行讲解：

已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF，求二叉树及后序遍历序列。

分析：先序遍历序列的第一个字符为根结点。对于中序遍历，根结点在中序遍历序列的中间，左边部分是根结点的左子树的中序遍历序列，右边部分是根结点的右子树的中序遍历序列。

先序：ABDCEF--ABDCEF

中序：BDAECF--BDAECF

得出结论：A是树根，A有左子树和右子树，左子树有BD结点，右子树有CEF结点。

先序：BD--BD

中序：BD--BD

得出结论：B是左子树的根结点，B无左子树，有右子树(只有D结点)。

先序：CEF--CEF

中序：ECF--ECF

得出结论：C是右子树的根结点，C有左子树(只有E结点)，有右子树(只有F结点)。