。 。。
。
。 。。
。
。
第七章 图论
练习：把下面的有序树改写为二叉树。
。
。 。。
。
。 。 。。。
。。
。
知识点提示：
。。 。 。
课下自学
l 此方法可推广至有序森林到二叉树的转换。 l 此方法具有可逆性。
第七章 图论
根树应用2：完全m叉树的应用
定理7-8.1
设有完全m叉树，共有t片树叶，i 个分枝点，则 (m-1)i=t-1。
v在无向树中，度为1的结点称为树叶，度数大于或等于2的 结点称为分枝点或内点。
。
。。
。
。。 。
。 。。
。。 。 。
上节知识回顾
定理7-7.1 设G=<V,E>是n阶m条边的无向图,则下面各
命题是等价的：
（1）G是树。
。
（2）G中任意两个结点之间有且仅有一条路。 （3）G中无回路且m=n-1。
。
。
（4）G是连通的且m=n-1。
。。
第七章 图论
定理7-8.2
若完全二叉树有n个分枝点，且内部通路长度总和为L，外 部通路长度总和为E，则 E=L+2n。
证明： 对分枝点数目n进行归纳证明。 当n=1时，如右图所示，
L=0， E=2， 显然， E=L+2n成立。
。 。。
第七章 图论
定理7-8.2 若完全二叉树有n个分枝点，且内部通路长度总 和为L，外部通路长度总和为E，则 E=L+2n。
第七章 图论
例：把下。面的m叉树改写为二叉树。 。
。
。。直接处于给定结点下面的结 点，作为左儿子，对于同一
。
。。
。
。
。 。 水平线上与给定结点右邻的 结点，作为右儿子
。。
。
。
。
在同一层次中，兄
。 除了最左边的分枝弟结点之间用从左
。 。 结点外，删去所有到右的有向边连接
从每一个结点长出
。
的。分枝 。
第七章 图论
根树应用1：一棵m叉有序树改写为一棵二叉树方法
任何一棵有序树都可以改写为一个对应的二叉树：
① 除了最左边的分枝结点外，删去所有从每一个结点长 出的分枝。在同一层次中，兄弟结点之间用从左到右 的有向边连接。
② 选定二叉树的左儿子和右儿子如下：直接处于给定结 点下面的结点，作为左儿子，对于同一水平线上与给 定结点右邻的结点，作为右儿子，依次类推。
。。 。
(5) G是连通的且G中任何边均为桥。
(6) G中没有回路，但在任何两个不同的结点之间加一条
新边，在所得的图中得到唯一的一个含新边的圈。
本节内容安排
7-8 根树及其应用
1、根树的相关定义 2、根树的性质及应用
——二叉树、m叉树 3、小结
第七章 图论
定义7-8.1
设D是有向图，若不考虑D图边的方向时是一棵无向树， 则称D为有向树。
是灯，则根据定理7-8.1可知i 个需要分9枝块点。，则
(m-1)i=t-1
第七章 图论
根树应用3：二叉树的应用——最优树问题
定义7-8.5
在根树中，
l 一个结点的通路长度为从树根到此结点的通路中的边 数。
l 分枝点的通路长度称为内部通路长度。 l 树叶的通路长度称为外部通路长度。
。
。。 。 。。A 。
。
证明： 完全m叉树中结点总数为: t+i 也可表示为 mi+1
。。 。。。 。 。。
故得 (m-1)i=t-1
第七章 图论
例：有28盏灯，拟用一个电源插座，问至少需要多少块
四插座的接线板？
分析：
四插座——m叉树——m 接线板——分枝点——i 灯 ——树叶 ——t
请思考？
解将：四叉树的每个分枝点看作是完四全插m座叉的树接，线有板，t片树树叶叶看，作
度称为v的层次
V1。
l 层次最大结点的层次称为树高
l 平凡树也称为根树。
V5。V。2V。6。V3V。7。。V4。V8。
V9。。。
定义7-8.3：根树包含一个或多个结点，这些结
点中某一个称为根，其他所有结点被分成有
限个子根树
第七章 图论
根树的不同画法：
V9。
。 。 。 。 在根树中，若将T中层数相
同V的5 结点VT为6都有标V序定7树次。序，V则8 称
Ø 若每个结点的出度恰好等于r或0，则称T为完全r叉树。 Ø 若完全r叉树所有树叶层次相同，则称T为正则r叉树。 当r=2时，称为二叉树。
第七章 图论
例：
。
。。 。 。。 。。
。ቤተ መጻሕፍቲ ባይዱ
。。 。。。 。 。。
。
。。 。 。。 。
二叉树?
完全二叉树?
正则二叉树?
请证明
在完全二叉树中，边的总数等于2(nt-1)， nt为树叶数。
Ø 若vi 可达vj ,则称vi为vj的祖先,vj 为vi的后代
Ø 若vi邻接到vj（即< vi, vj >∈ E(T)），则称vi为vj的 父亲，而vj为vi的儿子
Ø 若vj , vk的父亲相同，则称vj与vk是兄弟。
第七章 图论
定义7-8.4
在根树T中， Ø 若每个结点的出度的小于或等于r，则称T为r叉树。
结点度
如：
V1。
的概念如前所讲
V2。V3。V4。 V5。V6。V7。 V8。
V9。
第七章 图论
定义7-8.2——根树
设T是n(n ≥ 2)阶有向树，若T中恰好有一个结点的入度 为0，其余结点的入度均为1，则称T为根树
lll 从入出入树度度根为不为到1为0出的T0的度结任为 结点意0点称的结称为结点为根点v内的称点单为或向叶分通枝路点长
V2。V3。 V4。 V1。
V1。 V2。V3。 V4。 V5。V6。V7。 V8。
V9。
由于各有向边的方向一致，故
常省略，并且树根在最上方。
V。1
V。2 V。3 。V4
。
V5
V。6
。
V7
。
V8
V。9
第七章 图论
补充定义
V1。 V2。V3。 V4。 V5。V6。V7。 V8。
V9。
设T为一棵非平凡的根树，vi,vj∈V(T),
第七章 图论
二叉树在实际生活中应用广泛。 比赛开始
。
例如：M和E两人进行象 棋比赛，规定一人连
。。
胜两盘或共胜三盘即
。 。 。。
为获胜，则所有可能 的比赛结果可用如下
。 。。 。
二叉树来描述。
。。 。。
。 。。 。
在m叉树中，二叉树相对来讲比较容易处理，所以常常把 m叉树的问题转换到二叉树上来讨论。
证明：
假设n=k-1时成立，即E`=L`+2(k-1)。
离散数学图论
上节知识回顾
G=<V,E>，其中V是非空 点集，E是边集
无向图 有向图
图 连通图 非连通图
无向树 有向树
树 ：是一种特殊的图
上节知识回顾
7-7 无向树及其性质 定义7-7.1
v连通无回路的无向图称为无向树，简称树,常用T表示树。 v平凡图称为平凡树。
v若无向图G的每个连通分支都是树，则称G为森林。