第7章树内容介绍V$7.1无向树及生成树V$7.2根树及其应用S7.1无向树及生成树1、定义7.1无向树森林（1）连通而不含回路的连通图称为无向树，或树，用T表示。（2）每个连通分支均是树的非连通无向图称为森林。（3）设T=<V，E>为一颗无向树，度为1的顶点称树叶，度为2的顶点称分支点。2、定理7.1设G=<V,E>，V=n，E=m，下列命题是等价的：（1）G连通而不含回路（2）G的每对顶点之间具有唯一的一条路径。（3）G是连通的且m=n-1。（4）G中无回路且m=n-1。（5）G中无回路，但在G中任何两个不相等的顶点之间增加一条边，就形成唯一的一条初级回路。3、定理7.2设T=<V，E>是n阶非平凡的树，则T中至少有2片树叶。4、定义7.2生成树设G=<V,E>是无向连通图，T是G的生成子图，并且T是树，则称T是G的生成树。（1）G在T中的边称为T的树枝。（2）G不在T中的边称为T的弦。（3）T的所有弦的集合的导出子图称为T的余树。ae8bobod0dCcddc(b)(a)(c)（b）是（a）的生成树，（c）是（b）的余树。5、定理7.3任何连通图G至少存在一棵生成树。1
1 第 7 章 树 内容介绍 ✓ §7.1 无向树及生成树 ✓ §7.2 根树及其应用 §7.1 无向树及生成树 1、定义 7.1 无向树 森林 （1）连通而不含回路的连通图称为无向树，或树，用T表示。 （2）每个连通分支均是树的非连通无向图称为森林。 （3）设T=<V,E>为一颗无向树，度为1的顶点称树叶，度为2的顶点称分支点。 2、定理 7.1 设 G=<V,E>,|V|=n,|E|=m,下列命题是等价的： （1）G连通而不含回路. （2）G的每对顶点之间具有唯一的一条路径。 （3）G是连通的且m=n-1。 （4）G中无回路且m=n-1。 （5）G中无回路，但在G中任何两个不相等的顶点之间增加一条边，就形成 唯一的一条初级回路。 3、定理 7.2 设T=<V，E>是n阶非平凡的树，则T中至少有2片树叶。 4、定义 7.2 生成树 设G=<V,E>是无向连通图，T是G的生成子图，并且T是树，则称T是G的生成树。 （1）G在T中的边称为T的树枝。 （2）G不在T中的边称为T的弦。 （3）T的所有弦的集合的导出子图称为T的余树。 （b）是（a）的生成树，（c）是（b）的余树。 5、定理 7.3 任何连通图 G 至少存在一棵生成树
推论1：设n阶无向连通图G有m条边，则m≥n-1。推论2：设n阶无向连通图G有m条边，T是G的生成树，T，是T的余树，T’中有m-n+1条边。87.2根树及其应用1、定义7.6根树一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树。（1）入度为0的顶点称为树根。（2）入度为1，出度为0的顶点称为树叶。（3）入度为1，出度大于0的顶点称为内点。（4）内点和树根统称为分支点。Vo8V3OVV1Vd45aQV5V4V4'O88?V6VTV7V6(a)(b)从树根到任意顶点v的通路长度称为v的层数，记为1（v）。层数最大的顶点层数称为树高。（1）V4的层数？2层。（2）（b）图树高？3。2、树的相关概念在一棵根树中：（1）若顶点a邻接到顶点b，则称b为a的儿子。（2）若b，c同为a的儿子，则称b，c为兄弟。（3）若a≠d，而a可达d，则称a为d的祖先，d为a的后代。3、定义7.7根子树设T为一棵根树，a为T的一个顶点，且a不是树根，称a及其后代导出的子图T”为T的以a为根的子树，简称根子树。2
2 推论1：设n阶无向连通图G有m条边，则m≥n-1。 推论2：设n阶无向连通图G有m条边，T是G的生成树，T’是T的余树，T’中 有m-n+1条边。 §7.2 根树及其应用 1、定义 7.6 根树 一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1， 则称此有向树为根树。 （1）入度为0的顶点称为树根。 （2）入度为1，出度为0的顶点称为树叶。 （3）入度为1，出度大于0的顶点称为内点。 （4）内点和树根统称为分支点。 从树根到任意顶点v的通路长度称为v的层数，记为l(v)。层数最大的顶点层 数称为树高。 （1）V4的层数？2层。 （2）（b）图树高？3。 2、树的相关概念 在一棵根树中： （1）若顶点a邻接到顶点b，则称b为a的儿子。 （2）若b，c同为a的儿子，则称b，c为兄弟。 （3）若a≠d，而a可达d，则称a为d的祖先，d为a的后代。 3、定义 7.7 根子树 设T为一棵根树，a为T的一个顶点，且a不是树根，称a及其后代导出的子图 T’为T的以a为根的子树，简称根子树
VoV2根子树22OV3aQQV5V1V4aQV5V4oV14600V6V74、定义7.8有序树如果将根树每一层上的顶点都规定次序，这样的根树称为有序树。032O福2-005、定义7.9设T为一棵树（1）若T每个分支点至多有r个儿子，称r元树。（2）若T每个分支点恰好有r个儿子，称r元正则树。（3）若r元树是有序的，称r元有序的。（4）若r元正则树是有序的，称r元有序正则树。（5）若T是r元正则树，且所有的树叶层数都相等，都等于树高，称r元完全正则树。（6）若r元完全正则树T是有序树，称r元有序完全正则树。6、定义7.10最优2元树设2元树T有t片树叶vl，v2，.*，vt，分别带权为wl，w2，.*，wt称w（T)=wi1（vi）为T的权，其中1（vi）为带权wt的树叶vi的层数，在所有的带权wl，w2，，wt的2元树中，带权最小的2元树称为最优2元树。7、Huffman算法给定实数wl,w2,..,wt，wl≤w2≤.≤wt。（1）以wl，w2为权的两片树叶为儿子，做一个新分支点，其权为w1+w2。（2）在w1+w2，w2，，wt中选出最小的两个权，让他们对应的顶点作为儿子，作一个新分支点，其权等于两个儿子权值之和。加入新分支点。（3）重复（2）直到2元树构建完成为止。3
3 4、定义 7.8 有序树 如果将根树每一层上的顶点都规定次序，这样的根树称为有序树。 5、定义 7.9 设 T 为一棵树 （1）若T每个分支点至多有r个儿子，称r元树。 （2）若T每个分支点恰好有r个儿子，称r元正则树。 （3）若r元树是有序的，称r元有序的。 （4）若r元正则树是有序的，称r元有序正则树。 （5）若T是r元正则树，且所有的树叶层数都相等，都等于树高，称r元完全 正则树。 （6）若r元完全正则树T是有序树，称r元有序完全正则树。 6、定义 7.10 最优 2 元树 设2元树T有t片树叶v1，v2，.，vt，分别带权为w1，w2，.，wt称W(T)=wil(vi) 为T的权，其中l(vi)为带权wt的树叶vi的层数，在所有的带权w1，w2，.，wt的 2元树中，带权最小的2元树称为最优2元树。 7、Huffman 算法 给定实数w1,w2,.,wt，w1≤w2≤.≤wt。 （1）以w1,w2为权的两片树叶为儿子，做一个新分支点，其权为w1+w2。 （2）在w1+w2,w2,.,wt中选出最小的两个权，让他们对应的顶点作为儿子， 作一个新分支点，其权等于两个儿子权值之和。加入新分支点。 （3）重复（2）直到2元树构建完成为止
8、例题7.2求带权为1、4、6、7、8、10的最优2元树。构造过程：第一步：14第二步：-第三步：7第四步：6第六步：第五步：57第七步：9、2元树的行遍对于一棵根树的每个顶点都访问一次且仅一次称为行遍。对2元有序正则树行遍方法：（1）中序行遍：左子树，树根，右子树。（2）前序行遍：树根，左子树，右子树。（3）后序行遍：左子树，右子树，树根。10、例题7.3（1）对下图二元树用中序、前序、后序三种方法进行行遍
4 8、例题 7.2 求带权为1、4、6、7、8、10的最优2元树。 构造过程： 9、2 元树的行遍 对于一棵根树的每个顶点都访问一次且仅一次称为行遍。 对2元有序正则树行遍方法： （1）中序行遍：左子树，树根，右子树。 （2）前序行遍：树根，左子树，右子树。 （3）后序行遍：左子树，右子树，树根。 10、例题 7.3 （1）对下图二元树用中序、前序、后序三种方法进行行遍
a.h0de中序行遍：dｃｅbfagih前序行遍：abcdefigh后序行遍：decfbghIa（2）对下图二元树用中序、前序、后序三种方法进行行遍ab0ed中序行遍：cdbeafg前序行遍：abcdegf后序行遍：dcebfga5
5 中序行遍：d c e b f a g i h 前序行遍：a b c d e f i g h 后序行遍：d e c f b g h I a （2）对下图二元树用中序、前序、后序三种方法进行行遍。 中序行遍：c d b e a f g 前序行遍：a b c d e g f 后序行遍：d c e b f g a