软考中级
● 已知某二叉树的中序序列为 CBDAEFI、先序序列为 ABCDEFI，则该二叉树的高度为 （58） 。（58）A. 2B. 3C. 4D. 5
题目
● 已知某二叉树的中序序列为 CBDAEFI、先序序列为 ABCDEFI，则该二叉树的高度为 （58） 。
（58）
A. 2
B. 3
C. 4
D. 5
相似问题和答案
第1题：
已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为( )。对于任意一棵二叉树，叙述错误的是( )。
A．②、③、①、⑤、④
B．①、②、③、④、⑤
C．②、④、⑤、③、①
D．④、⑤、③、②、①
解析：本题根据题意先序遍历为1，2，3，4，5；中序遍历为2，1，4，3，5，可推算出后序遍历为2，4，5，3，l。由二叉树的先序遍历和后序遍历无法推}}{构造该二叉树的中序遍历。
第2题：
若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为(8)。
A．DEBAFC
B．DEFBCA
C．DEBCFA
D．DEBFCA
解析：本题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树，然后再得出其后序遍历结果。根据先序和中序来构造二叉树的规则是这样的：首先看先序遍历序列ABDECF，先序遍历中第一个访问的结点是A，这说明A是二叉树的根结点(因为先序遍历顺序是：根，左，右)。然后看中序遍历序列DBEAFC，中序中A前面有结点DBE，后面有结点FC。这说明DBE是A的左子树，FC是A的右子树(因为中序遍历顺序是：左，根，右)。再回到先序遍历序列中看DBE的排列顺序(此时可以不看其他的结点)，我们发现在先序遍历序列中B排在最前面，所以B是A的左子树的根结点。接下来又回到了中序遍历序列，中序遍历序列中D在B的前面，E在B的后面，所以D是B的左子树，E是B的右子树。对于A的右子树，可同样依此规则得出。由此，可构造二叉树，如图4-8所示。然后对这棵二叉树进行后序遍历，得到DEBFCA。
第3题：
● 某二叉树的先序遍历序列为 ABFCDE、中序遍历序列为 BFADCE，则该二叉树根的左孩子和右孩子结点分别是（38）。
（38）
A. B 和 F
B. F 和 B
C. B 和 C
D. C 和 B
第4题：
已知某二叉树的先序遍历序列是ABDCE，中序遍历序列是BDAEC，则该二叉树为______。
解析：本题考查数据结构基础知识。
对二叉树进行先序遍历的过程是：若二叉树非空，则先访问根结点，然后先序遍历左子树，最后先序遍历右子树。因此，二叉树的先序遍历序列中，第一个元素是根结点。
对二叉树进行中序遍历的过程是：若二叉树非空，则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。因此，若在中序遍历序列中已找出二叉树的根结点，则根结点左边为左子树的中序遍历序列，右边是右子树的中序遍历序列。
由此，根据先序序列确定根结点，根据中序序列划分左右子树，反复应用此原则，就可根据先序遍历序列和中序遍历序列恢复二叉树的结构。
本题中，先序序列为ABDCE，因此A是树根结点，中序序列为BDAEC，因此BD是左子树上的结点，EC是右子树上的结点。根据先序遍历序列，可知B是左子树的根结点，C是右子树的根结点。在中序遍历序列BDAEC中，D在B之后，因此D是B的右孩子。同理，在中序遍历序列BDAEC中，E在C之前，因此E是C的左孩子。
第5题：
已知某二叉树的中序序列为CBDAEFI、先序序列为ABCDEFI，则该二叉树的高度为(58)。
A．2
B．3
C．4
D．5
解析：本题考查二叉树的遍历运算。根据二叉树的定义，非空二叉树由根结点、根的左子树和根的右子树三部分组成。二叉树的先序遍历定义为：先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。二叉树的中序遍历定义为：中序遍历根的左子树，访问根结点，最后中序遍历根的右子树。由此，根据二叉树的先序遍历序列和中序遍历序列构造二叉树时，首先根据先序序列找到根结点，然后由中序序列分别得到左、右子树的中序序列和先序序列，如此反复进行分解，即可得到原二叉树。因该二叉树的先序序列中A是第一个结点，因此确定A是整棵二叉树的树根，在中序序列中找到A，并据此划分出根的左子树上的结点中序序列CBD和右子树上的结点中序序列EFI。再根据先序遍历的特点，先序序列指示出B是左子树的根结点，中序序列中C在B的左边、D在B的右边，因此确定C结点在以B为根的左子树上、D结点在以B为根的右子树上。依次类推，根据先序序列确定根，根据中序序列分割子树，最后得到的原二叉树如下图所示。
二叉树的层数为树的高度。
第6题：
:ACDBGFEA
BCDBFGEA
CCDBAGFE
DBCDAGFE
第7题：
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不确定
第8题：
● 已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 （57） 。对于任意一棵二叉树，叙述错误的是 （58） 。
（57）A. ②、③、①、⑤、④
B. ①、②、③、④、⑤
C. ②、④、⑤、③、①
D. ④、⑤、③、②、①
（58）A. 由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列
B. 由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列
C. 由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列
D. 由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列
试题（57）、（58）分析
本题考查数据结构基础知识。
遍历运算是二叉树的基本运算，主要有先序、中序、后序和层序遍历。
先序遍历的基本方法：对于非空二叉树，先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。因此，若已知某二叉树的先序遍历序列，则可直接得到其树根结点。
中序遍历的基本方法：对于非空二叉树，先中序遍历根的左子树，然后访问根结点，最后中序遍历根的右子树。因此，若已知某二叉树的根结点，则一可根据中序遍历序列将该二叉树左右子树上的结点划分开。
后序遍历的基本方法：对于非空二叉树，首先后序遍历根的左子树，接着后序遍历根的右子树，最后访问根结点。因此，若已知某二叉树的后序遍历序列，则可直接得到其树根结点。
题中给出的先序遍历序列为①、②、③、④、⑤，可知树根结点是①，据此再结合中序遍历序列②、①、④、③、⑤，可知②是根结点①左子树上的结点，由于是左子树上唯一的一个结点，因此②是根结点①的左孩子。对于右子树上的结点④、③、⑤，因右子树的先序遍历序列为③、④、⑤，因此③是根结点①的右孩子。依此类推，可知④是结点③的左孩子，⑤是结点③的右孩子。该二叉树如下图所示。
从二叉树的遍历过程可知，从先序遍历序列和后序遍历序列中无法将左子树和右子树上的结点区分开，因此，由某棵二叉树的先序遍历序列和后序遍历序列不能构造出该二叉树的中序遍历序列。
层序遍历二叉树的方法：设二叉树的根结点所在层数为1，则层序遍历二叉树的操作定义为从树的根结点出发，首先访问第一层的结点（根结点），然后从左到右依次访问第二层上的结点，接着是第三层上的结点，依此类推，自上而下、自左至右逐层访问树中各层上的结点。
第9题：
已知某二叉树的层序、中序序列分别为FDEBCA、DBAFCE，则该二叉树的后序序列为(57)。
A．ABDCEF
B．BCDEAF
C．DABECF
D．DBACEF
解析：遍历二叉树是按某种搜索策略巡访二叉树中的每一个节点，使得每个节点均被访问一次，而且仅被访问一次。二叉树可以递归定义成由3个部分组成，即根节点(记为D)、左子树(记为L)和右子树(记为R)。只要按某种次序遍历这三部分，就可遍历整个二叉树。
若限定左子树的遍历要在右子树之前遍历，那么根据访问根节点的位置的不同可有3种方法：前序遍历、中序遍历和后序遍历，分别简记为DLR、LDR和LRD。
层序遍历二叉树的操作定义为：从树的根节点出发，首先访问第1层的树根节点，然后从左到右依次访问第二层上的节点，其次是第三层上的节点，依次类推，自上而下、自左至右逐层访问树中各层上的节点。
根据以上遍历方法的特点，先序、后序和层序序列用于确定树根节点，在此基础上，根据中序序列划分根的左右子树，即可逐步构造出对应的二叉树。
对于本试题，首先根据层序序列的第一个节点为根，即F为根节点，然后根据中序序列划分左、右子树，就分别得到左、右子树的中序序列分别为DBA和 CE，因此得知根的左右子树都不为空，也就是说层序序列中的D、E分别是F的左子节点和右子节点。由于中序序列中C在E之前，因此C为E的左子树根，而在F的左子树D上，B、A在D之后，即说明D的左子树为空，B、A为其右子树的节点且B、A两节点形成父子节点关系。在层序序列中B在A之前，因此B为A的父节点，在中序序列中B在A之前，因此A是B的右子节点。因此该二叉树如图2-16所示。
图2-16二叉树的后序序列为ABDCEF。
第10题：
某完全二叉树层序序列为ABCDEF，则该完全二叉树的中序序列为______。
A．DBEAFC
B．DEBFCA
C．DEBCFA
D．DBEACF
解析：完全二又树是指除了最外层，其余层上的节点数目都达到最大值，而第h层上的节点集中存放在左侧树中。按照遍历左子树要在遍历右子树之前进行的原则，根据访问根节点位置的不同，可得到二叉树的前序、中序和后序3种遍历方法。