树的定义

def： 一个连通且无回路的无向图称为无向树。

树枝： 树中的边
树叶： 度为1的结点
分支点（内点）： 度大于1的结点
森林： 不连通的，但每个联通分支都是无向树的图

例1

无向树T，有2个2度顶点，2个3度顶点，1个4度顶点，其余顶点均为树叶。试求T的阶数n、边数m、树叶数t。

阶数就是节点数。

据定理：

2m = 总度数
树：m = 顶点数 - 1 = n - 1

解：

设树叶数为 t，树叶度数为1，则：

① 由 2m = 总度数：

2m = 2×2 + 2×3 + 1×4 + 1×t = 4 + 6 + 4 + t = 14 + t

② 由 m = n-1，而 n = 2 + 2 + 1 + t = 5 + t（所有顶点数之和）：

m=4+t

2m = 2(4 + t)

由①②联立：

14 + t = 2(4 + t)

14 + t = 8 + 2t

∴ t = 6

∴ n - 1 = 4 + t = 4 + 6 = 10

∴ n = 11，m = n - 1 = 10

结论： T的阶数 n = 11，边数 m = 10，树叶数 t = 6。

最小生成树

def： 连通图G所有生成树中带权最小的生成树称为最小生成树。

例2：求下图G的最小生成树T，计算T的权。

图G的边及权重：

边集： a-b=5, a-e=5, b-e=8, b-c=11, b-d=10, c-d=9, e-d=8（外圈 a=12, e=14 已被叉掉舍弃）

法一："避圈法"（Kruskal算法）

按边权从小到大依次加入，不构成回路则保留：

选 a-b = 5 ✓
选 a-e = 5 ✓
选 e-d = 8 ✓（b-e=8 构成回路 a-b-e，舍去）
选 c-d = 9 ✓
b-c=11, b-d=10 均构成回路，舍去

得到生成树：a-b, a-e, e-d, c-d

W(T) = 5+5+8+9 = 27

法二："破圈法"（逐步去边法）

从图中找回路，每次删去回路中权最大的边：

回路 a-c-b-a：删去权最大边 b-c=11 ✗
回路 a-b-e-a：删去权最大边 b-e=8 ✗
回路 b-d-e-b（含10）：删去 b-d=10 ✗
回路 c-d-e-…：删去权最大边，保留 c-d=9, e-d=8
外圈边 12, 14 均删去 ✗

得到生成树：a-b=5, a-e=5, e-d=8, c-d=9

W(T) = 5+5+8+9 = 27

两种方法结论一致：最小生成树权 W(T) = 27

例3：求带权为 3,4,5,8,9 的最优二元树

解：Huffman算法

① 排序

将权值从小到大排列：3, 4, 5, 8, 9

② 第一步合并

取最小两个 3, 4，合并为新结点 7：

    7
   / \
  3   4

剩余序列：5, 7, 8, 9

③ 第二步合并

取最小两个 5, 7，合并为新结点 12：

剩余序列：8, 9, 12

④ 第三步合并

取最小两个 8, 9，合并为新结点 17：

  17
 /  \
8    9

剩余序列：12, 17

⑤ 第四步合并（最终）

取 12, 17，合并为根结点 29：

        29
       /  \
      12   17
     /  \  / \
    7    5 8   9
   / \
  3   4

最优二元树权：W(T) = 3×3 + 4×3 + 5×2 + 8×2 + 9×2 = 9+12+10+16+18 = 65

树的定义 ​

例1 ​

最小生成树 ​

例2：求下图G的最小生成树T，计算T的权。 ​

法一："避圈法"（Kruskal算法） ​

法二："破圈法"（逐步去边法） ​