(1.3.6)--ch7-8离散数学离散数学.pdf
离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 7-8 根树及其应用根树及其应用 一、根树的定义一、根树的定义 定义定义7-8.1 如果一个有向图在不考虑边的方向时是一棵树如果一个有向图在不考虑边的方向时是一棵树,那么那么,这个有向图称为这个有向图称为有向树有向树.定义定义7-8.2 给定一个有向树给定一个有向树,若只有一个结点的入度为若只有一个结点的入度为 0,其余所有结点的入度都为其余所有结点的入度都为1,则称该树为则称该树为根树根树.在根数中在根数中,入度为入度为0的结点称为的结点称为根根，出度不为出度不为0 的结点称为的结点称为分枝点或内点分枝点或内点.出度为出度为0的结点称为的结点称为叶叶;在根树中在根树中,从根到任一结点的通路长度称为该结点的从根到任一结点的通路长度称为该结点的层次层次(级级).所有结点的层数最大的所有结点的层数最大的,称为根树的称为根树的树高树高.v0 是根是根;v0、v1、v2、v6、v7 是内点是内点;v3、v4、v5、v8、v9、v10 是叶是叶;树高为树高为3 例例1.判断下图是否是根树判断下图是否是根树,若是根树若是根树,给出其根、叶和内点给出其根、叶和内点,计计算所有结点所在的层数和树高算所有结点所在的层数和树高.解解.v0 层数为层数为0;v1、v2层数为层数为1;v3、v4、v5、v6、v7 层数为层数为2;v8、v9、v10 层数为层数为3;定义定义1.在根树中在根树中,若从结点若从结点 vi 到到vj 可达可达,则称则称vi是是vj的的祖先祖先,vj 是是vi的的后代后代；又若又若 是根树中的有向边是根树中的有向边,则称则称vi 是是vj的的父亲父亲,vj 是是vi的的儿子儿子；如果两个结点是同一个结点的儿子如果两个结点是同一个结点的儿子,则称这两个结点是则称这两个结点是兄弟兄弟.家族树家族树 定义定义2.若在有根树中规定了每一层上结点的次序若在有根树中规定了每一层上结点的次序,这样的这样的 根树称为根树称为有序树有序树.一般的一般的,在有序树中同一层中结点的次序为在有序树中同一层中结点的次序为从左向右从左向右.二、二叉树二、二叉树 定义定义7-8.4 在根树中在根树中,若每一个结点的若每一个结点的出度都小于或等于出度都小于或等于m,则称该树为则称该树为m叉树叉树.当当m=2时时,称为称为二叉树二叉树.若每个结点的若每个结点的出度恰好等于出度恰好等于m或等于或等于0,则称该树为则称该树为完全完全m叉树叉树.当当m=2时时,称为称为完全二叉树完全二叉树.若所有的若所有的叶结点的层次相同叶结点的层次相同,则称该树为则称该树为正则正则m叉树叉树.三叉树三叉树 完全二叉树完全二叉树 完全三叉树完全三叉树 例例2.甲、甲、乙两人进行球赛，规定三局两胜乙两人进行球赛，规定三局两胜.下图表示了比下图表示了比赛可能出现的各种情况赛可能出现的各种情况(图中结点标甲者表示甲胜图中结点标甲者表示甲胜,标乙者表标乙者表示乙胜示乙胜),这是一棵完全二叉树这是一棵完全二叉树.任何一棵有序树都可以转化为对应的二叉树任何一棵有序树都可以转化为对应的二叉树.树转化为二叉树的方法树转化为二叉树的方法:(1)从根开始从根开始,保留每个父亲同其左边孩子的连线保留每个父亲同其左边孩子的连线,撤销与别撤销与别 的儿子的连线的儿子的连线;(2)兄弟间用从左到右的有向边连接兄弟间用从左到右的有向边连接;(3)选定二叉树的左儿子和右儿子如下选定二叉树的左儿子和右儿子如下:直接处于给定结点直接处于给定结点 下面的结点作为左儿子下面的结点作为左儿子,对于同一水平线上与给定结点右邻的对于同一水平线上与给定结点右邻的 结点结点,作为右儿子作为右儿子,依次类推依次类推.例例1.将下图转化为二叉树将下图转化为二叉树.定理定理7-8.1 设有完全设有完全 m 叉树叉树,其树叶数为其树叶数为t,分枝点数为分枝点数为i,则则(m-1)i=t-1.证明证明:由假设知由假设知,该树有该树有i+t个结点个结点,由树的等价定义知由树的等价定义知,该树边数为该树边数为 i+t-1.又由握手定理及完全又由握手定理及完全 m 叉树的定义知叉树的定义知 即即 (m-1)i=t-1.mi=i+t-1,例例3.假设有一台计算机假设有一台计算机,它有一条加法指令可计算它有一条加法指令可计算3个数的个数的和和,如果要计算如果要计算9个数的和个数的和,至少需执行几次加法指令至少需执行几次加法指令?解解.用用3个结点表示个结点表示3个数个数,将表示将表示3数之和的结点作为它们数之和的结点作为它们的父亲结点的父亲结点,把把9个数看成树叶个数看成树叶,这样本题可理解为求一个完全这样本题可理解为求一个完全三叉树的分枝节点的个数问题三叉树的分枝节点的个数问题,由上述定理知由上述定理知,(3-1)i=9-1,即即 i=4,所以要执行所以要执行4次加法指令次加法指令.例例4.设有设有28盏电灯盏电灯,打算使用一个电源插座打算使用一个电源插座,问需用多少块问需用多少块有四个插座的接线板有四个插座的接线板?解解.把把28盏灯看成树叶盏灯看成树叶,将将4插头的接线板看成分枝点插头的接线板看成分枝点,这样这样本问题可理解为求一个完全四叉树的分枝点的个数本问题可理解为求一个完全四叉树的分枝点的个数i 的问题的问题,由上述定理知由上述定理知,有有 (4-1)i=28-1,即即 i=9,故一共需要故一共需要9块有四个插座的接线板块有四个插座的接线板.三、二叉树的应用三、二叉树的应用 1.最优二叉树最优二叉树 定义定义 给定一组数给定一组数 w1,w2,wn.令一棵二叉树有令一棵二叉树有 n 个叶结点个叶结点,并对它们分别指派并对它们分别指派 w1,w2,wn 作为权作为权,则称该二叉树为则称该二叉树为加权加权二叉树二叉树.图中所示是带权图中所示是带权 1,3,4,5,6的加权二叉树的加权二叉树 定义定义7-8.6.在权分别为在权分别为w1,w2,wn 的加权二叉树的加权二叉树 T 中中.若权若权是是wi 的树叶的树叶,其通路长度为其通路长度为L(wi),则称则称 1()niiiw L w 加权二叉树加权二叉树 T 的权的权,并记为并记为 w(T).为为 则此加权二叉树的权为：则此加权二叉树的权为：51+32+13+13=17 在所有带权在所有带权 w1,w2,wt 的二叉树中的二叉树中,w(T)最小的树称为最小的树称为最优二叉树最优二叉树.令令S=w1,w2,wt,w1 w2 wt,wi 是树叶是树叶 vi 所带的权所带的权(1)在在S中选取两个最小的权中选取两个最小的权 wi,wj,使它们对应的树叶使它们对应的树叶 vi,vj 做兄弟得一分支点做兄弟得一分支点 vij,令其带权令其带权 wij=wi+wj.(2)从从 S中去掉中去掉wi,wj,再加入再加入wij.(3)若若S中只有一个元素中只有一个元素,则停止则停止,否则转到否则转到(1).最优树的最优树的Huffman算法算法.例例4.求带权求带权 7,8,9,12,16的最优树的最优树 例例5.求带权为求带权为 2,3,5,7,8,9的最优树的最优树 给定一个序列的集合给定一个序列的集合,若其中没有一个序列若其中没有一个序列能是能是 另一个序列的前缀另一个序列的前缀,则称这个序列的集合为一个则称这个序列的集合为一个前缀码前缀码.定义定义7-8.7 2.前缀码问题前缀码问题 例如例如 000，001，01，10，11是前缀码是前缀码;而而00，01，001不是前缀码，不是前缀码，因为因为00是是001的前缀的前缀.定义定义.设设 =1 2 n 是长度是是长度是 n 的符号串的符号串,称其子串称其子串 1、1 2、1 2 n-1 分别为分别为 的长度为的长度为1、2、n-1的的前缀前缀.任意一棵二叉树的树叶都对应一个前缀码任意一棵二叉树的树叶都对应一个前缀码.定理定理7-8.5 二叉树对应的前缀码为：二叉树对应的前缀码为：00，0100，0101，011，11.任意一个前缀码都对应一棵二叉树任意一个前缀码都对应一棵二叉树.定理定理7-8.6 定理定理7-8.6应用举例应用举例:给定一个前缀码给定一个前缀码 000,001,01,1,求求出它对应的二叉树出它对应的二叉树.解解.1)先画出高度为先画出高度为3的完全二叉树的完全二叉树,并将每个结点连接的并将每个结点连接的 两条边分别用数字两条边分别用数字0和和1标记标记(如下图如下图).0 0 0 0 0 0 0 1 1 1 1 1 1 1 2)再将与前缀码中的序列对应的结点用方框加以标记再将与前缀码中的序列对应的结点用方框加以标记 0 0 0 0 0 0 0 1 1 1 1 1 1 1 3)最后将最后将有标记的结点的所有后裔以及从该结点出发的有标记的结点的所有后裔以及从该结点出发的边统统删去边统统删去,再从中删去所有未加标记的树叶再从中删去所有未加标记的树叶.这样得到的新这样得到的新的二叉树就恰好与所给的前缀码相对应的二叉树就恰好与所给的前缀码相对应.000 001 01 1 根树的思维形式注记图根树的思维形式注记图 根树根树 定义：一个结点入度为零其余结点入度为定义：一个结点入度为零其余结点入度为1 1(有向树有向树)二叉树二叉树 定义定义 应用应用:编码编码 树根树根 父亲父亲 儿子儿子 祖先祖先 兄弟兄弟 m叉树叉树 完全二叉树完全二叉树 正则二叉树正则二叉树 性质性质:数目关系数目关系 小小 结结 本节介绍了有向树、根树、本节介绍了有向树、根树、m叉树、完全叉树、完全m叉树、二叉树、叉树、二叉树、带权树、树的权、最优二叉树等概念及最优二叉树的带权树、树的权、最优二叉树等概念及最优二叉树的 Huffman算法算法.重点：掌握最优二叉树的重点：掌握最优二叉树的Huffman算法算法.
