9.2 根树及其应用

4)i← i+1,转到步骤2).
(注)以上算法需假定图中每条边的权都不 相同.但事实上对图中有若干条边的权相同的情 形,只要将它们的权作微小的变动,使之各不相同, 即可使用这个算法.
例：见书本图9.4
又有计算最小生成树的实例:
1 11
6
3 2
9
7 8
10
4 5
红绿粉红紫黄
另有“破圈法”：删除边破坏回路，同时保持图的连 通性，直到没有回路为止。 a
注意，具有 n 个结点和恰有 n-1 条边的图未 必是树，但连通或无回路的是。 连通无圈完全刻划了树，这是树的一个特
性；树还有另外一个重要性质是：它以最少的
边使结点连通。
定理9.2 给定树T=<V，E>，若|V|≥2，则T中至 少存在两个悬挂结点（树叶）。
证明: 1)设T=<V,E>是树,|V|=v.因为T是连通图,viT 有deg(vi)≥1且由定理5-1.1有∑deg(vi)=2(|V|-1)=2v-2.
例：下图为根树，右边是左图省掉方向的代替图。
v1
v2 v3 v4 v2
v1
v3 v4
v5
v6
v7
v8 v9
v5
v6
v7
v8 v9
v10 v11 v12
v10
v11 v12
为表示结点间的关系，有时借用家族中的
术语。一棵根树可以看成一棵家族树。令u是有
根树中的分枝结点，若从u到v有一条边或，则 结点v称为结点u的“儿子”，或称u是v的“父 亲”；若从u到w有一条路，称u是w的“祖先”， 或称w是u的“子孙”或“后代”，同一个分枝
第九章 树
9.1 无向树及生成树
9.2 根树及其应用

离散数学是数学的一个分支，主要研究离散对象的性质和关系。

在离散数学中，树和图是两个重要的概念和工具。

它们不仅在数学中具有重要的地位，而且在计算机科学、电子工程、通信工程等领域中也有广泛的应用。

首先，让我们来了解一下树和图的定义。

在离散数学中，树是一种特殊的图。

树是由若干个节点组成的，其中一个节点被称为根节点，其他节点分布在根节点之下的若干层次中，并且每个节点最多有一个父节点。

除此之外，树的每个节点可以有零个或多个子节点。

树的一个重要特点是：任意两个节点之间有且仅有一条路径相连。

在离散数学中，图是由若干个节点和连接节点的边组成的。

图可以分为有向图和无向图。

有向图中的边是有方向的，无向图中的边没有方向。

图的节点可以表示实体，边可以表示实体之间的关系。

图的一个重要特点是：图中的节点和边可以有多个连接。

树和图有着广泛的应用。

在计算机科学中，树和图常常被用于数据结构和算法。

比如，树可以用来实现二叉搜索树、堆、二叉树等数据结构；图可以用来实现图算法，如最短路径算法、最小生成树算法、拓扑排序算法等。

树和图的应用还涉及到网络优化、模式识别、数据挖掘、人工智能等领域。

在电子工程中，树和图被用来描述和分析电路。

树可以用来表示电路的拓扑结构，图可以用来表示电路元件之间的连接关系。

树和图在电路分析和设计中起到了至关重要的作用。

比如，树可以用来分析电路的戴维南等效电路、回路等；图可以用来优化电路的布局和布线。

在通信工程中，树和图被用来表示通信网络和通信路径。

通信网络可以看作是由节点和连接节点的通信链路组成的图，而通信路径可以看作是图中的一条路径。

树和图在通信网络的规划、管理和优化中扮演重要的角色。

比如，树可以用来构建网络拓扑，图可以用来分析和优化通信路径。

总之，离散数学中的树和图是非常重要的概念和工具，并且在各个领域中有广泛的应用。

无论是计算机科学、电子工程还是通信工程，都离不开树和图的帮助。

因此，我们应该加强对树和图的学习和应用，以更好地解决实际问题。

⑥ G中每一对结点之间有惟一一条基本通路。(n≥2)
2017/10/10 82-9
定理4.2.1 分析
直接证明这 6 个命题两两等价工作量太大，一 般采用循环论证的方法，即证明
(1) (2) (3) (4) (5) (6) (1) 然后利用传递行，得到结论。
2017/10/10
证明 TG = <VT, ET> 是 G = <V, E> 的生 分析 必要性：假设 必要性由树的定义即得，充分性利用构造性 成树，由定义 4.2.1 ， TG 是连通的，于是 G 也是连通的。 方法，具体找出一颗生成树即可
充分性：假设G = <V, E>是连通的。如果G中无回 路， G 本身就是生成树。如果 G 中存在回路 C1 ，可删除 C1中一条边得到图G1，它仍连通且与G有相同的结点集。 如果G1中无回路，G1就是生成树。如果G1仍存在回路C2， 可删除 C2 中一条边，如此继续，直到得到一个无回路 的连通图H为止。因此，H是G的生成树。
2017/10/10 82-22
思考题
1、一个图的生成树是不是唯一的呢？
2、如果不是唯一的，3个顶点的无向完全图有几棵 生成树？4个顶点的无向完全图又有几棵生成树？n 个顶点的无向完全图又有几棵生成树？
完全图是边数最 多的简单无向图
2017/10/10
82-23
定理4.2.3
一个图G = <V, E>存在生成树TG = <VT, ET>的充分 必要条件是G是连通的。
由定理4.2.1(4) 在结点给定的无向图中， 由定理4.2.1(5) 树是边数最多的无回路图 树是边数最少的连通图 由此可知，在无向图G = (n, m)中， 若m＜n-1，则G是不连通的 若m＞n-1，则G必含回路

3
欧拉图
欧拉通路：图中行遍所有顶点且恰好经过每条边一次 的通路
欧拉回路：图中行遍所有顶点且恰好经过每条边一次 的回路
欧拉图：有欧拉回路的图 半欧拉图：有欧拉通路，但无欧拉回路的图
几点说明： ①上述定义对无向图和有向图都适用。 ②规定，平凡图为欧拉图。 ③欧拉通路是简单通路, 欧拉回路是简单回路。 ④环不影响图的欧拉性。
定理 树T 的每一个分支节点都是T 的割点
27
练习①判断下列各图是否是树
v1
v4
v1
v4 v1
v4
v2 v3 v5
v2 v3 v5
v2 v3 v5
连通，有回路， 连通，无回路， 不连通，
n=5,m=5
n=5,m=4
n=5,m=3
不是树
ห้องสมุดไป่ตู้
是树
不是树
②在保持连通性的条件下，从K5中删去( 6 )条边， 得到一棵树
之间的道路，边的权表示对应道路的长度。沿道路 架设通讯线路，将这些城市联系起来，要求架设线路 最短(费用最省)，此问题就是求一棵最小生成树的问题。
31
克鲁斯卡尔 (Kruskal)算法 （P156） ——求最小生成树的算法 设G是n阶无向连通带权图G， (1)按权从小到大排列边(环除外)，
设W(e1)≤W(e2)≤…≤W(em)； (2) 令T，i1，k0； (3) 若ei与T中的边不构成回路，
注：有向树是弱连通的； 反之，无回路的弱连通有向图不一定是有向树 如，
34
在根树中，从根到其余每个结点都有唯一的一条 初级有向通路。 ①从根到某一顶点的有向通路的长度称为该顶点的层数 ②从根到树叶的最大层数称为有根树的树高 注：树根位于根树的第0层
35

上述算法能够推广到有序森林上去。
定理 设有完全m叉树，其树叶的数目为t,分支 数为i, 则(m-1)×i=t-1。
证明思路： m位选手,单淘汰赛,每局淘汰(m-1)位,
共比赛i局,最后剩1位选手。因此有：
(m-1)×i+1=t

定义 在根树中，一个结点的通路长度，就是从树 根到该结点的通路中的边数。分支点的通路长度称为 内部通路长度，树叶的通路长度称为外部通路长度。
定理2：任一棵树中至少存在两个叶。
证明： 因T连通则u∈T，deg(u)≥1。设T有k个一
度点，其它点均大于等于2，则 2e=∑deg(vi)≥k+2(v-k)=2v-k。 因e=v-1， 故2(v-1)≥2v-k，则k≥2。
2.2支撑树与支撑林
设F是图D的支撑子图，并且ω(F)=ω(D)。 若F是林，则称F为D的支撑林；若F是树， 则称F为D的支撑树。
例如:
a 19
b5
14 12
18
7
c
16 e 8
3
g
d
27
21
f
求最小生成树的克鲁斯卡尔(Kruskal)算法(避圈法)： a)在G中选取最小权的边，记作e1，置i=1。 b)当i=n-1时结束，否则转c)。 c)设已选择边为e1，e2，……ei，此时无回路。在G 中选取不同于这i条边的边ei+1，该边使得{e1，…， ei+1}生成的子图中无回路，并ei+1是满足该条件中权 最小的一条边。
定理2.4 每个连通图都含支撑树。 推论2.4.1每个图都含支撑林或者支撑树。 推论2.4.2每个图均有ε≥ν- ω。 定理2.5设F是G的支撑林。若E(G)\E(F)
非空，则对其中的任何边e，F+e含有且 仅含有一条圈。

树
图7-13 二叉树
树
例7.11 计算机中存储的文件目录,目录可以包含子目录
和文件。图7-14用多叉树表示一个文件系统。C表示根目录,
可以表示成根树,内点表示子目录,树叶表示文件或空目录。
树
图7-14 多叉树表示的文件系统
树
2.二叉树的遍历
定义7.10 对于一棵根树的每个结点都访问一次且仅一次
树
图7-16 给定单词二叉搜索树
树
7.2.3 最优二叉树及其应用
1.哈夫曼树
树
例7.14 计算图7-17所示带权二叉树的权值。
图7-17-带权二叉树
树
7.2.1 根树的概念
定义7.6 一个有向图D,如果略去有向边的方向所得的无
向图为一棵无向树,则称D为有向树。换句话说,若有向图的
基图是无向树,那么这个有向图为有向树。入度为0的顶点称
为树根(Root),入度为1且出度为0的顶点称为树叶;入度为1且
出度大于0的顶点称为内点。内点和树根统称为分支点。
有一种特殊结构的有向树叫根树。
图7-2 无向图
树
树
例7.2 设T 是一棵树,它有三个2度结点,两个3度结点,一
个4度结点,求T 的树叶数。
树
7.1.2 生成树的概念与性质
1.生成树的概念
定义7.2 设G=<V,E>是无向连通图,T 是G 的生成子图,并
且T 是树,则称T 是G的生成树(SpanningTree),记为TG 。
树
定理7.1 设G=<V,E>是n 阶无向图,G 中有m 条边,则下面
关于G 是树的命题是等价的:
(1)G 连通而不含回路;
(2)G 的每对顶点之间具有唯一的一条路径;

14. 12枚外观相同的硬币，其 中有一枚比其他的或轻 或重.使用决策树描述一个 算法，使得只用一个天 平且最多进行三次比较 就可以确定出坏币并且 判断出它是 轻是重..
解：如下图：
补充：如果连通加权图 G的权值互不相同，则 G有唯一一棵最小生成树 .
证：反证法，设G有T1 , T2 两棵最小生成树，则 T1 , T2的权之和相等, 且存在边e1 , e2 权值不同. 此时e1 T1但e2 T2，e2 T2 但e1 T1 , 令T3 T1 e1 e2，T4 T2 e2 e1，则T3和T4亦是生成树. 由e1，e2的权不同可知：T3或T4中必有一个是权比 T1 ( T2 )小的树，得矛盾 .
11. 根据图回答下列问题 . (a.)对下列每个二进制序列 进行解码. (1)100111101 (2)10001011001(3)10000110110001(4)0001100010110000 (b.)对下列单词进行解码 . (1)den(2)need (3)leaden(4) penned
8. 明下列各题： 1.)若完全二叉树T有m个内点和k个叶子点，则m k 1. 2.)完全二叉树T的边数e，满足e 2(k 1).其中，k为叶子点数.
证： (1.)因为有m个内点的完全二叉树有 2m 1个顶点， 所以由顶点关系得： 2m 1 m k , 则m k 1. (2.)因为树T的边数(e) 顶点数(2m 1) 1, 所以e 2m 2(k 1).
3. 设无向图 G中有n个顶点 m条边，且 m n, 则G中必有圈.
设G有连通分支 T1 , T2 , , Tk (k 1) , 若G中无圈，则 Ti (1 i k ) 也无圈，所以 Ti 是树 .

树的实现及其应用树（Tree）是一种非常重要的数据结构，它在计算机科学中有着广泛的应用。

树是由节点（Node）和边（Edge）组成的一种层次结构，其中一个节点可以有零个或多个子节点。

树结构中最顶层的节点称为根节点（Root），最底层的节点称为叶节点（Leaf），除了根节点外，每个节点有且仅有一个父节点。

一、树的基本概念在树的结构中，每个节点可以有多个子节点，这些子节点又可以有自己的子节点，以此类推，形成了树的层次结构。

树的基本概念包括以下几个要点：1. 根节点（Root）：树结构的最顶层节点，没有父节点。

2. 叶节点（Leaf）：树结构的最底层节点，没有子节点。

3. 父节点（Parent）：一个节点的直接上级节点。

4. 子节点（Child）：一个节点的直接下级节点。

5. 兄弟节点（Sibling）：具有相同父节点的节点互为兄弟节点。

6. 子树（Subtree）：树中的任意节点和它的子节点以及这些子节点的子节点构成的子树。

7. 深度（Depth）：从根节点到某个节点的唯一路径的边的数量。

8. 高度（Height）：从某个节点到叶节点的最长路径的边的数量。

二、树的实现树的实现可以通过多种方式来完成，其中最常见的是使用节点和指针的方式来表示树结构。

在实际编程中，可以通过定义节点类（NodeClass）来表示树的节点，然后通过指针来连接各个节点，从而构建出完整的树结构。

下面是一个简单的树节点类的示例代码：```pythonclass TreeNode:def __init__(self, value):self.value = valueself.children = []```在上面的示例中，TreeNode类表示树的节点，每个节点包含一个值（value）和一个子节点列表（children）。

通过不断地创建节点对象并将它们连接起来，就可以构建出一棵完整的树。

三、树的遍历树的遍历是指按照一定顺序访问树中的所有节点。

NODE *t; char x; {if(t==NULL)
return(NULL); else
{if(t->data==x) return(t);
if(x<(t->data) return(search(t->lchild,x));
else return(search(t->lchild,x)); } }
——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储， 它是动态查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
讨论1：二叉排序树的插入和查找操作 例：输入待查找的关键字序列=（45，24，53，45，12，24，90）
二叉排序树的建立 对于已给定一待排序的数据序列,通常采用逐步插入结点的方 法来构造二叉排序树,即只要反复调用二叉排序树的插入算法 即可，算法描述为： BiTree *Creat (int n) //建立含有n个结点的二叉排序树 { BiTree *BST= NULL;
for ( int i=1; i<=n; i++) { scanf(“%d”,&x); //输入关键字序列
– 法2：令*s代替*p
将S的左子树成为S的双亲Q的右子树，用S取代p 。 若C无右子树，用C取代p。
例：请从下面的二叉排序树中删除结点P。
F P
法1:
F
P
C
PR
C
PR
CL Q
CL QL
Q SL
S PR
QL S
SL
法2:
F
PS
C
PR
CL Q
QL SL S SL

是 v1 v5,v7,v8,v9,v10,v11
v2,v3,v4,v6
否
§9.2.1 基本概念
二、有向树的性质 设有向树T=<V,E>, |V|=n, |E|=m，则:
① T 中无回路； ② T 是连通图； ③ m = n 1； ④ 删去T中任何一条边后，所得到的图不连通。
避圈法 破圈法
求最小生成树 (方法一)
Kruskal避圈算法 (从边的角度) (1)将各条边按照权值从小到大的顺序排列； (2)依次选取权值最小并且没有造成回路的边； (3)总共选取n-1条边（n为图中的结点数）。
求最小生成树(方法二)
破圈法 (从边的角度) 每次删去回路中权最大的边。
举例
（3） 由性质②来推证性质③。 对结点数进行归纳。 当n = 2时，m = n 1 = 1，由T的连通性质，T没有回路。如果两个结点之 间增加一条边，就只能得到唯一的一个基本回路。 假设n = k时，命题成立。则当n = k + 1时，因为T是连通的并有(n1)条边 ，所以每个结点的度数都至少为1，且至少有一个结点的度数为1。否则 ，如果每个结点的度数都至少为2 ，那么必然会有结点的总度数2m 2n ，即m n。这与m = n 1相矛盾，所以，至少有一个结点v的度数为1。 删除结点v及其关联的边，得到图T*，由假设知，图T*无回路。现将结点 v及其关联的边添加到图T*，则还原成T，所以，T没有回路。 在连通图T中，任意两个结点vi和vj之间必存在一条通路，且是基本通路。 如果这条基本通路不唯一，则T中必有回路，这与已知条件矛盾。进一步 地，如果在连通图T中，增加一条边(vi, vj)，则边(vi, vj)与T中结点vi和vj之 间的一条基本通路，构成一个基本回路，且该基本回路必定是唯一的。 否则，当删除边时，T中必有回路，这与已知条分支结点各1个，其余 结点均为叶结点，求树T中叶结点的数目？ 解 设树T中叶结点的数目为x，则树T的结点数目为(x+3) 。 由树的性质知，树T中边的数目为 (x+3) 1 = x +2。 由握手定理知：2(x+2) = 41 + 31 +1 + x1 可以解出： x = 5。

e10， 则分别产生初级回路e1e3e4， e1e4e5e2， e6e8e9，
•
•
•
e7e6e9e10。
•
第九章 树
这些初级回路有一个共同特点： 它们中均只含一条弦，
其余的边均是树枝， 我们称这样的回路为基本回路。 对于
G的每棵生成树T， m-n+1条弦对应着m-n+1个基本回路，
这些基本回路构成的集合称为对应T的基本回路系统。 显
例如图9.1.3中， T1和T2是图G的两棵生成树， 1 和2 是 分别对应于它们的余树。
第九章 树
图9.1.3 图的生成树和余树
第九章 树
由图9.1.3可见， G与T1、 T2的区别是G中有回路， 而 它的生成树中无回路， 因此要在一个连通图G中找到一棵 生成树， 只要不断地从G的回路上删去一条边， 最后所得 无回路的子图就是G的一棵生成树。 于是有如下定理。
这个问题的数学模型为： 在已知的带权图上求权最小 的生成树。
定义9.1.4 设无向连通带权图G=〈V, E, ω〉， G中带 权最小的生成树称为G的最小生成树(最优树)。
定理9.1.4 设连通图G的各边的权均不相同， 则回路 中权最大的边必不在G的最小生成树中。
证明略。
第九章 树
定理的结论是显然的， 由此寻找带权图G的最小生成 树， 可以采用破圈法， 即在图G中不断去掉回路中权最大 的边。
(5) 1， 1， 1， 1， 1， 2， 5
(6) 1， 1， 1， 1， 1， 3， 4
(7) 1， 1， 1， 1， 1， 1， 6
第九章 树
注意到， 不同构的度数列对应不同的树， 但对应同一 度数列的非同构的树不一定唯一， 所以对应(1)有T1， 对应 (2)有T2、 T3和T4， 对应(3)有T5和T6， 对应(4)有T7和T8， 对应(5)有T9， 对应(6)有T10， 对应(7)有T11(见图9.1.2)。

网络工程专业《离散数学》本科课程教学大纲（2022版）计算机学院2022年编制一、课程基本信息课程代码：128003课程名称：离散数学学分/学时：4.5学分/72学时课程类别：专业教育模块课程性质：专业基础课开课学期：第三学期授课对象：22网络工程本先修课程：高等数学、线性代数二、课程简介《离散数学》课程在讲授利用离散问题进行建模、数学理论、计算机求解方法和技术知识的同时，培养学生的数学抽象能力和严密的逻辑推理能力，通过本课程的学习，可以增强学生使用离散数学知识进行分析问题和解决实际问题的能力，为后续的计算机专业课程打下坚实的基础。

主要内容包括命题逻辑基本概念、等值演算、推理理论，一阶逻辑基本概念、推理理论，集合代数、二元关系、函数、基本组合计数公式、图的基本概念、欧拉图与哈密顿图、树、代数系统。

通过本课程的学习，学生能够掌握离散数学的基本知识、概念、公式及其应用，掌握离散数学中的常规逻辑推断方法，能够具备有效地收集、整理和分析数据的能力，并对所考察的问题作出推断或预测，以及应用数据挖掘和数据分析方法解决实际问题的能力，从而为今后学习、工作和发展建立良好的知识储备。

三、课程具体目标1.通过该课程的教学，了解并掌握计算机科学中普遍地采用离散数学中的一些基本概念、基本思想和基本方法。

通过本课程的学习将得到良好的数学训练，提高抽象思维能力和逻辑推理能力，掌握有关逻辑和证明的基本技巧和方法，理解并能初步运用离散结构进行问题建模和求解，从而为其学习计算机专业各门后续课程做好必要的知识准备，并为从事计算机的应用提供理论基础。

【毕业要求1.1工程知识】（M）2.掌握命题逻辑基本概念、等值演算、推理理论，一阶逻辑基本概念、推理理论，集合代数、二元关系、函数、基本的组合计数、图论等知识的相关的基本概念、基本表示和一些相关运算。

【毕业要求1.1工程知识】（M）3.在传统模式课堂上让学生自带移动智能终端（BYOD，Bring Your Own Device）开展即时互动反馈的信息化教学新模式，以满足教师和学生课堂教学互动与即时反馈需求，从而激发学生的独立思考、自主学习和探究的能力。

人教版二年级上册《9.2 练习课》同步练习卷一、填一填．1. 在横线上填上厘米或米。

2. 一个乘数是5，另一个乘数是8，积是________．3. 商店里有红、黄、蓝三种颜色的圆形纸。

豆豆要买2种颜色的纸有________种不同的选法。

4. 有3个数2、3、7，任意选取其中2个能组成________个不同的两位数。

5.6. 在〇里填上“>”“<”或“＝”．算一算。

用竖式计算。

连一连。

找规律，画出最后一个钟面上的时针和分针。

看图列式计算。

（1）买5本《口袋书》需要多少钱？答：买5本《口袋书》需要________元。

（2）买1本《恐龙世界》和1本《我的动物朋友》能省下6元钱吗？答：________省下6元钱。

（3）你还能提出其他数学问题并解答吗？像这样继续摆下去，第4个图形有多少根小棒？第8个呢？你能发现什么规律？参考答案与试题解析人教版二年级上册《9.2 练习课》同步练习卷一、填一填．1.【答案】厘米,米,厘米,米【考点】根据情景选择合适的计量单位【解析】根据生活经验以及对长度单位和数据大小的认识，结合实际情况可知计量飞飞的身高用“厘米”做单位，计量儿童床的长度用“米”做单位，计量铅笔的长度用“厘米”做单位，计量树的高度用“米”做单位，据此解答即可。

【解答】飞飞的身高是150厘米。

儿童床长2米。

铅笔长约18厘米。

树高约5米。

2.【答案】40【考点】表内乘法【解析】已知两个乘数，求它们的积，把它们相乘，根据乘法口诀“五八四十”求积即可。

【解答】5×8＝403.【答案】3【考点】握手问题【解析】红、黄、蓝3种颜色的纸，豆豆要买2种不同颜色的纸，可看作是两两握手，每种颜色的都要和另外的两种组合，3种颜色共有3种组合，据此列举即可。

【解答】红、黄；红、蓝；黄、蓝；共有3种。

答：豆豆要买2种颜色的纸有3种不同的选法。

故答案为：3．4.【答案】6【考点】简单的排列、组合【解析】当十位上的数是2是，可以组成23、27两个数；当十位上的数是3时，可以组成32、37两个数，当十位上的数是7时，可以组成72、73两个数，一共有2+2+2＝6（个）．【解答】当十位上的数是3时，可以组成32、37两个数（1）当十位上的数是7时，可以组成72、73两个数（2）一共有：2+2+2＝4+2＝6（个）答：能组成6个不同的两位数。

树及应用实验报告实验目的研究树结构及其应用，了解树的基本概念和常见操作，掌握树在实际问题中的运用。

实验内容1. 树结构的定义和特点2. 常见树的实现方式3. 二叉树及其操作4. 树的遍历算法5. 树在排序和搜索中的应用6. 树在图算法中的应用实验步骤与结果1. 树结构的定义和特点树是一种非线性的数据结构，由节点和边组成。

一个节点可以有多个子节点，但每个节点只有一个父节点。

树具有以下特点：- 树中只有一个根节点，它没有父节点。

- 每个非根节点有且只有一个父节点。

- 除了根节点外，每个节点可以有零个或多个子节点。

- 节点之间通过边连接。

2. 常见树的实现方式树可以通过链表或数组两种方式进行实现。

链表实现的树称为链式树，数组实现的树称为顺序树。

链式树的节点是通过指针进行连接的，每个节点包含数据和指向子节点的指针。

链式树的优点是插入和删除节点方便，缺点是访问节点需要遍历链表。

顺序树将节点存储在一个数组中，通过计算索引值来访问对应位置的节点。

顺序树的优点是访问节点快速，缺点是插入和删除节点困难。

3. 二叉树及其操作二叉树是一种特殊的树结构，每个节点最多有两个子节点。

二叉树的操作包括插入节点、删除节点、查找节点等。

二叉树的插入节点操作如下：1. 如果树为空，则将新节点作为根节点。

2. 如果新节点的值小于当前节点的值，则将新节点插入到当前节点的左子树中。

3. 如果新节点的值大于当前节点的值，则将新节点插入到当前节点的右子树中。

二叉树的删除节点操作如下：1. 如果要删除的节点是叶子节点，则直接删除它。

2. 如果要删除的节点只有一个子节点，则将子节点替代要删除的节点。

3. 如果要删除的节点有两个子节点，则将它的后继节点替代要删除的节点。

4. 树的遍历算法树的遍历算法包括先序遍历、中序遍历和后序遍历。

先序遍历按照根节点、左子树、右子树的顺序遍历树。

中序遍历按照左子树、根节点、右子树的顺序遍历树。

后序遍历按照左子树、右子树、根节点的顺序遍历树。

生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树.
否则删去圈上的任一条边, 这不破坏连通性, 重复进行 直到无圈为止,剩下的图是一棵生成树. 推论 1 设 n 阶无向连通图有 m 条边, 则 mn1. 推论 2 设 n 阶无向连通图有 m 条边, 则它的生成树的余树 有 mn+1 条边.
{0,10,010, 1010} 不是前缀码
例 在通信中，设八进制数字出现的频率如下：
0：25%
1：20%
2：15%
3：10%
4：10%
5：10%6：5% Nhomakorabea7：5%
采用 2 元前缀码, 求传输数字最少的 2 元前缀码 (称作最佳前
缀码), 并求传输 10n(n2)个按上述比例出现的八进制数字需
要多少个二进制数字？若用等长的 (长为 3) 的码字传输需要
推论 3 设
为 G 的生成树 T 的余树，C 为 G 中任意一个
圈，则 C 与
一定有公共边.
基本回路与基本回路系统
定义 设 T 是 n 阶 m 条边的无向连通图 G 的一棵生成 树，设 e1, e2, … , emn+1 为 T 的弦. 设 Cr 为 T 添加弦 er 产生的 G 中惟一的圈(由 er和树枝组成), 称 Cr 为对应 弦 er的基本回路或基本圈, r=1, 2, …, mn+1. 称{C1, C2, …, Cmn+1}为对应 T 的基本回路系统. 求基本回路的算法: 设弦 e=(u,v), 先求 T 中 u 到 v 的路径 uv, 再并上弦 e, 即得对应 e 的基本回路. 基本割集与基本割集系统定义 设 T 是 n 阶连通图 G 的一棵生成树, e1, e2, …, en1 为 T 的树枝，Si 是 G 的只含树枝 ei, 其他边都是弦

W(T)等于所有分支点的权之和
36
实例
例 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由下图给出，W(T)=38
7，4，5 4，3，4，5 2，2，3，4，5 7，9
37
小结

树与有序树
（ m=n1）
无向树及生成树
基本回路与基本回路系统 基本割集与基本割集系统 最小生成树

根树及其应用
23/60
例 求最小生成树
5 1 5 3 6 6 5 1 5 3 6 4 6 6 5 2 3 5 6 4 5 5 1 5 2 5 5 2 5
4
24/60
普里姆(Prim)算法
设置一个集合T，开始图上任选一点u0加入T，图顶点数 为n。重复以下工作n-1次:
• 在满足uT,vT的所有边中选边权w最小的 • 将v加入集合T中 • 输出边u ,v及边上的权 w
6
无向树的性质(续)
定理2 设T 是 n 阶非平凡的无向树，则T中至少 有两片树叶. 证 设T有x片树叶，由握手定理及定理1可知，
2(n 1) d (vi ) x 2(n x)
由上式解出x2.
7
例1 已知一棵树有5个4度顶点，3个3度顶点， 3个2度顶点，问有几个一度顶点？
(a)
(b) 只讨论(b)这样的所谓的“根 树”——有一个根的树。
28/53
根树
设T=(V,E)是一棵有向树，若仅有一个顶点的入度为0， 其余的顶点的入度均为1，这样一棵有向树我们称为 根树。 入度为0的顶点称为树根， 出度为0的顶点称为树叶， 出度不为0的顶点称为分枝点。 例
c d e a b d
有序树: 将根树同层上的顶点规定次序 r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元有序树: 有序的r元树 r元正则有序树: 有序的r元正则树

定理7-8.3设T为带权W,≤w2≤≤w的最优树，则-1带权W1,W2的树叶，Vwl2 Vw2是兄弟。-2 树叶vw,Vw2为儿子的分支点，其通路长度最长。-▣-证明思路：设在带权W1,W2,w的最优树中，V是通路 长-的分支点，v的儿子分别带权w,和W,故有-Lwx≥Lw1-Lw≥Lw2-若Lw>Lw1,将W、与w对调 得到新树T’,则-wT-wT=[wLW+W.LWjJ-[WLWx+wLWjJ-=LWWI-W+LWiWxi-Wx-Wi[LW-LW1<0-即wT<wT,与是最优树假设矛盾。故LwFLw。-同理可证LwxLw2。 此-LW-LW.-LW-LW2.-分别将W1,W2与w,w,对调得一最优树，VwVw2是兄弟。可
பைடு நூலகம்7-8根树及其应用根树及其应用
一、根树-1、有向树-定义7-8.1如果一个有向图在不考虑边的方向时-是一棵树，那么，该有向图称为有向树。
2、根树-定义7-8.2-一棵有向树，如果恰有一个-结点的入度为0，其余所有结点的入度都为1，-则称为根树 ooted tree。入度为0的结点称-为T的树根。出度为0的结点称为树叶，出度-不为0的结点称为分支点或 点。-根树的画法有：树根在下，向上生长；-树根在上，向下生长。
8.定理7-8.2设有完全二叉树有n个分支点，-且内部通路长度为总和为，外部通路长度总和-为E,则-E=I 2n。-口证明思路：对分支点采用数学归纳法。口-二、最优树-二叉树的一个重要应用就是最优树问题。给-定一组 w1,w2,,Wn。令一棵二叉树有n个-叶结点，并对它们分别指派w1,w2,.,w作-为权，则该二叉树称为 权二叉树。
习惯把有向树的根画在最上方，边的箭头全指-向下，则可以省略全部箭头，树根到一个结点的有-向通路的长度称为该 的层数。所有结点的最大层-数称为树高。-0-01-●-V2-02-U4-b6-U5-04-v3-78-g10-Ug-U8