软件技术基础：树与叉树

1、2.5树与二叉树树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间 存在明显的分支和层次关系。2.5.1 树的定义及其存储结构1. 树的定义和术语树是由n个(n >0)结点组成的有限集合T,其中有且仅有一个结点称 为根结点(root)，其余结点可以分为m(m>0)个互不相交的有限集合Ti, T2，Tm其中每个集合Ti本身又是一棵树，称为根结点root的子树。 当n=0时称为空树 。矚慫润厲钐瘗睞枥庑赖。这是一个递归的描述，即在买偶数树时又用到树本身这个术语。图 2.33所示为一棵树，A为根结点，期于结点分为三个不相交的子集Ti, T2, T3,它们均为根结点A下的三棵

2、树，而这三棵树本身也是树 。聞創沟燴鐺險爱氇谴争。图2.33树用二元组关系来定义树为Tree=(T,R)数据结构树(Tree)由数据元素集合T及各种R组成，其中T是具有相同 类型的数据元素集合T =x 1, X2，Xn。若T为空集(T二?)，则R二？, 称为空树，否则R是T上某个二元关系H的集合，即R=H。H的描述如 下： 残骛楼諍锩瀨濟溆塹籟。(1) 在T中存在唯一的称为根的元素root，它在H关系下无前趋。 若root工？，则存在m个子集Ti, T2，T(m>0),对任意 的j zk(1 <j,k <m), 有Tj ATk= ?，则存在唯一的数据元素Xi Ti(1 <

3、;i <m),满足<root,x i> H。 酽锕极額閉镇桧猪訣锥。 对应于 Ti, T2，Tm, H-<root , xi>,，<root , xm>，满 足vroot , Xi> H, H2,，Hm(m>0)，对任意的 j k(1 <j,k <m) 有H nHk= ? , H满足在Ti上的二元关系。因此(T i , Hi)也是一棵符 合本定义的树，称为根root的子树 。彈贸摄尔霁毙攬砖卤庑。树结构中常用的术语有.结点(node):表示树中的元素。.结点的度(degree):结点拥有的子树数，如图2.33中结点A的 度为3,

4、 C的度为1。一棵树中最大的结点度数为这棵树的度，图2.33 中树的度为3。 謀荞抟箧飆鐸怼类蒋薔。.叶子(leaf):度为零的结点，又称为端结点。.孩子(child):除根结点外，每个结点都是其前趋结点的孩子。.双亲(parents):对应上述孩子结点的上层结点称为这些结点的双 亲。例如图2.33中，D是A的孩子，A是D, C, B的双亲 。厦礴恳蹒骈時盡继價 骚。.兄弟(sibling):同一双亲的孩子。.结点的层次(level):从根结点开始算起，根为第一层，根的直接 后继结点为第二层,其余个层次依次类推。例如图2.33 中共分为4层。茕桢广鳓鯡选块网羈泪。.深度(depth):树中结点

5、的最大层次数。图2.33中树的深度为4。.森林(forest):是m(m>0)棵互不相交的树的集合。.有序树：树中结点在同层中按从左至右有序排列、不能互换的称为 有序树，反之称为无序树。2. 树的存储结构仅讨论链式存储结构。异构型：节省存储空间，运算不便。同构型：运算方便，浪费空间。假设有一棵具有n个结点的k叉树，则有nk个指针域，其中有用的指针 域为n-1个，因此空链域个数为nk-(n-1)=n( k-1)+1个 。鹅娅尽損鹤惨歷茏鴛賴。图234树的链式结构不同的k值进行比较比"喘）T =12n+l3nn+12nk越大，空链域比例越高，k=2时比例最低，因此着重讨论二叉树结构

6、。2.5.2二叉树及其性质1. 二叉树定义及其存储结构二叉树是n(n >0)个结点的有限集合，它或为空树n=0)，或由一个 根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成籟丛妈 羥为贍贲蛏练淨。通常用具有两个指针域的链表作为二叉树的存储结构其中每个结点由 数据域(data)、左指针域(L child)和右指针域(R child) 组成，即預頌圣鉉儐歲龈讶骅籴L childdataR child二叉树的链表结构如图2.35(b)所示心)(b)图2.3 5二叉树2. 二叉树的基本性质(1) 二叉树的第I层上至多有2i-1 (i >1)个结点。1 , 21-1 . 2, 22-

7、1 :(2) 深度为h的二叉树中至多含有2h-1个结点。1, 21-1 . 2, 22-1 20+21+22+23+2h-1 =1+2 0+21+22+23+2h-1 -1(3) 在任意二叉树中，若有n°个叶子结点，n2个度为2的结点，则必有：no=n2+1。每增加一个度为2的结点，叶子结点就增加一个。3. 几种特殊形式的二叉树(1) 满二叉树：深度为h含有2h-1个结点的二叉树为满二叉树。图2.36所示为一棵深度为4的满二叉树。完全二叉树如果一棵n个结点的二叉树，按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1n编号完全一致, 则称该树 为完全二叉树，如图2.3

8、7(a)所示；而图2.37(b) 就不是完全二叉树。 渗釤呛俨匀谔鱉调硯錦。6(710) (11砂 Q2)(时图2.37完全二叉厠与非完全二丈树(3)平衡二叉树平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树:它 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度 之差的绝对值不超过1。图2.38(a)为平衡二叉树，(b)为不N2 3S平街二叉树与非平衡二叉柳4. 一般树转换为二叉树(1) 在兄弟结点之间加一连线；(2) 对每个结点，除了与它的第一个孩子保持联系外去除与其它孩 子的联系；以树根为轴心，将整棵树顺时针旋转45 °。图29 F树海换为二叉拥D)ABCDEFGCBD

9、AEGF图2-40遍历二叉树二叉树的遍历遍历是指遵循某条搜索路线，依次访问某数据结构中的全部结点，而且每 个结点只被访问一次。1. 遍历二叉树的定义DLR, LDR LRD, DRL，RDL，RLD六种遍历形式。若规定先左后右，则归并成下述三种形式：DLR:先序遍历LDR:中序遍历LRD:后序遍历以图2.40中的二叉树为例，三种遍历结果为: 先序：中序： 后序：GG1CC1DD1FFFFFF1BBBBBB1B1B1B1EE1E1E1E1E1E1E1E1E1AAAAAAAAAAAA1A1A1A1A1A1A1A1A1A1A1A1A1ABCDEFG先CBDAEGF中CDBGFEA后2. 遍历算法PR

10、OORDER(p)/ 先序遍历/1.if (p<>nil) then2. write(data(p); /访问根结点/遍历左子树遍历右子树3. PROORDER (L child(p);/4. PROORDER (R child(p);/FRFR1BRBR1ERER1ER1ER1ER1ER1ARARARARARAR1AR1AR1AR1AR1AR1AR1AR1AR1ABC顎轮烂蔷。G擁締凤袜备訊INORDER(p)/ 中序遍历1.if (p<>nil) then2. INORDER(L,child(p); /遍历左子树3. write (data(p); /访问根结点7/

11、5. ReturnFRFR1BRBR1ERER1ER1ER1ER1ER1ARARParARARAR1AR1AR1AR1AR1:AR1:AR1AR1AR1C B D AEGFPOSTORDER(p)/ 后序遍历1.if (p<>nil) then2. POSTORDER(L,child(p); /遍历左子树/3. POSTORDER(R,child(p); /遍历右子树/4. write (data(p); /访问根结点7/5. ReturnFRFR1BRBR1ERER1ER1ER1ER1ER1ARARARARARAR1:AR1AR1AR1AR1AR1AR1:AR1AR1CDBG F

12、 E A 贓熱俣阃歲匱阊邺镓騷。统计二叉树中的叶子结点数/p指向根结点count为计数器，初值为01.if (p<>nil) then2. if (Lchild(p)=nil) and (R child=nil)3. the n count co unt +14. COUNTLEFT(L,child(p);5. COUNTLEFT(R,child(p);6. return(co unt)2.5.4二叉树的应用1. 二叉排序树(1)定义二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据均小于根结点的数据值；右子树上所有结点的数据值均大于或 等于根结点的数据值。左子

13、树和右子树又各是一棵二叉排序树。图2.41在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列，如 图2.41 中的二叉排序树，中序遍历可得到有序序列 2,3,4,8,9,9,10,13,15,18,21。蜡變黲癟報伥铉锚鈰赘。(2) 二叉排序树的生成二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向 二叉排序树中插入新的结点。对任意的一组数据元素序列R1, R2,，Rn,要生成一棵二叉排序 树的过程为：<1>令R1为二叉排序树的根结点。<2>若R><R1,令R2为R1的左子树的根结点；否则R2为R1的右子 树的根结点。<3>R3,

14、，Rn结点的插入方法同上。二叉排序树插入算法如下：INSERBET(t,b) /将数值b插入根结点指针为t的二叉排序树中此 函数返回值为指向根结点t的指针/ 買鲷鴯譖昙膚遙闫撷凄。1.if (t=n il) then /生成一个新结点其数值域为b/2. GETNODE(t); data(t)b;L child(t)nil;Rchild(t)nil 綾镝鯛駕櫬鹕踪韦辚翟。3. else if (b<data(t) then4. L child(t) j|NSERTBET(L child(t),b)插入左子树/5. else6. R child(t)j|NSERTBET(R child(t)

15、,b) /插入右子树/7. return(t)图2.42所示为序列10 , 18 , 3, 8,12 , 2 , 7, 3构成一棵二叉排删除二叉排序树上的结点删除二叉排序树上的一个结点，也就是要在已排好序的序列中删 除一个元素，因此要求删除一个结点后二叉树仍然是一棵二叉排序树。 驅踬髏彦浃绥譎饴憂锦。删除二叉排序树上结点过程较插入过程复杂，按照被删除结点在 二叉排序树中的位置，可以有以下几种情况：<1>被删除结点是叶子结点则删除后不会影响整个二叉排序树的 结构，因此只需修改它双亲结点的指针即可。<2>被删除结点P只有左子树Pl或右子树Pr，此时只要将左子树 或右子树直接

16、成为其双亲结点F的左或右子树即可，见图2.43(a)所 示。猫虿驢绘燈鮒诛髅貺庑。<3>若被删除结点P的左右子树均为非空。这是要循着P的左子 树的根结点C,向右一直找到结点S,要求S的右子树为空。然后将S 的左子树改为结点Q的右子树，将S结点的数据域值取代P结点的数 据域值，删除前后如图2.43(b)© 所示 。锹籁饗迳琐筆襖鸥娅薔。<4>若被删除的结点为二叉排序树的根结点则删除后应修改根结图N伯二叉排序树剛除程算法如下：DELNODE(t,p,f)/t 为根结点指针p指向被删除结点f指向其双亲 当 p=t 时 仁nil/構氽頑黉碩饨荠龈话骛。l. fag O

17、/fag=O需要修改F结点指针,fag=1 不需修改2.if (L child(p)二 nil) then sR child(p)/p为叶子或左子树为空/ s为所要替代p 的子树輒峄陽檉簖疖網儂號泶。3. else if (R child(p)=nil) then sL child(p)/p的右子树为空/4. else qp；s L child(p)p 的左右子树均非空75. while (R child(s)<>nil) do6. q s;s JR child(s)/ 寻找 s 结点/7. if (q=p) then L child(q)L child(s)8else R chi

18、ld(q) L child(s)9. data(p) data(s) /s值代替 p 值/10. RET(s); fag 1 / 释放 s 结点/11.if (fag=0) then /修改 F 结点指针12if (f=nil) then ts/ 被删除结点为根结点/13. else if (L child(f)=p)then L child(f)s14. else R child(f) s15. RET(p) / 释放结点 p/16. return2. 哈夫曼树 哈夫曼树又称最优树，是一类带权路径最短的树。(1) 树的路径长度从树中一个结点到另一个结点之间的分支数目称为这对结点之间的路 径长

19、度。树的路径长度是从树根到每个结点的路径长度之和。路径长 度用PL表示，图2.44中(a)(b)两棵树的路径长度分别为: 尧侧閆繭絳 闕绚勵蜆贅。(a) PL=0+1+2+2+3+4+5=17 ；(b) PL=0+1 + 1+2 X4+3=13。图九44耦|的路程长度在任何二叉树中，都存在如下情况:路径为0的结点至多只有1个；路径为1的结点至多只有2个；路径为k的结点至多只有2k个。 因此，n个结点的二叉树路径长度满足PL吃幌去log 21+log 22+log 23+log 24+log 25+log 26+log 27+log 28+识饒鎂錕缢灩筧嚌严淒。=0+1+1+2+2+2+2+3+

20、 从上述关系可知，具有最小路径长度的二叉树为完全二叉树。 (2)树的带权路径长度结点带权路径长度为该结点到树根之间的路径长度与结点上权 值的乘积。树的带权路径长度为树中叶子结点的带权路径长度之和，记作wpL=yK=1其中M为树中每个叶子结点的权值，l k为每个叶子结点到根结点的路径长度。WPL最小的二叉树称作最优二叉树或哈夫曼树。凍鈹鋨劳臘皆痫帚胫籴。 例如图2.45中的三棵二叉树，都有4个叶子结点a, b, c, d,分别具 有权值乙5，2，4，它们带权路径长度分别为:恥諤銪灭萦欢煬鞏鹜B(a) WPL=7*2+5*2+2*2+4*2=36(b) WPL=7*3+5*3+2*1+4*2=46

21、(c) WPL=7*1+5*2+2*3+4*3=35其中以(c)为最小，可以验证(c)为哈夫曼树。图2.45 的带叔路径长度(3) 哈夫曼树的构造原则：权值越大的叶子离根结点的距离越近。<1>由给定的n个权值w 1，他，Wn构成n棵二叉树的集合F=Ti， T2，其中每棵二叉树只有一个权值为W的根结点，如图 2.46(a)所示 。鯊腎鑰诎褳鉀沩懼統庫。<2>在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二 叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之 和，如图2.46(b)所示 。硕癘業颃诌攆檸攜驤蔹。<3>将新的二叉树假如F中，

22、去除原两棵根结点权值最小的树。<4>重复<2>,<3>两步骤，直到F中只含一棵树为止。这棵树就是哈 夫曼树，如图2.46(d)所示 。阌擻輳嬪諫迁择植秘騖。图2*哈夫曼树构造过程在计算机上实现上述算法，首先要确定存储结构，由于哈夫曼树中没有度 为1的结点，因此一棵有n个叶子结点的哈夫曼树共有2n-1个结点。结 点采用数组型链表结构每个结点由4个数据域组成，艮即氬魯躑竄贸恳彈瀘颔澩。date:存放结点权值L child: 左指针R child: 右指针Prnt:双亲指针算法如下：HUFFMAN(n,L child,R child,data,Prnt,w)w1:

23、 n存放n个权值L child1:m,R child1:m,data1:m,Prnt1:m,m=2 n-1T；0 /初始化/0初始化1. for i=1 to n2. dataiwi;L child(i)R child(i)3. e nd(i)4. for i=1 to (2*n-1) Prnti5. e nd(i)6. for k=n+1 to (2*n-1)7. SELECT(k-1,i,j) 从data1:k-1中选出双亲为零的两个权值最小的下标i,j釷鹆資贏車贖孙滅獅赘。8. datak datai+datej9. L childki; R childkj;10. Prnti k; P

24、rntj k;11. e nd(k)12. retur n对应图2.46中哈夫曼树的存储空间的初始状态为图2.47(a)，最终状态 为图 2.47(b)。PrutLchllR chll7000500020004000000000(«)dataPrutL chilR chil7700560025004500663411r25IS016(b)图茲的哈夫曼欄越算法实现123456(4) 哈夫曼树的应用最佳判定算法分数段0 5960 6970 7980 8990 100比例0.050.150.400.300.10分数段0-5960-697079808990-100比例0.050.150.40

25、0.300,10©图2*8几种不同的判断树COUNTLEFT(A,count)p指向根结点,coun为计数器,初值为01.if (pv>nil) then2. if (L child(p)=nil and (R child=nil)3. then couRtcount +14. *COUNTLEFT(L,child(p);COUNTLEFT(B,count)p指向根结点,counts计数器,初值为01.if (p<>nil) then2. if (Lchild(p)=nil and (R child=nil)3. then counttcount +14. *COU

26、NTLEFT(L,child(p);COUNTLEFT(C,count)p指向根结点,coun为计数器,初值为01.if (p<>nil) then2. if (Lchild(p)=nil and (R child=nil)3. then counttcount +14. *COUNTLEFT(L,child(p);COUNTLEFT(NIL,count)p指向根结点,coun为计数器，初值为01.if (p<>nil) then2. if (L child(p)=nil and (R child=nil)3. then counttcount +14. *COUNTL

27、EFT(L,child(p);5. COUNTLEFT(R,child(p);6. return5. COUNTLEFT(R,child(p);COUNTLEFT(NIL,count)p指向根结点,coun为计数器，初值为01.if (p<>nil) then2. if (L child(p)=nil and (R child=nil)3. then counttcount +14. *COUNTLEFT(L,child(p);5. COUNTLEFT(R,child(p);6. return6. return5. COUNTLEFT(R,child(p);COUNTLEFT(D,

28、count)p指向根结点,coun为计数器,初值为01.if (p<>nil) then2. if (Lchild(p)=nil and (R child=nil)3. then counttcount +14. *COUNTLEFT(L,child(p);COUNTLEFT(NIL,count)p指向根结点,coun为计数器，初值为01.if (p<>nil) then2. if (L child(p)=nil and (R child=nil)3. then counttcount +14. *COUNTLEFT(L,child(p);5. COUNTLEFT(R,child(p);6. return5. COUNTLEFT(R,child(p);COUNTLEFT(NIL,count)p指向根结点,coun为计数器，初值为01.if (p<>nil) then2. if (L child(p)=nil and (R child=nil)3. then counttcount +14. *COUNTLEFT(L,child(p);5. COUNTLEFT(R,child(p);6.