选择题
13. 已知一棵二叉树，如果先序遍历的结点顺序为ADCEFGHB，中序遍历的结点顺序为cDFEGHAB，则后序遍历的结点顺序为______。
【正确答案】
D
【答案解析】 要解答出本题，首先需要对各种遍历方式有一个清晰的认识。可以通过图1来介绍二叉树的三种遍历方式的区别。
图1 二叉树的遍历方式
1)先序遍历：先遍历根结点，再遍历左子树，最后遍历右子树。所以，图1的先序遍历序列是ABDECFG。
2)中序遍历：先遍历左子树，再遍历根结点，最后遍历右子树。所以，图1的中序遍历序列是DBEAFCG。
3)后序遍历：先遍历左子树，再遍历右子树，最后遍历根结点。所以，图1的后序遍历序列是DEBFGCA。
从上面的介绍可以看出，先序遍历序列的第一个结点一定是根结点，因此，本题中可以确定这个二叉树的根结点为A。由中序遍历的特点可以把树分为三部分：根结点A、A的左子树和A的右子树。在中序遍历的序列中，在A结点前面的序列一定是在A的左子树上，在结点A后面的序列一定在A的右子树上。由此可以确定：A的左子树包含的结点为CDFEGH，右子树包含的结点为B(见图2a)。接下来对A的左子树上的结点采用同样的方法进行分析：对于序列CDFEGH，先序遍历的时候先遍历到结点D，因此，结点D是这个子树的根结点；通过对中序遍历进行分析可以把CDFEGH分为三部分：根结点D、D的左子树包含的结点为C、D的右子树上包含的结点为FEGH(见图2b)。然后对FEGH用同样的方法进行分析：在先序遍历的序列中先遍历到的结点为E，因此，根结点为E，通过分析中序遍历的序列，可以把这个序列分成三部分：根结点E、E的左子树上的结点F和E的右子树上的结点GH(见图2c)。最后分析结点GH，在先序遍历序列中先遍历到G，则说明G为根结点，在中序遍历序列中先遍历到结点G，说明H是G右子树上的结点(见图2d)。由此可以发现，通过先序遍历和中序遍历完全确定了二叉树的结构，可以非常容易
图1 二叉树的遍历方式
1)先序遍历：先遍历根结点，再遍历左子树，最后遍历右子树。所以，图1的先序遍历序列是ABDECFG。
2)中序遍历：先遍历左子树，再遍历根结点，最后遍历右子树。所以，图1的中序遍历序列是DBEAFCG。
3)后序遍历：先遍历左子树，再遍历右子树，最后遍历根结点。所以，图1的后序遍历序列是DEBFGCA。
从上面的介绍可以看出，先序遍历序列的第一个结点一定是根结点，因此，本题中可以确定这个二叉树的根结点为A。由中序遍历的特点可以把树分为三部分：根结点A、A的左子树和A的右子树。在中序遍历的序列中，在A结点前面的序列一定是在A的左子树上，在结点A后面的序列一定在A的右子树上。由此可以确定：A的左子树包含的结点为CDFEGH，右子树包含的结点为B(见图2a)。接下来对A的左子树上的结点采用同样的方法进行分析：对于序列CDFEGH，先序遍历的时候先遍历到结点D，因此，结点D是这个子树的根结点；通过对中序遍历进行分析可以把CDFEGH分为三部分：根结点D、D的左子树包含的结点为C、D的右子树上包含的结点为FEGH(见图2b)。然后对FEGH用同样的方法进行分析：在先序遍历的序列中先遍历到的结点为E，因此，根结点为E，通过分析中序遍历的序列，可以把这个序列分成三部分：根结点E、E的左子树上的结点F和E的右子树上的结点GH(见图2c)。最后分析结点GH，在先序遍历序列中先遍历到G，则说明G为根结点，在中序遍历序列中先遍历到结点G，说明H是G右子树上的结点(见图2d)。由此可以发现，通过先序遍历和中序遍历完全确定了二叉树的结构，可以非常容易