二叉树的遍历
1-1
假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？
AA.ABCD
BB.ACDB
C C .DCBA
DD.DABC
1-2
对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树____
AA.是完全二叉树
BB.所有结点都没有左儿子
C C .所有结点都没有右儿子
DD.这样的树不存在
1-3
已知一二叉树的后序和中序遍历的结果分别是FDEBGCA和FDBEACG，那么该二叉树的前序遍历结果是什么？
AA.ABDFECG
BB.ABDEFCG
C C .ABDFEGC
DD.ABCDEFG
二叉搜索树
2-1
已知一颗由1、2、3、4、5、6、7共七个结点组成的二叉搜索树（查找树），其结构如图所示，问：根结点是什么？
AA.1
BB.4
C C .5
DD.不能确定
2-2
在上题的搜索树中删除结点1，那么删除后该搜索树的后序遍历结果是：
AA.243765
BB.432765
C C .234567
DD.765432
2-3
若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上
AA.正确
BB.错误
2-4
若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小值一定在叶结点上
AA.正确
BB.错误
答案区
| 题号 | 正确答案 |
| 1-1 | D |
| 1-2 | B |
| 1-3 | A |
| 2-1 | C |
| 2-2 | A |
| 2-3 | B |
| 2-4 | A |
解析区
1-1
通过一个前序遍历序列和一个中序遍历序列可以唯一地确定一颗二叉树，
现在已知前序遍历，我们要知道选项中哪个是这个前序遍历序列不可能匹配的序列，即两个序列构成的二叉树不存在，那么该中序遍历序列就是不可能的。
对于通过已知两种遍历序列（其中必须有一种为中序）求出唯一的二叉树还有疑惑的可以跳转至
数据结构和算法学习记录——层序遍历（层次遍历）、二叉树遍历的应用（输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树）_天上_的博客-CSDN博客
数据结构和算法学习记录——层序遍历（层次遍历）、二叉树遍历的应用（输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树）像这样一组简单的序列，只有先序遍历序列和后序遍历序列的情况下，就有两颗是符合的二叉树，其中根节点是容易确定的，先序的第一个节点就是根，后序的最后一个节点就是根；之前讲过的递归先序遍历二叉树写法很简单，而要输出二叉树中的叶节点，就可以在进行遍历的过程中进行检测，如果为叶节点则输出，否则继续遍历。
经验证，
这颗二叉树的前序遍历序列和中序遍历序列都为ABCD，
故而A选项是正确的。
经验证，
这颗二叉树的前序遍历序列为ABCD；中序遍历序列为ACDB，
故而B选项是正确的。
经验证，
这课二叉树的前序遍历序列为ABCD，中序遍历序列为DCBA，
故而C选项是正确的。
经验证，
这课二叉树的前序遍历序列为ADBC，中序遍历为DABC， 因前序遍历与题干冲突，这课二叉树不存在，
故而，D选项是错误的。
综上所述，正确答案选择的是D。
1-2
这道题在我们做完上面一道题之后，很容易的就可以得到答案。
上面一道题中，分别出现了前序遍历序列和中序遍历序列结果一样以及结果相反的情况：
其前序和中序遍历序列结果一样时，是一颗右斜的二叉树，都没有左儿子，而结果相反时，是一颗左斜的二叉树，都没有右儿子。
故而答案选择B：所有结点都没有左儿子。
1-3
这道题就是一个很直接的已知两种序列（其中必须一种为中序）求二叉树的问题。下面直接上手求出二叉树：
二叉树出来了，我们就很可以得到它的前序遍历序列为：ABDFECG，
故而正确答案选择A。
2-1
我们知道二叉搜索树的特点是：
左子树小于根结点，右子树大于根结点。
所以根据这个特点来完成第一题即可。
先看A选项，根结点为1。这棵二叉搜索树的结点由1-7构成，很显然，如果根结点为1，那将没有任何数比1还小，而这棵二叉搜索树是有左子树的，
所以1不可能为根结点。
看B选项，根结点为4。
比4要大和比4小的结点数各有3个，不满足该二叉搜索树的结构，所以4也不可能为根结点。
再看C选项，根结点为5。比5大的结点数为2，比5小的结点为4。
从结构上看是可行的，我们来写出这棵二叉搜索树：
最后看D选项。在已知所有结点的键值的情况下，我们是能够通过左子树的结点数和右子树的结点数来确定根结点的，
即左子树的所有结点的键值小于根结点，右子树的所有结点的键值大于根结点。
综上所述，正确答案选择的是C。
2-2
这道题要求删除上一道题的二叉搜索树的结点1，再求出后序遍历序列。我们在上一道题就已经把完整的二叉搜索树写出来了，所以直接操作即可。
最终，删除之后的二叉搜索树写出其后序遍历序列为：243765
与之匹配的选项为A，
故而正确答案选择A。
2-3
二叉搜索树的最大值一定在最右端，我们画出一颗完全二叉树：
通过这个例子就可以很明显地看出这道判断题应该是错误的，在完全二叉树中，一个结点如果有左子树，那么该结点不一定会有右子树，一定会有右子树的情况是为满二叉树。而最大值一定在右端的结点，
故而这道题选择错误的，即B选项。
2-4
这道题用到的知识点与上一道题是一样的，只不过换成了二叉搜索树的最小值，最小值一定在左端的结点中。
这道题选择正确的，即A选项。
end
