




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
DATA1065865ABCDEFG数据结构第6章树和二叉树主讲:李泽平2/1/20231学习提要
第6章树
1.熟练掌握二叉树的结构特性,了解相应的证明方法。
2.熟悉二叉树的各种存储结构的特点及适用范围。
3.熟练掌握各种遍历策略的递归和非递归算法。
4.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
5.熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。
6.了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。2/1/20232
1.数据的逻辑结构
2、数据的存储结构3、数据的运算:检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A顺序存储
B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题串、数组和广义表2/1/20233线性结构
A,B,C,·······,X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结2/1/20234
1.数据的逻辑结构
2、数据的存储结构3、数据的运算:检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A顺序存储
B链式存储线性表栈队树形结构图形结构数据结构的三个方面2/1/20235树形结构全校学生档案管理的组织方式2/1/20236ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGA2/1/202376树的定义和基本术语1.树的定义:由一个或多个结点组成的有限集合。仅有一个根结点,结点间有明显的层次结构关系。
A
C
GT2D
HIT3J
M
BEL
KT1F现实世界中,能用树的结构表示的例子:学校的行政关系、书的层次结构、人类的家族血缘关系等。2/1/20238树是一种常用的非线性结构。我们可以这样定义:树是n(n≥0)个结点的有限集合。
若n=0,则称为空树;否则,有且仅有一个特定的结点被称为根。
当n>1时,其余结点被分成m(m>0)个互不相交的子集T1,T2,...,Tm,每个子集又是一棵树。
由此可以看出,树的定义是递归。2/1/20239KLMEFGHIJBCDAA(a)(b)(c)2/1/202310介绍几个概念:
结点:数据元素的内容及其指向其子树根的分支统称为结点。
结点的度:结点的分支数。
终端结点(叶子):度为0的结点。
非终端结点:度不为0的结点。
结点的层次:树中根结点的层次为1,根结点子树的根为第2层,以此类推。
树的度:树中所有结点度的最大值。
树的深度:树中所有结点层次的最大值。
有序树、无序树:如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树。
A
C
G
T2D
HI
T3J
M
BEL
KT1F2/1/202311
森林:
是m(m≥0)棵互不相交的树的集合。在树结构中,结点之间的关系又可以用家族关系描述,定义如下:
孩子、双亲:
结点子树的根称为这个结点的孩子,而这个结点又被称为孩子的双亲。子孙:
以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先:
从根结点到该结点路径上的所有结点。
兄弟:
同一个双亲的孩子之间互为兄弟。
堂兄弟:
双亲在同一层的结点互为堂兄弟。
A
C
GT2D
HIT3J
M
BEL
KT1F2/1/202312
2.树的基本运算常用操作:(1)构造一个树CreateTree(T)
(2)清空以T为根的树ClearTree(T)
(3)判断树是否为空TreeEmpty(T)
(4)获取给定结点的第i个孩子Child(T,node,i)
(5)获取给定结点的双亲Parent(T,node)
(6)遍历树Traverse(T)
对树遍历的主要目的是将非线性结构通过遍历过程线性化,即获得一个线性序列。树的遍历顺序有两种,一种是先序遍历,即先访问根结点,然后再依次用同样的方法访问每棵子树;另一种是后序遍历。2/1/2023136.2二叉树(BinaryTree)1、二叉树的定义及其性质
(1)二叉树的定义二叉树的五种基本形态二叉树一种特殊的树型结构,特点是树中每个结点只有两棵子树,且子树有左右之分,次序不能颠倒。空二叉树
仅有根结点
右子树为空左子树为空左右子树均非空因为树的每个结点的度不同,存储困难,使对树的处理算法很复杂。所以引出二叉树的讨论。2/1/202314
二叉树是n(n0)个结点的有限集合。它或为空树(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。
特别要注意:二叉树不是树的特殊情况。aabb两棵不同的二叉树二叉树也可以用递归的形式定义。即:二叉树是n(n≥0)个结点的有限集合。当n=0时,称为空二叉树;当n>0时,有且仅有一个结点为二叉树的根,其余结点被分成两个互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。2/1/202315
1.从概念上讲,树,森林和二叉树是三种不同的数据结构,将树,森林转化为二叉树的基本目的是什么,并指出树和二叉树的主要区别。【5分】
树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是解释不同,也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树唯一表示,并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有二:一是二叉树的度至多为2,树无此限制;二是二叉树有左右子树之分,即使在只有一个分枝的情况下,也必须指出是左子树还是右子树,树无此限制,当只有一个孩子时,不知为左/右孩子。
2.树和二叉树之间有什么样的区别与联系?【4分】
树和二叉树逻辑上都是树形结构,区别有以上题1所述三点。二叉树不是树的特例。
3.请分析线性表、树、广义表的主要结构特点,以及相互的差异与关联。【10】
线性表属于约束最强的线性结构,在非空线性表中,只有一个“第一个”元素,也只有一个“最后一个”元素;除第一个元素外,每个元素有唯一前驱;除最后一个元素外,每个元素有唯一后继。树是一种层次结构,有且只有一个根结点,每个结点可以有多个子女,但只有一个双亲(根无双亲),从这个意义上说存在一(双亲)对多(子女)的关系。广义表中的元素既可以是原子,也可以是子表,子表可以为它表共享。从表中套表意义上说,广义表也是层次结构。从逻辑上讲,树和广义表均属非线性结构。但在以下意义上,又蜕变为线性结构。如度为1的树,以及广义表中的元素都是原子时。另外,广义表从元素之间的关系可看成前驱和后继,也符合线性表,但这时元素有原子,也有子表,即元素并不属于同一数据对象。2/1/202316
二叉树的基本运算(1)构造一棵二叉树CreateBTree(BT)(2)清空以BT为根的二叉树ClearBTree(BT)(3)判断二叉树是否为空BTreeEmpty(BT)(4)获取给定结点的左孩子和右孩子LeftChild(BT,node),RightChild(BT,node)(5)获取给定结点的双亲Parent(BT,node)(6)遍历二叉树Traverse(BT)2/1/202317A)
二叉树的第i层上至多有2i-1(i1)个结点。(2)二叉树的基本性质423167891011121314155第三层上(i=3),有23-1=4个节点。第四层上(i=4),有24-1=8个节点。2/1/202318性质1:二叉树的第i层上至多有2i-1(i1)个结点。证明:利用归纳法证明。二叉树的第1层只有一个根结点,所以,i=1时,2i-1=21-1=20=1成立。假设对所有的j,1≤j<i成立,即第j层上最多有2j-1个结点成立。若j=i-1,则第j层上最多有2j-1=2i-2个结点。由于在二叉树中,每个结点的度最大为2,所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍,即2i-2*2=2i-1。2/1/202319A)
二叉树的第i层上至多有2i-1(i1)个结点。
B)
深度为K的二叉树中至多含有2K-1个结点。(2)二叉树的基本性质423167891011121314155此树的深度h=4,共有24-1=15个节点。2/1/202320
性质2:深度为k的二叉树中至多含有2k-1个结点。证明:由性质1可以得出,1至K层各层最多的结点个数分别为:20,21,22,23,...,2K-1。这是一个以2为比值的等比数列,前n项之和的计算公式为:2/1/202321其中a1为第一项,an为第n项,q为比值。可以得到,该数列前K项之和为:2/1/202322A)
二叉树的第i层上至多有2i-1(i1)个结点。B)
深度为h的二叉树中至多含有2h-1个结点。C)
若在任意一棵二叉树中,有n0个叶子结点,有n2个度为2的结点,则:n0=n2+1(2)二叉树的基本性质423167891011121314155n0=8n2=72/1/202323性质3:对于任意一棵二叉树T,如果度为0的结点个数为n0,度为2的结点个数为n2,则n0=n2+1
证明:假设度为1的结点个数为n1,结点总数为n,B为二叉树中的分支数。因为在二叉树中,所有结点的度均小于或等于2,所以结点总数为:
n=n0+n1+n2(1)再查看一下分支数。在二叉树中,除根结点之外,每个结点都有一个从上向下的分支指向,所以,总的结点个数n与分支数B之间的关系为:n=B+1。2/1/202324又因为在二叉树中,度为1的结点产生1个分支,度为2的结点产生2个分支,所以分支数B可以表示为:B=n1+2*n2。将此式代入上式,得:
n=n0+n1+n2(1)
n=n1+2n2+1(2)用(1)式减去(2)式,并经过调整后得到:n0=n2+1。
2/1/202325
8910111213141545672312/1/202326
性质4:具有n个结点的完全二叉树的深度为[log2n]+1。其中,[log2n]的结果是不大于log2n的最大整数。证明:假设具有n个结点的完全二叉树的深度为K,则根据性质2可以得出:
2K-1-1<n≤2K-1
将不等式两端加1得到:
2K-1≤n<2K
将不等式中的三项同取以2为底的对数,并经过化简后得到:
K-1≤log2n<K
由此可以得到:log2n=K-1。整理后得到:K=log2n+1。2/1/202327
性质5:对于有n个结点的完全二叉树中的所有结点按从上到下,从左到右的顺序进行编号,则对任意一个结点i(1≤i≤n),都有:(1)如果i=1,则结点i是这棵完全二叉树的根,没有双亲;否则其双亲结点的编号为「i/2」。(2)如果2i>n,则结点i没有左孩子;否则其左孩子结点的编号为2i。(3)如果2i+1>n,则结点i没有右孩子;否则其右孩子结点的编号为2i+1。下面我们利用数学归纳法证明这个性质。我们首先证明(2)和(3)。当i=1时,若n≥3,则根的左、右孩子的编号分别是2,3;若n<3,则根没有右孩子;若n<2,则根将没有左、右孩子;以上对于(2)和(3)均成立。假设:对于所有的1≤j≤i结论成立。即:结点j的左孩子编号为2j;右孩子编号为2j+1。2/1/2023282i+2
2i2i+12i+22i+3i+12i2i+1i
i
i+12/1/202329由完全二叉树的结构可以看出:结点i+1或者与结点i同层且紧邻i结点的右侧,或者i位于某层的最右端,i+1位于下一层的最左端。可以看出,i+1的左、右孩子紧邻在结点i的孩子后面,由于结点i的左、右孩子编号分别为2i和2i+1,所以,结点i+1的左、右孩子编号分别为2i+2和2i+3,经提取公因式可以得到:2(i+1)和2(i+1)+1,即结点i+1的左孩子编号为2(i+1);右孩子编号为2(i+1)+1。又因为二叉树由n个结点组成,所以,当2(i+1)+1>n,且2(i+1)=n时,结点i+1只有左孩子,而没有右孩子;当2(i+1)>n,结点i+1既没有左孩子也没有右孩子。2/1/202330以上证明得到(2)和(3)成立。下面利用上面的结论证明(1)。对于任意一个结点i,若2i≤n,则左孩子的编号为2i,反过来结点2i的双亲就是i,而2i/2=i;若2i+1≤n,则右孩子的编号为2i+1,反过来结点2i+1的双亲就是i,而(2i+1)/2=i,由此可以得出(1)成立。2/1/202331(3)满二叉树一棵深度为K且有2k-1个结点的二叉树称为满二叉树。423167891011121314155特点:每一层上都含有最大结点数。2/1/202332423167891011125
非完全二叉树(4)完全二叉树423167891011125
完全二叉树特点:除最后一层外,每一层都取最大结点数,最后一层结点都集中在该层最左边的若干位置。2/1/202333(5)树与二叉树的区别A.树的结点个数至少为1,而二叉树的结点个数可以为0。B.树中结点的最大度数没有限制,二叉树结点最大度数为2。C.树的结点子树无左、右之分,二叉树的结点子树有明确的左、右之分。
二叉树树2/1/2023342、二叉树的存储结构
(2)链式存储结构T[16]若父结点在数组中i下标处,其左孩子在2*i处,右孩子在2*i+1处。11ABCFED
●●●●●●●●●124
8
910563712131415(1)顺序存储结构(1)顺序存储结构2h-1=24-1=15用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储,将造成存储的浪费。这种存储结构适用于完全二叉树2/1/202335(2)链式存储结构在顺序存储结构中,利用编号表示元素的位置及元素之间孩子或双亲的关系,因此对于非完全二叉树,需要将空缺的位置用特定的符号填补,若空缺结点较多,势必造成空间利用率的下降。在这种情况下,就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示:2/1/202336lchildDatarchildA^DB^C^^E^^F^图为一般二叉树的二叉链表结构AECBDF每个结点由数据域、左指针域和右指针域组成。2/1/202337这种存储结构的特点是寻找孩子结点容易,双亲比较困难。因此,若需要频繁地寻找双亲,可以给每个结点添加一个指向双亲结点的指针域,其结点结构如下所示。有关二叉树在链式存储结构下的操作算法将在随后介绍。2/1/202338链式存储结构的描述:Typedef
struct
BiTNode{
int
data;
Struct
BiTNode
*lchild,*rchild;}BiTNode,*BiTree;lchildDatarchildlchildDatarchildlchildDatarchild2/1/2023396.3二叉树的遍历
二叉树是一种非线性的数据结构,在对它进行操作时,总是需要逐一对每个数据元素实施操作,这样就存在一个操作顺序问题,由此提出了二叉树的遍历操作。
所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类:一类按根、左子树和右子树三个部分进行访问;另一类按层次访问。下面我们将分别进行讨论。2/1/202340
(1)按先左后右的原则,一般使用三种遍历:先序遍历(DLR):
访问根结点,按先序遍历左子树,按先序遍历右子树。中序遍历(LDR):
按中序遍历左子树,访问根结点,按中序遍历右子树。后序遍历(LRD):
按后序遍历左子树,按后序遍历右子树,访问根结点。二叉树为空时,执行空操作,即空二叉树已遍历完。2/1/202341下面我们再给出两种遍历二叉树的方法:(1)对一棵二叉树中序遍历时,若我们将二叉树严格地按左子树的所有结点位于根结点的左侧,右子树的所有结点位于根右侧的形式绘制,就可以对每个结点做一条垂线,映射到下面的水平线上,由此得到的顺序就是该二叉树的中序遍历序列。2/1/202342DGBAECHF
GHDEFBCA2/1/202343
(2)任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来,我们将它称为二叉树的包线,这条包线对于理解二叉树的遍历过程很有用。GHDEFBCA2/1/202344由此可以看出:(1)遍历操作实际上是将非线性结构线性化的过程,其结果为线性序列,并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列;(2)遍历操作是一个递归的过程,因此,这三种遍历操作的算法可以用递归函数实现。
ABCDFHEG2/1/202345(2)遍历算法先序遍历:DLR中序遍历:LDR后序遍历:LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCA2/1/202346VoidPreOderTraverse(BiTreeT){if(T!=NULL){
printf(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverser(T->rchild);}}/*先序遍历*/主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);2/1/202347中序遍历二叉树的递归算法:
voidinOrderTraverse(BiTreeT){if(T!=NULL){inOrderTraverse(T->lchild);
printf(T->data);
inOrderTraverse(T->rchild);}}后序遍历二叉树的递归算法:
voidPostOrderTraverse(BiTreeT){if(T!=NULL){PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf(T->data);}}2/1/202348
CDBFGEA
#5
若二叉树的先序遍历为:ABCDEFG(ABECDFGHIJ),中序遍历为:CBDAFEG(EBCDAFHIGJ),求二叉树的后序遍历序列。
先序遍历中的第一个元素必为二叉树的根结点。中序遍历中的根结点恰为左、右子树的分界点。先序遍历:ABCDEFG中序遍历:CBDAFEG2/1/202349
(3)遍历二叉树的应用
1)建立一棵二叉树
(在遍历过程生成结点,建立二叉树的存储结构,用链式存储结构)BiTree
CreatBiTree(){BiTreeT;
scanf(&ch);
if(ch==
)T=NULL;else{T=(BiTNode)malloc(sizeof((BiTNode));T->data=ch;/*生成根结点*/T->lchild=CreatBiTree();/*构造左子树*/T->rchild=CreatBiTree();/*构造右子树*/}return(T);}ADBCABDCABΦDΦΦCΦΦ按先序遍历2/1/202350ch=ATTAcreat(TL)ΛT=Λ,Creat(T)
返回creat(TR)Tch=ΦDΛ||=返回creat(TR)D=Tch=ΦΛΛ返回ch=DTTDcreat(TL)=||ΦΦcreat(TR)ch=CTTCcreat(TL)–+ch=BTTBcreat(TL)ΦTch=ΦBΦΛTCΛch=Φ–+返回creat(TR)TCΛch=ΦΛ+返回ATABΦΛABΛD||=ABΛDΛΛABΛDΛΛC–+BΦAABΛDΛΛCΛΛ2/1/202351
2)统计二叉树中叶子结点的个数方法:对二叉树进行遍历,判断被访问的结点是否叶子结点,若是叶子结点,则将计数器加1。实现算法:int
countleaf(BiTree){intn1,n2;
if(T==NULL) return(0);
elseif(T->lchild==NULL)&&(T->rchild==NULL)return(1);else{n1=countleaf(T->lchild);n2=countleaf(T->rchild);return(n1+n2);}}2/1/202352(4)按层次遍历二叉树实现方法为从上层到下层,每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。GHDEFBCA按层次遍历该二叉树的序列为:
ABCDEFGH2/1/202353二叉树用顺序存储结构表示时,按层遍历的算法实现A1B23C
D45EF67G(a)A1B23CD4E67F(b)图6-202/1/202354voidLevelOreder(QBTreeBT){for(i=1;i<=BT.n;i++)if(BT.item[i]!=’#’)Visite(BT.item[i]);}
2/1/202355访问过程描述如下:访问根结点,并将该结点记录下来;若记录的所有结点都已处理完毕,则结束遍历操作;否则重复下列操作。取出记录中第一个还没有访问孩子的结点,若它有左孩子,则访问左孩子,并将记录下来;若它有右孩子,则访问右孩子,并记录下来。二叉树用链式存储结构表示时,按层遍历的算法实现。2/1/202356在这个算法中,应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作;而取出记录的结点就是出队操作。这样一来,我们的算法就可以描述成下列形式:(1)访问根结点,并将根结点入队;(2)当队列不空时,重复下列操作:从队列退出一个结点;若其有左孩子,则访问左孩子,并将其左孩子入队;若其有右孩子,则访问右孩子,并将其右孩子入队;2/1/202357
6.4树和森林
1.树的存储结构
(1)双亲表示法树的双亲表示法主要描述的是结点的双亲关系。2/1/202358ABDCEFGHIJ2/1/202359类型定义:#defineMAX_TREE_NODE_SIZE100typedef
struct{
TEntryTypeinfo;
intparent;//双亲位置域}ParentNode;typedef
struct{
ParentNodeitem[MAX_TREE_NODE_SIZE];
intn;//树中当前的结点数目}ParentTree;2/1/202360这种存储方法的特点是寻找结点的双亲很容易,但寻找结点的孩子比较困难。算法实现举例:
int
Parent(ParentTree
T,intnode){if(node<0||node>=T.n)return-2;elsereturnT.item[node].parent;}2/1/202361(2)孩子表示法孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定,所以利用链式存储结构更加适宜。举例:2/1/202362root0A214^1C^2B35^3E^4D6^5F^6G789^7H^8I^9J^2/1/202363在C语言中,这种存储形式定义如下:#defineMAX_TREE_NODE_SIZE10typedef
struct
ChildNode{
intchild;//该孩子结点在一维数组中的下标值
struct
ChileNode*next;//指向下一个孩子结点}CNode;typedef
struct{
TEntryTypeinfo;//结点信息
CNode*firstchild;//指向第一个孩子结点的指针}TNode;2/1/202364
typedef
struct{
TNodeitem[MAX_TREE_NODE_SIZE];
intn,root;
//n为树中当前结点的数目,root为根结点在一维数组中的位置
}ChildTree;
这种存储结构的特点是寻找某个结点的孩子比较容易,但寻找双亲比较麻烦,所以,在必要的时候,可以将双亲表示法和孩子表示法结合起来,即将一维数组元素增加一个表示双亲结点的域parent,用来指示结点的双亲在一维数组中的位置。2/1/202365获取给定结点第i个孩子的操作算法实现:int
Child(ChildTreeT,intnode,inti){if(node<0||node>=T.n)return-2;
p=T.item[node].firstchild;j=1;while(p&&j!=i){p=p->next;j++;}
if(!p)return-2;
elsereturnp->child;}2/1/202366(3)孩子兄弟表示法孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系,其结点结构为:
其中,firstchild为指向该结点第一个孩子的指针,nextsibling为指向该结点的下一个兄弟,item是数据元素内容。举例:2/1/202367^H^I^J^^E^F^G^B^CD^A^T2/1/202368在C语言中,这种存储形式定义如下:typedef
struct
CSNode{
EntryTypeitem;
struct
CSNode*firstchild,*nextsibling;}CSNode,*CSTree;voidAllChild(CSTreeT,CSTreep)//输出树中p指针所指结点的所有孩子信息{q=p->fisrtchild;while(q){
printf(“%c”,q->item);q=q->nextsibling;}}2/1/202369voidLevelOrder(BTree*BT){if(!BT)exit;
InitQueue(Q);p=BT;//初始化
Visite(p);EnQueue(&Q,p);//访问根结点,并将根结点入队
while(!QueueEmpty(Q)){//当队非空时重复执行下列操作
DeQueue(&Q,&p);//出队
if(!p->Lchild){Visite(p->Lchild);EnQueue(&Q,p->Lchild);//处理左孩子
if(!p->Rchild){Visite(p->Rchild);EnQueue(&Q,p->Rchild);//处理右孩子
}}2/1/202370
2、将树和森林转换为二叉树
由于二叉树可以用二叉链表表示,为了使一般树也能用二叉链表表示,必须找出树与二叉树之间的关系。这样,给定一棵树,可以找到唯一的一棵二叉树与之对应。(1)树转换为二叉树方法:·对每个孩子进行从左到右的排序;
·在兄弟之间加一条连线;
·对每个结点,除了左孩子外,去除其与其余孩子之间的联系;
·以根结点为轴心,将整个树顺时针转45度。2/1/202371
I
A
B
C
DEF
G
H(b)
A
B
CDE
G
HFI(a)树转换为二叉树ABEFCDGHI(d)ABCDEFGHI(c)2/1/202372
A
B
CDE
G
HFI二叉树转换为树ABEFCDGHI(a)ABEFCDGHI(b)c若结点X是其双亲Y的左孩子,则把X的右孩子,右孩子的右孩子,…,都与Y用连线连起来,最后去掉所有双亲到右孩子的连线.2/1/202373
(2)森林转换为二叉
树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法:·将各棵树分别转成二叉树;·把每棵树的根结点用线连起来;·以第一棵树的根结点作为二叉树的根结点,按顺时针方向旋转。2/1/202374
二叉树转换为森林ADCBEFHIGJEFADCBHIGJADCBEFHIGJEFADCBHIGJ方法:·将二叉树转成若干棵二叉树;·将各棵树二叉树分别转成树;2/1/202375
6.6哈夫曼树及其应用
1、哈夫曼树
树的路径长度的概念:
(1)结点之间的路径长度:从一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。(2)树的路径长度:是从树的根到每一结点的路径长度之和。2/1/2023761245367PL=0+1+1+2+2+2+2=10树的路径长度用PL表示。2/1/2023771245367PL=0+1+1+2+2+2+2=101245C67PL=0+1+1+2+2+3+3=12树的路径长度用PL表示。2/1/202378
结点带权的路径长度:
从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度:
树中所有叶子结点带权路径长度之和。
abcd7524WPL=7*2+5*2+2*2+4*2=362/1/202379树的带权路径长度记作:
其中:Wk为树中每个叶子结点的权;
Lk为每个叶子结点到根的路径长度。abcd7524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉树就称作最优二叉树或哈夫曼树。2/1/202380abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35哈夫曼树(最优树)带权路径长度最小的二叉树就是哈夫曼树。公式:2/1/202381675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼树的构造例:给定权值{7,5,2,4},构造哈夫曼树。方法:(1)由原始数据生成森林;(2)在森林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树,其根结点的权值为左右子树根结点权值之和。规定左子树根结点的权值小于右子树根结点的权值。(3)将新的二叉树加入到森林F中,去除原两棵权值最小的树;(4)重复2、3步骤,直至F中只剩一棵树为止。注意:参看书中P146的例子。2/1/2023823、哈夫曼树的应用(1)判定树在解决某些判定问题时,利用哈夫曼树可以得到最佳判定算法。例1将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的,可用图(a)二叉树结构来实现。a<60
a<70
a<80
a<90
不及格中等良好优秀及格YNYNYNYN(a)输入10000个数据,则需进行31500次比较。2/1/202383分数0—5960—6970—7980—8990—99比例0.050.150.40.30.1070≤a≤80
a<60
及格中等良好80≤a<90
60≤a<70
不及格优秀YNYYYNNN(b)不及格Ya<90
a<80
a<70
a<60
优秀中等及格良好YNNN(c)YYY学生成绩分布不是均匀的情况:以比例数为权构造一棵哈夫曼树,如(b)判断树所示。再将每一比较框的两次比较改为一次,可得到(c)判定树。输入10000个数据,仅需进行22000次比较。2/1/202384146833442200001111T;ACS各字符编码是T;
ACS
000110110111上述电文编码:11010111011101000011111000011000方法:(1)用{2,4,2,3,3}作为叶子结点的权值生成一棵哈夫曼树,并将对应权值wi的叶子结点注明对应的字符;(2)约定左分支表示字符“0”,右分支表示字符‘1’(3)从叶子结点开始,顺着双亲反推上去,直到根结点,路径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制编码的逆序。(2)哈夫曼编码-----利用哈夫曼树构造通讯中电文编码(前缀码)例2:要传输的电文是{CAS;CAT;SAT;AT}要传输的字符集是D={C,A,S,T,;}每个字符出现的频率是W={2,4,2,3,3}注意:编码的总长度恰好为哈夫曼树的带权路径长。2/1/202385作业#1.有n个叶子结点的哈夫曼树,其结点总数为2n-12/1/20238635817115592728CDAEB00001111#2.
设电文中出现的字符为A,B,C,D,E,每个字母在电文中出
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 IEC TS 63346-1-1:2024 EN Low-voltage auxiliary power systems - Part 1-1: Terminology
- 【正版授权】 IEC 62386-105:2024 EN-FR Digital addressable lighting interface - Part 105: Particular requirements for control gear and control devices - Firmware transfer
- 【正版授权】 ISO/IEC TR 19583-24:2025 EN Information technology - Concepts and usage of metadata - Part 24: 11179-3:2013 Metamodel in RDF
- 2025-2030年中国锌系常温磷化液市场运营现状与发展前景分析报告
- 2025-2030年中国钒铁行业市场经营状况及投资战略研究报告
- 2025江西省安全员B证(项目经理)考试题库
- 2025-2030年中国软体家具市场运行态势及发展趋势分析报告
- 2025-2030年中国贝复舒行业前景展望及未来投资规划研究报告
- 2025-2030年中国蛋品加工市场运营状况及发展趋势分析报告
- 2025-2030年中国管道管产业前景趋势及投资战略研究报告
- 《工程合同管理与招投标实训》课程电子教案
- 肿瘤科疼痛一病一品
- 2024-2030年中国矿用锚杆行业发展现状需求分析报告
- 2024年1月浙江省高考英语真题试卷含答案
- 人民医院样本外送检测管理制度
- DG-TJ 08-2451-2024 电动自行车集中充电和停放场所设计标准
- DB3301-T 65.28-2024 反恐怖防范系统管理规范 第28部分:硬质隔离设施
- 心电监护仪的操作及注意事项 课件
- 11BS4排水工程华北标图集
- 电子备课教案(一二年级体育)
- 湖北省武汉市汉阳区2023-2024学年七年级下学期期末数学试题
评论
0/150
提交评论