免费版：华文慕课-数据结构二叉树题库
目录
华文课后题
王道课后题
华文课后题
1、一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）
解析：
答案： 10
2、请写出下面这棵二叉树的中序遍历
解析：
左-根-右 left-root-right
答案： LXMECKPBQHDA
3、下列关于二叉树性质的说法正确的有：
A、非空满二叉树的结点个数一定为奇数个。
解析：非空满二叉树只有度为0或者度为2两种结点，而这两种结点的个数差为1，所以加起来必为奇数。
n0 = 5个 n2 = 4个 n0 = n2 + 1
B、非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。
解析：非完全二叉树无法知道每一层哪些位置缺了结点，不能像完全二叉树那样直接计算出两个儿子的编号，所以不能用顺序存储结构存储。
C、当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。
解析：只要倒数第二层的度都为0或者2，此棵完全二叉树即为满二叉树，最下面一层不一定要全满
D、完全二叉树最多只有最下面的一层结点度数可以小于2。
解析：倒数第二层也可以有度数为0的结点。
E、一棵非空二叉树的为空的外部结点数等于其结点数加1。
解析：
设度为0,1和2的结点数为
，
和
，那么为空的外部结点数目等于2
+
=
+
+
+1，于是等于结点数加1。
长方形为扩充的外部结点数 = 15个
圆形为原先的二叉树结点数 = 14个
F、满二叉树的所有结点的度均为2。
解析：结点度数还可以为0。
4、已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。
解析
答案： DGEBFCA
5、下列关于二叉树遍历的说法正确的有:
A、只有空二叉树和一个根结点的二叉树这两种二叉树的前序和中序遍历的顺序恰好一样。
解析：前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。所以所有结点左子树为空的二叉树也满足要求。
B、所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。
解析：前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。
C、所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。
解析： 前序为中左右，而中序为左中右，所有结点都没有右子树后，前序为中左，而中序为左中，两者不同。
D、只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。
解析：前序为中左右，而后序为左右中，缺失左子树，前序为中右，而后序为右中；
缺失右子树，前序为中左，而后序为左中，都不一样。（下面的选项同理）
E、所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。
解析：前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。
F、所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。
解析：前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。
G、只有空二叉树和一个根结点的二叉树这两种二叉树的中序和后序遍历的顺序恰好一样。
解析：中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。所以所有结点右子树为空的二叉树也满足要求。
H、所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。
解析：中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。所以所有结点右子树为空的二叉树才满足要求。
I、所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。
解析： 中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。
J、存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。
解析：只有一个根结点的二叉树满足要求。
6、下列关于二叉搜索树的说法正确的有
A、二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。
解析：
B、如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在x的左子树之中。
解析：这样的结点就位于χ的左子树的右子树中。
C、当根结点没有左儿子时，根结点一定是值最小的结点。
解析：右子树中的结点的值都大于根结点，所以根结点的值是最小的。
D、二叉搜索树一定是满二叉树。
解析：不一定。如果对于一个结点存在值比它大的结点，但不存在比它小的，这时它可能就只有一个儿子。
E、二叉搜索树一定是完全二叉树。
解析：不一定。按照从小到大的顺序依次插入一些值（数量超过1个），就可以让二叉搜索树变成一条链，这样显然不是完全二叉树。
F、从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。
解析：右子树中的结点的值都大于根结点，所以根结点的值是最小的。
7、
从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码构造出一棵二叉搜索树，以怎样的顺序插入关键码集合{14,32,47,6,9,12,78,63,29,81}可以使得树的深度最小？请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。
解析
通过[
]=4可以得到树的最小层数。然后因为需要保证先插入的元素尽可能的小，所以可以使得右子树尽可能的满。构造出这样一棵二叉搜索树后，按照前序遍历可以得出答案。 如果有多组满足要求的方案，请使得你的答案中先插入的元素尽可能的小。
答案： 12 6 9 47 29 14 32 78 63 81
8、下列关于堆的说法正确的有:
A、堆一定是满二叉树。
解析：堆采用完全二叉树实现。
B、最小堆中，最下面一层最靠右的结点一定是权值最大的结点。
解析：