高中信息技术-竞赛班数据结构专项培训教程-07树教案(20201123121210)

1、WOR格式6.专业资料完美整理7树 7.1 树的概念【定义】树（Tree ）是门（n0）个结点的有限集合 T，它满足如下两个条件:（1）有且仅有一个特定的称为根（Root ）的结点；（2）其余的结点可分为m （ m，0 ）个互不相交的有限集合， 颗树，并称为根的子树（Sub Tree ）。其中每一个集合又都是1.2.3.4.5.【基本术语】kO E树的结点包含一个数据元素及若干指向其子树的分支结点拥有的子树数称为结点的度 （degree ）。如图7.1, A的度为3 , C的度为1 , F的度为0度为0的结点称为叶子（leaf ）或终端结点。例如K、 I、J。度不为0的结点称为分支结点或非终端

2、结点。除根结点外，分支结点也称为内部结点。O G O H OIJJF、树的度 是树内各结点的度的最大值，如图7.1中树的度为孩子（Child ），该结点称为孩子的 结点的子树的根称为该结点的（pare nt如图7.1.1, B为A的子树的根，则同一个双亲的孩子之间互称为 将这些关系进一步推广，可认 为所有结点。例如，M的祖先为H。兄弟（sibli ngD是M的祖父 上的A、 D、图 7.1.1G、 M、双亲）。B是A的孩子，而A则是B的双亲。），例如B、C、D互为兄弟。结点的祖先是从根到该结点所经分支反之，结点的子树中的任一结点都称为该结点 的子孙，女口 B的为E、F、K、L。 结点的 层次（

3、level ）是从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第x层，则其子树的根就在x+1层。树中结点的最大层次称为树高度或深度（depth ）。如图的7.1如果将树中的结点的各子树看成从左到右是有次序的（即不能互换） 则称为无序树。如图7.1.2的树的深度为4。，则称该树为有序树, 否OAC BWOR格式o o o o图7.1.2两棵不同的有序树7. 森林 （forest ）是m （ m，0）棵互不相交的树的集合。专业资料完美整理 7.2 二叉树二叉树的定7.2.1义二叉树（bi narytree）是一种树型结构，至多只有二棵子树（即二叉树中不存在度大 于二叉树的子树有左右之分，

4、其次序不能任意颠 倒。7.2.1（如图）/OBC它的每个结点OO/ Vf2结点），并且，DEF GOO O OH IJO OO图7.2.1满二叉树和完全二叉树是两种特殊形态的二叉 树。满二叉树是指深度 k,且有2为-1完全二叉树是指深度为k , 深度为编号从1到n的结点-八 / 1 /O3对应时个结点的二叉树。有n个结点，当且仅当每一个结点都与k的满二叉树O2O5/O3O6O3OO6O 89图7.2.27.2.2性质1 :i10OOOOOOO12 11113 4 15满二叉树二叉树的性质 在二叉树的第层上至多有O89图7.2.3OOOO10性质2 :性质3 :1112完全二叉树O8 9图7.2

5、.4101112非完全二叉树 个结点（i 个结点（k 深度为k的二叉树至多有1）。2的结点数为n2，则其叶子结点数 为对任意一棵二叉树，如果度为。性质4 :具有n个结点的完全二叉树的深度 为n个结点的完全二叉 性质5 :如果对一棵有树log 2n 1的结点按层序编号（每层从左到右），则对任如果2*in ，则结 点i为叶子结点）；否则其左孩子无左孩子（结点i为2*i结点i( 11，则其双亲结点点i果是i div 2如果无右孩子，否则其右孩子2*i+1n，则结点 i为 2*i+1参考答案及证明:2 i-1证明：利用归纳法当i=1时，只有一个根结点，显然，2-1 =20=1正确；假设对所有的j, 1

6、 jnil the n beg inWOR格 式write (pdata)；preorder ( p A . Ichild);preorder ( p a . rchild);end;end ;请完成中序遍历二叉树的递归算法：procedure inorder( p : pointer)；begin end请完成后序遍历二叉树的递归算法：procedure postorder(p : pointer )；begi n end ；语句 二叉树的三种遍历递归算法写得非常精妙，只要对它稍加修改(主要在process处就可的各种不同功能、用途的算法。如建立二叉树、查找结点、求每个结点所处的层次、求二叉

7、树的高度、结点个数、复制二叉树等。 7.4 二叉树的建立二叉树的建立可分先序、中序、后序三种方法。先序建立二叉树即输入结点数据的 顺序按先序遍历所得的序列输入，输入“*”，表示该子树为空，如输入a b c * * d * * e *到的二叉树如图7.4.1，得中序、后序类推。eOWOR格式oc od图741专业资料完美整理WOR格 式专业资料完美整理【练习】：请将前面遍历二叉树的算法稍加改动，分别写出先序、中序、后序建立二叉树的算法。树的存储结构7.5【思考】请先不要看下面内容，如果对一棵树（不定支 数）、多重链表表示法每个结点的m个指针域指向该结点的子数，设，你如何设计它的存储结构?m为树的

8、度，结点结构如下:chil ? childm d2Data child1很容易看出，多重链表的缺点是，当树中结点的子树数相差较大，许多结点的 度小于链表中有很多空指针域，空间较浪费。、双亲表示法这种存储结构利用每个结茨（枷財）只有唯一的双亲的性质， 同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。储树的结点，pare nt011223555OO123456789DEFOOOGHI其存储结构说明如下：OOOCGdataABDEFHICBTYPE tno de=recordData :(Pare nt :char ；:integer；end;VAR tree : array 1.max

9、 no de of tnode孩子表示法L_ 一_:将每个结点的孩子结点用单链表链接起来，树 中为空） 表。*-*rxjn1 I/l2LJ L 3LJ1*耳而将这 链的头结点按顺序排列起来，组成420A.n 个卜结点有一个、线A0AB1A12就 i条孩子链（叶子的孩子链3WOR格式3C 164D 25E 276F 37G 5专业资料完美整理如图7.5.1( a)孩子链表的存储结构说明如下:TYPE tlink=Atnode;Tno de=RECORDData : char;Next : tli nk;En d;Var tree: array 1. .n of tli nk;这种方法较适用于涉及

10、孩子的操作，但不适用于涉及双亲的操作。我们可以采取改进的存7.5.1(b) 储方法，在每一个孩子链的头结点中加一个域，存储其双亲结点的位置，如图。四、孩子兄弟表示法又称二叉链表表示法，链表中结点的两个链接域分别指向该结点的第一个孩子结点 和下一个兄弟结点。结点结构说明如下：TYPEtli nk=At no de;Tno de=RECORD23456Data : char; fch , n sib :tli nk;END 7.6森林与二叉树的转换从上面树的孩子兄弟表示法可以看出，二叉树和树都可 则以二叉链表作为媒介可导出树与二叉树之间的一个对应 可以找出唯一的一棵二叉树与之对应。1 *-耳1树1

11、6将一般树或森林转换成二叉树表示，其目的是为了节省存储空间。 761树或森林转换成二叉树树转换成二叉树的步骤如下: 将结点的所有兄弟连接在一起； 将所有不是连到最左子结点的子结点链表删除; 将结点的右子树向顺时针方向旋转45。【图761】树转换OOOOOHIJODGEFOOa)BCOBOEOAODOBODOAD b)HI JO - O- OOOOOOH IJ/电乂:叉树的步骤如下:OOOOOF GH I将森林中的各棵树分别转换成二叉树；爪/ Q乞树的树根相连;(d)OIOH5将所有转换而成的 申寸的右子树，第三棵树第二棵树作为第一棵作为第二棵树的右子树？，以第一棵树的树根为根。/9 1算法描述

12、如下:/B =, LB ,rootRB。如果F = T 1 , T2 ,? , Tm 是森林，则可按如下规则转换成一棵二叉树(1 )若F为空，即m= 0 ,则B为空树；root(T1)；(2 )若F非空，即m 0,则B的根root即为森林中第一棵树的根B 的左子树LB是第一棵树转换而成的二叉树；转换而成的二叉树。B的右子树RB是从森林F = T 2 , T 3 ,? , T m 转换所得的二叉树，左支是孩子，右支是兄弟。 762二叉树转换成森林或树二叉树转换成树其实是树转二叉树的逆过程，步骤如下： 将每个结点的右子树向逆时针方向旋转45。 删除与左子树的横向连接； 断开连接后的结点与左子树为兄

13、弟，将其与双亲相连。如果 B = root , LB, RB是一棵二叉树，则可按如下规则转换成森F= T 1 , T2 ,林Tm。(1 )若B为空，则F为空；(2 )若B非空，则F中第一棵树T1的根 root(T 1)即为二叉树B的根root ;1中根结点的子树森林是B的左子树LB转换而成的森T由中其余的树F =,林；FTT,? , T 是由B的右子树RB转换而成的森林/ 2/ 3m【练习】将下列的树或森林转换成二叉树 ( /o AOBo COD OE oF OG(2)Aoo八J o Io o oo oDEHJKo ooF GMoL【练习】将下列的二叉树转换成树或森林(1) o 二/ AoB(

14、2)oAoBoCoDoEoAoboCoD、(5)ODo o oH IJ KL M N O 7.7树和森林的遍历-、先序遍历森林若森林非空，可按以下规则遍历：（1）访问第一棵树的根；（2）先序遍历第一棵树的子树；（3）先序遍历余下的其它树；二、中序遍历森林若森林非空，可按以下规则遍历：（1）中序遍历森林中第一棵树的根结点（2）访问第一棵树的根结点；（3）中序遍历余下的其它树；oDoao F对上图森林进行遍历 先序遍历序列：ABCDEFGHIJ中序遍历序列：BCDAFEHJIGoJ 7.8哈夫曼树及其应用 7.8.1扩充二叉树-几个基本概念从树中一个结点到另一个结点之间的分支构成这两个结点之间的路

15、径;路径上的分支数目称为 路径长度；树的路径长度是从树根到每一结点的路径长度之和；-扩充二叉树 是指将原二叉树中每个凡缺少左、右孩子的结点，均扩充为带左、右两个孩子。例如图7.8.1（ a ）中的二叉树变为扩充二叉树后如图7.8.1（ b ）所示，图中圆形结点是原来的，称为内部结点；方形结点是扩充结点，又称外部结点。J LJW ULbon(a)二叉树(b) 扩充二叉树内路径长度1(从根到每一内结点的路径长度之)：和1=1+2+1+2+3+2=11外路径长度E (从根到每一外结点的路径长度):之和E=3+3+2+3+4+4+3+3=25 一些规律：(1)若扩充二叉树n个内部结点，则有个外部结点；

16、有(2)扩充二叉树的内、外路径长I、E的关系E =。度是答案：(1 )(2) E=I+2nn+1证明：(1) . n + 1证明：根据二叉树性质3(对任意一棵二叉树，如果度为 2的结点数为n2,则其叶子结点数为n2+1 ) 扩充二叉树的内部结点的度都是2,有n个内部结点，则外部结点(即叶子)有 n+1个。证毕。(2) . E = I + 2n证明：(数学归纳法)当n=1时，由于只有一个内部结点，I = 0 , E = 2,所以E = I + 2n假设对于所有的k，都有E k = I k + 2 k当k+1时，即添加一个内部结点，设其路径长度L,为贝y I k+1 = I k+ LE k+1 =

17、 -L + 2 ( L + 1 )=(I k + 2 k ) + L + 2 I=I k+1 + 2 ( k+ 1)证毕。 7.8.2 最优二叉树(哈夫曼树)对扩充二叉树的外部结点均赋于一个权值，则称带权二叉树。其带权路径长度是每个外部结点到根的路径长度Lj乘以权值Wj的积之和。f II、I=11 + 22+?+ m mWL WLWL211451154251142(a)(b)(c )图782如图7.8.2中的几种扩充二叉树的带权路径长度分别为:WEa = 11 X 2 + 5 X 2 + 4 X 2 + 2 X 2 = 44WEb = 4 X 2 + 5 X 3 + 11 X 3 + 2 X

18、1 =58WEc = 11 X 1 + 5 X 2 + 4 X3+ 2 X 3 =39规律：权值越大的外部结点离根结点越近，其带权路径长度最短，如(c)中的树。假设有n个权值W1 ,W2 ,? , Wn,试构造一棵有n个叶子结点的二叉树，每个叶子结点(外部结点)带权 Wi，则其中带权路径长度最小的二叉树称为 最优二叉树 或哈夫曼树。【例】将学生百分制成绩用 A B、C、D、E等级表示，成绩分别规律如下：分数05960697079808990100等级EDCBA比例0.050.150.400.300.10数a60a80nynya70f a70a90r-ejyny ny 1nD- _a80yAl1

19、n CBA1厂n-a601Cya90 nED(a)BA(b)若有10000个数据，按图(a)的判定过程进行转换，则有80%的数据至少要进行三次比较， 完成10000个数据转换的比较次数为：10000X (1 X 5% + 2 X 15% + 3 X 40% + 4 X (30%+10%) = 31500 次按图(p)Y的判定过程、完成10000X ( 2.10000个数据转换的比较次数为、一 /X (10% + 30% + 40%) + 3X (5% + 15%) = 22000rJrw,显然，后者的判定过程效率比前者高。图(b)所示的判定过程是最优的，该二叉树称为最 优二叉树，又称哈夫曼树。

20、 7.8.3哈夫曼树的构造如何构造哈夫曼树呢？哈夫曼（Huffman ）最早给出一个带有一般规律的算法（哈夫曼算法）： 根据给定的n个权值W 1 ,W2 ,? , Wn构成n棵二叉树的集合F =T 1 ,T 2 ,? ,T n ，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且 置新树的根结点的权值为其左右子树根结点的权值之和。WOR格 式 在F中删除这两棵树，同时将新树加入 F中。4100专业资料完美整理重复(2)和(3)，直到F中只含一棵树口 一 .8.3 所示为图7.8.3 r。哈曼树的构建过程如7

21、(a)81173411(d) 7.8.4哈夫曼树的应用1.用一利用哈夫曼树可以构成最佳判断f过程。例如，要对一批正整数按下表要求分类:5/18350a 10050a 100100a100a7/18【图7.8.4】亠【图7.8.4WOR格式专业资料完美整理a 50a属第一类a属第四类a 50其最佳判断过程如图7.8.4( b)所示，这是按哈夫曼树的原则来组织的判断过程，其平均执行时间最短。而图7.8.4(a)的判断平均时间最长。2. 哈夫曼编码ASCII码。例如，假设需要传送的报文内容为 一般通信中传送字符采用等长的“ ABACCDA它只有四种字符，只需两个字符的串就可分辩。设A B、C D的编

22、码分别为：00、01、10、11,则上述报文的电文为“ 00010010101100 ”，总长14位，对方接收时，可按2位一分进行译码。如果对字符设计不等长的编码，且出现频率高的采用尽可能短的编码，则可以提高通信速度。例如设计 A、B、C、D的编码分别为：0、00、1、01，则上述电文可改为：“000011010”，长度仅为9。但这样的电文无法翻例如前四个字符“ 0000 ”就可有多种译法，或是译，“ AAAA , 或是“ ABA,也可以是“ BB ”。因此，要设计长短不等的编码，则要求任一字符的编码都不是另 一个字符编码的前缀，这种编码称为前缀编码。0 1可以利用二叉树来设计二进制的前缀编码

23、。约定二叉树的0 10 1左分支表示字符 0 ，右分支表示字符 1 ，树叶代表给定的A B C 01字符，则可以从树根到叶子的路径上分支字符组成的字符串作DE为该叶子字符的编码。如图7.8.5 所示。图 7.8.5而哈夫曼树可使电文总长最短。以字符出现的频率为权，设计一棵哈夫曼树，由此 得到的二进制前缀编码称为 哈夫曼编码。下面讨论具体的做法：设需要编码的字符集 D= d 1,d 2,? ,d n，设Wi 为 diW1,W2, ? ,Wn。将权值作为外部结点构造成哈夫曼树，取 左支为在文本中出现的次数，0,右支为1，从根至叶路径则权值W=上0、1组成的二进制串作为该叶结点字符的编码。将编码存入

24、D对应的编码表。发送：根据字符从编码表中找到相应的编码发送出去，如发送 abcbc字符串，发出的二进制串是 111101100110。WOR格 式接收译码：对收到的二进制串，按顺序从哈夫曼树根走到叶结点，0走左支，1走右支，直走到叶结点，就可译出一个字符。下次再从根开始对后续二进制位串进行译码，译出下一个 字符，如此下去，直至译完为止。【练习】已知某系统在通信联络中只可能出现八种字符a,b,c,d,e,f,g,h，其频率分别为:0.05，0.29 ，0.07 ，0.08 ，0.14 ，0.23 ，0.03 ，0.11，试设计哈夫曼编码，进行报文编码和译码。输入格式：输入文件名：hfm.in第1

25、行为字母B或Y， B代表进行报文编码，Y 代表进行译码。第2行为整数n，代表报文/电文行数第3到n + 3行为报文/电文内容输出格式：输出文件名：hfm.out第1行为报文/电文行数 n第2到n+2行为报文/电文 （若非报文字符则该行输出erro ）内容r入输出举例：输入：输出：B22111111010db|1011110101111bdhd1 W 1111 W 1 W 1111输入：输出：Y111fhd000101111【综合练习】1、中序遍历问题描述按先序输入一棵二叉树，请输出其中序遍历。（树结点用不同的小写字母表示，“ * ”表示子树为空）WOR格式输入：abc*d*c*be输出：cbd

26、aecd专业资料完美整理2、求先序排列(NOIP2001普及组)问题描述给出一棵二叉树的中序和后序排列，求出它的先序排列。 (约定树结点用不同的大写字母表示，长度w8)。样例输入：BADC BDCA输出：ABCD3、有根树的同构(GDOI2003 day2-4)4、二叉树(GDKOI2005 day1-1 ) 7.9树与并查集 7.8.1引例【例】亲戚若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某 个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。x的如果x,y 是亲戚，那么亲戚都是y的亲戚，y的亲戚也都是x的亲戚

27、。数据输入：第一行： 三个整数n,m,p ,( nv=5000,mv=5000,pv=5000),分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi, Mj , 1=Mi, Mjv=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi , Pj ,询问Pi和Pj是否具有亲戚关系。数据输出：P行，每行一个Yes或No。表示第i个询问的答案为“具有”或“不具有”亲 戚关系。样例：-output.in put.txttxt6 5 3Yes1 2Yes1 5No3 45 21 31 4 7.8.2 并查集 并查集是一种树形数据结构，用于集合的合并和查找。 并查集的主要操作

28、有：1）判断两个元素是否属于同一个集合2）合并两个不相交集合3）路径压缩7.9.1判断两个元素是否属于同一个集合；合并两个不相交集用Si.father 表示元素i的父亲结点S1.father =11S2.father=1S3.father=1S4.father =3S5.father =3S6 .father=5由此用某个元素所在树的根结点表示该元素所在的集合。判断两个元素时候属于同 一个集合的时候，只需要判断他们所在树的根结点是否一样即可；也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可7.9.2路径压缩候，需要0(N)的时间，于是可以采用“路径压缩”的方法1如果我们每次判断两个元素是否属于同一个集合，都采用寻根判断的话，当树是链的时1it it提高效率。3j456路径压缩是在找完根结点之后， 在递归回来的时候顺便把路径上元素的父亲指针都 指向根结点。之后，对任意两个元素是否属于同一个集合的判断，复杂度则降为0(1)。参考程序：fun cti on g