|E(T1)|=|V(T1)|-1， |E(T2)|=|V(T2)|-1 故m=|E(T1)|+|E(T2)|+1
=|V(T1)|-1+ |V(T2)|-1+1 =n-1。
⑸ T连通的且m=n-1.
⑹ T无回路且m=n-1.
⑸⑹:只需证明T无回路。对T关于顶点 数归纳。
当n=1或n=2时，显然成立。
八.遍历二叉树 在二叉树的一些应用中, 常常要在树中查找具有某些
特征的结点,或者对所有结点逐一进行某种处理, 这就提 出了遍历二叉树问题. 即按照一定规律巡访树中每个结点 一次.
由于二叉树是一个非线性结构, 每个结点都可能在左右 两棵子树上, 为此要寻找一种规律, 以便使二叉树上结点 的信息排成一个线性队列上, 从而便于遍历.
⑷ T连通的,且每条边都是割边.
⑸ T连通的且m=n-1.
⑷⑸:关于点数用归纳法证明。
当n=1或2时，T是平凡图或K2，显然有m=n-1。 假设nk时结论成立，往证n=k+1时成立。
当n=k+1时。取T的一条边e，由⑷，e是割边，
所以T-e有两个分支T1和T2， 因为|V(T1)|k, |V(T2)|k, 所以，由归纳假设，有
⑴后序遍历左子树
⑵后序遍历右子树
⑶访问根结点.
后序遍历:32x2－×－x3x＋÷＋
九. 最优树(哈夫曼树 Huffman)
二叉树的一个重要应用就是最优树.
1.带权二叉树的定义:设有一组权值:w1, w2, w3,… , wm, 不仿设w1≤w2≤w3≤…≤wm, 设有一棵二叉树有m片 叶子,分别带有权值w1, w2, w3,… , wm,称此树为带权二 叉树.
此树是m叉树.
2.完全m叉树:在根树中,如果每个结点的出度都是m或者
等于0, 则称此树是完全m叉树.
3. 正则m叉树:在完全m叉树中,如果所有树叶的层次相 同,
则称之为v1 正 则m叉树. v1
v1
v2
v3 v2
v3 v2
v3
v4 v5 v6 v4 v5
N
取ej使得
ai=ej i=i+1
S∪{ ej}有回路?
|S|=n-1, 说明是树
Y
最后S={a1, a2, a3,… ,an-1}
j=j+1
边按升序排序:边(vi, vj)记成eij 边 e28 e34 e23 e38 e17 e24 e45 e57 e16 权1 1 2 2 2 3 3 3 4
a:b
<
=
a:c
a:c
> a:cFra bibliotek<=
< =>
=>
a轻 b重 c重 a:d c轻 b轻 a重
< => d重 全真 d轻
d)搜索树:八数码游戏:
283 164
75
283 64
17 5
283 14
765
…………………..
搜索策略: 宽度优先, 深度优先, 启发式搜索,….
Step2. 构造[Sk , Sk ], 若[Sk , Sk ] , 则G不连
通, 停止. 否则, 设
w(ek ) min w(e) ek vk vk' , vk Sk .

e[Sk , Sk ]

令
S k 1

Sk

{v
' k
},
Ek1 Ek {ek }.
置k=k+1. 返回Step1.
1.每个结点保留左儿子结点, 剪掉右边其分支. 被剪掉 的结点如下处理(重新嫁接). 2.同一个层次的结点, 从左到右依次画出(被剪掉的结 点 嫁接到它的哥哥结点上).
r
a
b
c d e f g h i jk l
r
a
b
c d e f g
h
i j k l
3.分支结点(内结点):度数大于1的结点. (b)
4.森林:一个无向图的每个连通分支都是树.如(b)
5.与树定义等价的几个命题 定理1给定图T, 以下关于树的定义是等价的. ⑴ T无回路的连通图. ⑵T无环且每对结点之间有一条且仅有一条路. ⑶ T无回路但在任一对不相邻的顶点间添加一条
新边e，则T+e包含唯一的回路. ⑷ T连通的,且每条边都是割边. ⑸ T连通的且m=n-1. ⑹ T无回路且m=n-1. 证明:⑴⑵:已知T是连通无回路图,所以T中无环。
v1 8 v8 7 v5 3 v4
4 2 v7 4
34 6 6 v6
Kruskal算法: 设G是有n个结点,m条边(m≥n-1)的连通 图. S=Φ i=0 j=1
将所有边按照权升序排序: e1, e2, e3,… ,em
S=S∪{ai} j=j+1
|S|=n-1 Y 输出S 停 N
v4 v5 v6 v7
定理1 T是棵完全m叉树, 有t个叶结点, i个分支结点,
则(m-1)i=t -1 . 证明:T的所有结点的出度总和为 mi. 入度总和(i-1)+t. 故 mi=i-1+t 所以(m-1)i=t-1
七. m叉有序树转化成二叉树 因为二叉树便于存贮, 也便于处理, 所以通常可以将多叉 树化成二叉树.方法是:
最小生成树很有实际应用价值.例如结点是城市名,边的权
表示两个城市间的距离, 从一个城市出发走遍各个城市,
如何选择最优的旅行路线.又如城市间的通信网络问题,如
何布线,使得总的线路长度最短.
例如:右图所示 2.求最小生成树算法 ---Kruskal算法: (贪婪算法)
v2 71
2 3 2
v3 51
v7
的一条边,则称vi是vj的父结点, vj是vi的子结点.
5.祖先结点与后裔结点: 在根树中,如果从vi到vj有路,则 称
vi是vj的祖先结点, vj是vi的后裔结点. 6.根树结点的层次:从根结点到某个结点的路径的长度,称
为该结点的层次. 同一层次的结点称为兄弟结点.
7.树高:从树根到各个叶结点的路径中, 最长路径的长度,
v2
v3
如果G中有回路,可以通过反复删去回路 v4
v5
中的边,使之既无回路,又连通.就得到生成树.
思考题:设G是有n个结点,m条边的连通图, 问要删去多少
条边,才得到一棵生成树?
三.赋权图的最小生成树
1.定义:一棵生成树中的所有边的权之和称为该生成树的
权. 具有最小权的生成树,称为最小生成树.
称为该树的高度(树高).
三.举例: a)语法树
主语
句子
谓语短语
冠词 形容词 名词 动词
宾语


The little boy
b)算术表达式树
((a+b)÷c)×(d－e) ÷
冠词 saw
The
×
－
名词
apple
+
c d e
a b
c)判定树:有四枚金币a,b,c,d,已知道三个是真的,最多一 个是假的,它们的外表完全相同,只是重量有点差别.给你 一架天平找出假币.
⑷ T连通的,且每条边都是割边.
⑵⑶:显然T无回路，否则对回路上的任一对顶 点都至少存在两条路，与⑵矛盾。设u，v是T 中任意两个不相邻的点，令e=uv，由⑵，T中 有一条唯一的u-v路，所以T+e中包含唯一的回 路。
⑶⑷:因为T无回路，所以T的每条边都是割边； 若T不连通，设T1，T2是T的两个分支，设 uV(T1), vV(T2), 则uvE(T)，显然T+uv 不存在回路，与⑶矛盾。
假设nk时结论成立，往证n=k+1时成 立。
因为T连通，所以(T)1，由m=n-1及 d(v)=2m得，T中至少存在一点u，使 得d(u)=1。考虑T’=T-u，显然T’连通， 且|E(T’)|=|V(T’)|-1，由归纳假设，T’ 无回路，所以T无回路。
⑹ T无回路且m=n-1. ⑴ T无回路的连通图. ⑹k由⑴⑹2:得。假，对设任T不意连的通Ti，，设Ti是T1无, T回2,路…,的T连k为通T图的，连所通以分T支i是，树则，
例：求图G的最小生成树。 v2
1
3
v1
2
4 4
v4 2
v5
2
4
v3
破圈法
----Prin算法的对偶方法. 最适合于在图 上作业. 当图比较大时, 还可以几个人同 时在各个局部作业.
Step0. 令G0=G. k=0.
Step1. 若Gk不含圈, 转Step2. 若Gk中
含有圈C.
v6
Prin算法(边割法)
实质: 在n-1个边割集中, 取每个边割集的一条 权最小的边, 构成G的一个生成树.
定义：[Sk , Sk ] {uv | u Sk，v Sk}。 Step0. 设v为V的任一顶点. 令S0={v}, E0=,
k=0.
Step1. 若Sk=V, 结束. 以Sk为点集, Ek为边集 的图即是G的最优树. 否则转Step2.
v6 v5
二.根树:如果一棵有向树,恰有一个结点的入度为0,其余
所有结点的入度均为1,则称此树为根树.
v1
1.树根:入度为0的结点. 2.叶:出度为0的结点.
v2
v3
3.分支结点(内结点):出度不为0的结点. v4 v5 v6
4.父结点与子结点:如果<vi,vj>是根树中
有三种遍历方式 1.先序遍历 2.中序遍历 3.后序遍历
1.先序遍历 ⑴访问根结点. ⑵先序遍历左子树
+