因证明题部分较为简单，大多为记忆内容，因此同种证明思路不过多赘述。

1. n（n>1）个权值构造的Huffman树中不存在度为1的节点。

（反证法，1）

哈夫曼树（最优树）：带权路径最短的树。

假设存在一个度为1的节点，即该树有一棵子树。

设该节点为A，其子树为B。可将AB合并成一个节点，

则B以下叶子节点的带权路径减少，树的带权路径长度减少，

显然合并后的树，带权路径长度小于原树，

与原树是Huffman树的条件相悖，故假设不成立。

2. 若（u，v）是一条最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含（u，v）的最小生成树。

（反证法， 2）

令N = （V，{E}），v∈V

设：连通网网N中的任何一棵最小生成树都不包含（u，v），T是N中的一棵最小生成树。

由生成树定义可知：

①当把边（u，v）加入T中，T中必存在一条包含（u，v）的回路。

②T中必存在另一条边（u1，v1）， u1∈U，v1∈V。

则u和u1之间，v和v1之间均有路径相通。

删去边（u1，v1），即可消除上述回路，得到新生成树【T1】.

因为（u，v）的代价不高于（u1，v1），所以【T1】的代价不高于T，

所以【T1】是包含（u，v）的一棵最小生成树，与假设矛盾。

因此，问题得证。

3. n个节点，k条边的非联通无向图是一个森林（n>k），证：森林有n-k棵树。

设：森林有x棵树，每棵树的节点数为x1，x2，… xn；

除根节点外，每个节点都有唯一的一条分支（边）与之对应，即：总边数 = 总节点数 -1；

（注：几道证明题都用到这句话，也是围着这句话展开的证明）

每棵树的边数为(x1-1)，(x2-1)，… (xn-1)；

则 n = x1 + x2 + …+xn；

k = (x1-1) + (x2-1)+ … + (xn-1)=(x1 + x2 + … + xn) – x = n – x

所以： x = n – k

4. 高度为h的二叉树节点数不超过2^h-1。

（归纳法, 1）

令n表示二叉树的节点总数

①高度h = 1； n = 1 = 2^1 – 1；

②h≤k； 设 n ≤ 2^k – 1；

③h = k + 1；

定义可知：第i层最多有2^( i-1 )个节点。

n + 2^k【n表示k层节点总数，2^k表示k+1层最多节点数，相加为k+1层最多节点数】

≤2^k -1 + 2^k = 2^( k+1 ) -1;

所以，k+1层总节点数≤2^( k+1 ) -1;

综上，由归纳法得证，高度为h的二叉树节点数不超过2^h-1.

5. 高度为h的2-3B树中叶子节点数目在2^(h-1) 到 3^(h-1)之间。

（归纳法，2）

令N表示2-3B树的叶子节点总数

①h = 1，N = 1； 2^(1-1) ≤ N ≤ 3^(1-1) ，不等式成立。

②h ≤ k， 设 2^(k-1) ≤ N ≤ 3^(k-1)；

③h = k+1，

根据定义，2-3

B树的子树有2~3棵，分别记为：r1，r2，r3。

对于每棵子树，高度都小于等于k，

由②可知，每棵树的叶子节点数目：2^(k-1) ≤ N ≤ 3^(k-1)；

各子树的叶子节点都是原树的叶子节点，分两种情况：

⑴最少有2棵子树，每棵子树叶子节点最少为2^(k-1)，所以N ≥ 2*2^(k-1) = 2^k

⑵最多有3棵子树，每棵子树叶子节点最多为3^(k-1)，所以N ≤ 3*3^(k-1) = 3^k

所以， 2^k ≤ N ≤ 3^k;

综上，由归纳法得：高度为h的2-3B树中叶子节点数目在2^(h-1) 到 3^(h-1)之间。

结语：大体分为这5种，后续有值得补充的再补充上。