【数据结构】树与二叉树 ——经典选择题 详解

题目1：

解析：

结点的度：一个结点拥有的直接子结点（孩子结点）的个数，叫做该结点的度。

树的度：树中所有结点里 度数最大的节点 的度数；

叶子节点：度为0的结点；

题目中说树的度是4，也就是说所有节点中度最大是4。

设度为x的点有nx个，那么n0=? ,n1=4 ,n2=2 ,n3=1 ,n4=1 ;

有一个度就有一条边，树的 总边数 = 总度数 = 0*n0 + 1*n1 + 2*n2 + 3*n3 + 4*n4 = 5 ;

树的 总结点数 =  n0+n1+n2+n3+n4 = n0+8 ;

树的总边数 = 树的结点数 – 1；(因为除了根节点，树中每个节点都 有且仅有 一条边连向自己的父节点，即除了根节点，一个节点对应一条边)

所以 n0+8-1=15； 得 n0=8；

题目2：

解析：

n 叉树：树的度 ≤ n，每个结点最多只能连 n 个孩子结点（可以连 0到n个 孩子节点）

这个题目我们会发现，跟 题目1 是一个道理，但是我们只知道n2,n3,n4, 剩下n1,n0均未知，求n0；

这里来说明，度为1的结点数（n1）可以不必知道，n1值不影响结果。

证明：（设 总结点数为N，总边数为B） N = n0+n1+n2+n3+n4 B = 0*n0 + 1*n1 + 2*n2 + 3*n3 + 4*n4     = n1+ 2*n2 + 3*n3 + 4*n4 B=N-1； 即 n1 + 2*n2 + 3*n3 + 4*n4 = n0 + n1 + n2 + n3 + n4 -1； n1两边都是1倍，消去，则知道n2,n3,n4值即可求解n0；

本题为：

4*2+2*3+1*4 = n0+4+2+1-1 ;

得n0=12;

题目3：

解析：

（二叉）搜索树：对于每个节点的值都有 左孩子<父节点<右孩子；

AVL树：自平衡的 二叉搜索树

完全二叉树：树的 倒数第二层及以上必须是满的，不能有空缺（也就是必须所有左右孩子都存在），最后一行可以不满，但是必须是从左往右填满的（不能有 右边有结点 但 左边没节点 的情况）。

最小堆（它是一种 完全二叉树）：父节点最小（就是父节点 < = 左右孩子）,但是左右孩子之间大小关系不确定；

最大堆（也是 完全二叉树）：父节点最大（父结点 > = 左右孩子）,左右孩子之间大小关系不确定；

A项：中序遍历是按照 左->根->右 的顺序来遍历，由于搜索树  左孩子<父节点<右孩子 ，所以遍历结果一定是从小到大的；

B项：中序遍历是按照 根->左->右 的顺序来遍历，由于最小堆 父节点 < = 左右孩子 ，而左右孩子间大小不确定，所以遍历结果并不一定有序；

C项：搜索树中，有 左<右 ，同一层的结点从左到右必定是从小到大的；

D项：最小堆中，父节点最小（父节点 < = 孩子结点），所以 从任意根结点到任一叶结点 路径上的所有结点（也就是从任意父节点向下一路找孩子，先遍历A，向下遍历A的某一个孩子B，再向下遍历B的某一个孩子C……直到遍历到叶节点F，它没有孩子了，遍历停止）一定是从小到大的。

题目4：

解析：

【满二叉树的第n层有 2的(n-1)次方 个节点】                                                                                    

 证明： 第一层有2的0次方个节点（根节点），第二层有2的1次方个节点（第一层每个节点在第二层有两个孩子，2的0次方*2），第三层有2的2次方个节点（第三层每个节点在第二层有两个孩子，2的1次方*2），以此类推即可得此结论 

【对于满二叉树，前n层的节点个数为  2的n次方 – 1】

证明： 对于满x叉树, 第n层有x的n-1次方个结点，前n层的结点数可用 等比数列前n项求和公式 

Sn =  [a1*(1-q的n次方)] / (1-q) = [1*(1-x的n次方)] / (1-x) ，代入x=2易得Sn= 2的n次方 – 1

来看这道题吧：

第9层若满，应共有 2的(9-1)次方 = 256 个节点，

这棵树有两种可能的情况：

1. 第九层是最后一层，第九层一共就只有这100个叶节点，而前八层是全满的；

2. 第九层是倒数第二层，是满的，第十层不满，第九层的那100个叶子节点在第十层没有孩子结点，256-100=156个非叶节点 在第十层有孩子结点；

很明显，情况2下 这棵树总节点数更多，我们就这种情况继续讨论。

第九层的 156个非叶子节点 每个节点在第10层最多有两个孩子，156*2=312个（第10层节点数）， 再加上前9层满的：2的9次方  – 1=511；

那么共有511+312=823个节点。

题目5：

解析：

以二叉链表作为二叉树的存储结构，那么每个节点有左右指针两个指针域（如果该节点没有某个孩子，那就把指向这个孩子的指针 指向空）

n个节点有2n个指针域，

一个非空指针域对应一条边（为方便理解，可以把每条边看做一根非空指针，结点A连向它的孩子B的边 可以看作 A指向B的非空指针；空指针指向空，也就是对应位置的孩子节点并不存在，也就没有连向这个孩子的边），非空指针域数 = 边数。

总边数 = 总结点数 – 1 ；（因为除了根节点，每个节点都 有且仅有 一条边连向它的父节点，也就是除了根节点，一个节点对应一条边）

假设有x个空链域，

则 2n-x = n-1;

得 x=n+1;  

题目6：

解析：

先构造哈夫曼树（最优二叉树）：

将每个字符的频次作为叶子节点，按权重从小到大排序： 3, 4, 5, 6, 8, 10

每次取当前集合中权重最小的两个节点合并，生成父节点（权重为两者之和），并放入集合中。

第一次合并：取3和4（当前最小两个），合并为父节点7（3+4）。 集合变为：5, 6, 7, 8, 10； 第二次合并：取5和6，合并为父节点11（5+6）。 集合变为：7, 8, 10, 11； 第三次合并：取7和8，合并为父节点15（7+8）。 集合变为：10, 11, 15； 第四次合并：取10和11，合并为父节点21（10+11）。 集合变为：15, 21； 最后一次合并：取15和21，合并为根节点36（15+21）。 哈夫曼树构造完成。（如图）

哈夫曼编码的加权平均长度 =（各字符频次 * 从根节点到该叶子节点的长度）/ 总频次之和 =（3*3+4*3+8*2+10*2+5*3+6*3）/ (3+4+8+10+5+6) =90/36 =2.5

（注：从根节点到该叶子结点的长度 就是 从根节点到该叶子结点所经过的边数）