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

1、§7 树§7.1 树的概念【定义】 树（Tree）是n（n>0）个结点的有限集合T，它满足如下两个条件：(1) 有且仅有一个特定的称为根（Root）的结点；(2) 其余的结点可分为m（m0）个互不相交的有限集合，其中每一个集合又都是一颗树，并称为根的子树（Sub Tree）。 图7.1.1【基本术语】k1. 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度（degree）。如图7.1，A的度为3，C的度为1，F的度为0。2. 度为0的结点称为叶子（leaf）或终端结点。例如K、L、F、G、M、I、J。度不为0的结点称为分支结点或非终端结点

2、。除根结点外，分支结点也称为内部结点。3. 树的度是树内各结点的度的最大值，如图7.1中树的度为3。4. 结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲（parent）。如图7.1.1，B为A的子树的根，则B是A的孩子，而A则是B的双亲。同一个双亲的孩子之间互称为兄弟（sibling），例如B、C、D互为兄弟。将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支上的所有结点。例如，M的祖先为A、D、H。反之，结点的子树中的任一结点都称为该结点的子孙，如B的为E、F、K、L。5. 结点的层次（level）是从根开始定义起，根为第一层，根的孩子为第二层。若

3、某结点在第x层，则其子树的根就在x+1层。树中结点的最大层次称为树的高度或深度（depth）。如图7.1的树的深度为4。 图7.1.2 两棵不同的有序树6. 如果将树中的结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树,否则称为无序树。如图7.1.2。 7.森林（forest）是m（m0）棵互不相交的树的集合。§7.2 二叉树 图7.2.1§7.2.1 二叉树的定义二叉树（binary tree）是一种树型结构，它的每个结点至多只有二棵子树（即二叉树中不存在度大于2结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。（如图7.2.1） 满二叉树和完全

4、二叉树是两种特殊形态的二叉树。 满二叉树是指深度为k，且有2k-1个结点的二叉树。 完全二叉树是指深度为k，有n个结点，当且仅当每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时。 图7.2.4 非完全二叉树 图7.2.3 完全二叉树 图7.2.2 满二叉树§7.2.2 二叉树的性质性质1：在二叉树的第i层上至多有 个结点（i1）。性质2：深度为k的二叉树至多有 个结点（k1）。性质3：对任意一棵二叉树，如果度为2的结点数为n2，则其叶子结点数为 。性质4：具有n个结点的完全二叉树的深度为性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），则对任一结

5、点i （1in），有： 如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点是i div 2 如果2*i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子为2*i 如果2*i+1>n，则结点i无右孩子，否则其右孩子为2*i+1 参考答案及证明： 2i-1证明：利用归纳法 当i=1时，只有一个根结点，显然，2i-1=20=1 正确； 假设对所有的j，1j<i，命题成立，即第j层上至多有2j-1个结点； 由假设，第i-1层上至多有2i-1个结点，由于二叉树中的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上最大结点数的2倍，即2*2i-2=2i-1

6、2k-1 证明：深度为K的二叉树的最大结点数为 n2+1证明：设叶子结点数为n0，度为1的结点数为n1，则该数结点的总数为： n n0 + n1 + n2 （1）树中结点之间的连线称为分支。树中除根结点外，其余每个结点都有一个分支进入，设B为二叉树分支的总数，则有： B n 1 另一方面，这些分支是由度为1或2的结点射出的，所以： B n1 + 2n2 所以： n 1 n1 + 2n2 （2） 由式（1）和（2）得： n0 + n1 + n2 1 n1 + 2n2 即： n0 n2 + 1 证明：假设深度为K的完全二叉树的结点数为n，则根据性质2和完全二叉树定义有： 或 于是 k是整数 证明略

7、§7.2.2 二叉树的存储结构1顺序存储结构 图7.2.5 将二叉树的所有结点按一定的次序，存储到一片连续的存储单元中。这种结构，较适用于满二叉树或近似满二叉树。 如图7.2.5中完全二叉树的存储结构如下：ABCDEFGHIJKLM123456789101112131415 图7.2.6图7.2.6中的二叉树的存储结构如下：ABCDFGIM123456789101112131415可以看出，当二叉树较稀疏时，采用顺序存储将造成浪费。练习1) 如果完全二叉树最多有n层，那么存储该树的数组最少设_个单元；2) 某结点存储于Si，则存在双亲结点的条件： if _其双亲结点位于S _ ，其左

8、孩子结点位于S _ ；2链式存储结构 设计不同的结点结构可以构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域，如图7.2.7。 有时为了便于找到结点的双亲，则还可以在结点的结构中增加一个指向其双亲结点的指针域。用这两种结点结构所得的二叉树的存储结构分别称为二叉链表和三叉链表，如图7.2.8。 Lchild Data Rchild图7.2.7 ABCDEFG ABCDEFG(a) 二叉链表(b) 三叉链表图7.2.8 在具体应用中采用什么存储结构，除根据二叉树的形态之外，还

9、应考虑需进行何种操作。如找结点的双亲，在三叉链表中容易实现，而在二叉链表中则需从根中指针出发巡查。§7.3 遍历二叉树遍历二叉树（traversing binary tree）是指按某种搜索路径巡访树中每个结点，使得每个结点均被访问一次，且仅访问一次。根据二叉树的定义知，二叉树由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三个部分，则遍历了整棵二叉树。假设以D、L、R分别表示访问根结点、遍历左子树、遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。前三种分别称为先（根）序、中（根）序、后（根）序，后三种称为逆先序、逆中序、逆后序。通常只使

10、用前三种。先序遍历二叉树的操作定义为： 图7.3.1【例7.3_1】DLR（先序）：ABDICFMGLDR（中序）：DIBAFMCGLRD（后序）：IDBMFGCA（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；中序遍历二叉树的操作定义为： （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；后序遍历二叉树的操作定义为： （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点；遍历算法的描述形式随存储结构的不同而不同，若定义二叉树的存储结构如下： TYPE Pointer = node； node RECORD data ：char； lchild ，rc

11、hild ：pointer； END；先序遍历二叉树的递归算法如下： procedure preorder（p ：pointer）； beginif p<>nil then beginwrite (p.data)；preorder（p . lchild）；preorder（p . rchild）； end； end； 请完成中序遍历二叉树的递归算法： procedure inorder（p ：pointer）； begin end； 请完成后序遍历二叉树的递归算法： procedure postorder（p ：pointer）； begin end； 二叉树的三种遍历递归算法写得

12、非常精妙，只要对它稍加修改（主要在process语句处），就可的各种不同功能、用途的算法。如建立二叉树、查找结点、求每个结点所处的层次、求二叉树的高度、结点个数、复制二叉树等。§7.4 二叉树的建立 图7.4.1二叉树的建立可分先序、中序、后序三种方法。先序建立二叉树即输入结点数据的顺序按先序遍历所得的序列输入，输入“*”，表示该子树为空，如输入a b c * * d * * e * * ，得到的二叉树如图7.4.1。中序、后序类推。【练习】：请将前面遍历二叉树的算法稍加改动，分别写出先序、中序、后序建立二叉树的算法。§7.5 树的存储结构【思考】 请先不要看下面内容，如果

13、对一棵树（不定支数），你如何设计它的存储结构？一、 多重链表表示法每个结点的设m个指针域指向该结点的子数，m为树的度，结点结构如下： Data child1 child2 childm 很容易看出，多重链表的缺点是，当树中结点的子树数相差较大，许多结点的度小于m时，链表中有很多空指针域，空间较浪费。二、 双亲表示法这种存储结构利用每个结点（除根外）只有唯一的双亲的性质，以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。 dataABCDEFGHIparent011223555123456789其存储结构说明如下：TYPE tnode=recordData：

14、char；Parent：integer； end；VAR tree：array 1.maxnode of tnode； 三、 孩子表示法将每个结点的孩子结点用单链表链接起来，树中n个结点就有n条孩子链（叶子的孩子链为空），而将这n条链的头结点按顺序排列起来，组成一个线性表。ABCDEFGHI23456789123456789（a）孩子链表24785369123456789ABCDEFGHI011223555（b）带双亲的孩子链表图7.5.1如图7.5.1（a）孩子链表的存储结构说明如下： TYPE tlink=tnode; Tnode=RECORD Data : char; Next : tl

15、ink; End; Var tree: array 1.n of tlink;这种方法较适用于涉及孩子的操作，但不适用于涉及双亲的操作。我们可以采取改进的存储方法，在每一个孩子链的头结点中加一个域，存储其双亲结点的位置，如图7.5.1(b)。四、 孩子兄弟表示法又称二叉链表表示法，链表中结点的两个链接域分别指向该结点的第一个孩子结点和下一个兄弟结点。237896145结点结构说明如下：TYPE tlink=tnode; Tnode=RECORD Data : char; fch , nsib :tlink; END§7.6 森林与二叉树的转换 从上面树的孩子兄弟表示法可以看出，二叉树

16、和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找出唯一的一棵二叉树与之对应。将一般树或森林转换成二叉树表示，其目的是为了节省存储空间。§7.6.1 树或森林转换成二叉树树转换成二叉树的步骤如下： 将结点的所有兄弟连接在一起； 将所有不是连到最左子结点的子结点链表删除； 将结点的右子树向顺时针方向旋转45°。 （a） - （b）【图7.6.1】 （c）（d） （e）树转换成二叉树的步骤如下： 将森林中的各棵树分别转换成二叉树； 将所有转换而成的二叉树的树根相连；第二棵树作为第一棵树的右子树，第三棵树作为第二棵

17、树的右子树，以第一棵树的树根为根。算法描述如下:如果 FT1 , T2 , , Tm 是森林，则可按如下规则转换成一棵二叉树 Broot , LB , RB。（1）若F为空，即m0，则B为空树；（2）若F非空，即m0，则B的根root即为森林中第一棵树的根root(T1)； B的左子树LB是第一棵树转换而成的二叉树；B的右子树RB是从森林FT2 , T3 , , Tm转换而成的二叉树。 转换所得的二叉树，左支是孩子，右支是兄弟。§7.6.2 二叉树转换成森林或树二叉树转换成树其实是树转二叉树的逆过程，步骤如下： 将每个结点的右子树向逆时针方向旋转45°。 删除与左子树的横向

18、连接； 断开连接后的结点与左子树为兄弟，将其与双亲相连。如果Broot , LB , RB是一棵二叉树，则可按如下规则转换成森林FT1 , T2 , , Tm。（1）若B为空，则F为空；（2）若B非空，则F中第一棵树T1的根 root(T1) 即为二叉树B的根root； T1中根结点的子树森林是由B的左子树LB转换而成的森林； F中其余的树FT2 , T3 , , Tm 是由B的右子树RB转换而成的森林。【练习】将下列的树或森林转换成二叉树 （1） （2）【练习】将下列的二叉树转换成树或森林 （1） （3） （2） （4） （5） §7.7 树和森林的遍历一、 先序遍历森林若森林非空

19、，可按以下规则遍历： （1）访问第一棵树的根； （2）先序遍历第一棵树的子树；对上图森林进行遍历先序遍历序列：A B C D E F G H I J中序遍历序列：B C D A F E H J I G （3）先序遍历余下的其它树；二、 中序遍历森林若森林非空，可按以下规则遍历： （1）中序遍历森林中第一棵树的根结点 （2）访问第一棵树的根结点； （3）中序遍历余下的其它树；§7.8 哈夫曼树及其应用§7.8.1 扩充二叉树· 几个基本概念 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径；路径上的分支数目称为路径长度；树的路径长度是从树根到每一结点的路

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

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

22、+1 E k L + 2 ( L + 1 ) E k + L + 2 ( I k + 2 k ) + L + 2 I k + L + 2 k + 2 I k+1 + 2 ( k+ 1) 证毕。§7.8.2 最优二叉树（哈夫曼树）对扩充二叉树的外部结点均赋于一个权值，则称带权二叉树。其带权路径长度是每个外部结点到根的路径长度Lj 乘以权值Wj 的积之和。（a） （b） （c）图7. 8. 2115424521111542W1L1W2L2WmLm 如图7.8.2中的几种扩充二叉树的带权路径长度分别为： WEa 11×25×24×22×2 44 WE

23、b 4×25×311×32×1 58WEc 11×15×24×32×3 39规律：权值越大的外部结点离根结点越近，其带权路径长度最短，如（c）中的树。假设有n个权值W1 ,W2 , Wn， 试构造一棵有n个叶子结点的二叉树，每个叶子结点（外部结点）带权Wi ，则其中带权路径长度最小的二叉树称为最优二叉树或哈夫曼树。【例】将学生百分制成绩用A、B、C、D、E等级表示，成绩分别规律如下：分数05960697079808990100等级EDCBA比例数0.050.150.400.300.10a<60a<70a

24、<80a<90ABCDEyyyynnnna<80a<70a<90a<60ABCDEyyyynnnn(a)(b)若有10000个数据，按图(a)的判定过程进行转换，则有80%的数据至少要进行三次比较，完成10000个数据转换的比较次数为：10000×(1×5% + 2×15% + 3×40% + 4×(30%+10%) = 31500 次按图(b)的判定过程，完成10000个数据转换的比较次数为：10000×( 2×(10% + 30% + 40%) + 3×(5% + 15%)

25、= 22000 次显然，后者的判定过程效率比前者高。图(b)所示的判定过程是最优的，该二叉树称为最优二叉树，又称哈夫曼树。§7.8.3 哈夫曼树的构造如何构造哈夫曼树呢？哈夫曼（Huffman）最早给出一个带有一般规律的算法（哈夫曼算法）：(1) 根据给定的n个权值 W1 ,W2 , Wn 构成 n 棵二叉树的集合 FT1 ,T2 ,Tn，其中每棵二叉树Ti 中只有一个带权为Wi 的根结点，其左右子树均空。(2) 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新树的根结点的权值为其左右子树根结点的权值之和。(3) 在F中删除这两棵树，同时将新树加入F中。(4)

26、 重复(2)和(3)，直到F中只含一棵树为止。哈夫曼树的构建过程如图7.8.3所示。【图7.8.3】8534（a）653476（b）68（c）347656118834715（d）5611561183471526（d）§7.8.4 哈夫曼树的应用1 用于判断过程利用哈夫曼树可以构成最佳判断过程。例如，要对一批正整数按下表要求分类：数a出现概率属第几类a202/18120<a504/18250<a1005/183100<a7/184a20a50a100a属第三类a属第四类a属第二类a属第一类a20a50a100a属第四类a属第三类a属第二类a属第一类（a）（b）【图7.

27、8.4】其最佳判断过程如图7.8.4（b）所示，这是按哈夫曼树的原则来组织的判断过程，其平均执行时间最短。而图7.8.4（a）的判断平均时间最长。 2 哈夫曼编码一般通信中传送字符采用等长的ASCII码。例如，假设需要传送的报文内容为“ABACCDA”，它只有四种字符，只需两个字符的串就可分辩。设A、B、C、D的编码分别为：00、01、10、11，则上述报文的电文为“00010010101100”，总长14位，对方接收时，可按2位一分进行译码。DECAB图7.8.500001111如果对字符设计不等长的编码，且出现频率高的采用尽可能短的编码，则可以提高通信速度。例如设计A、B、C、D的编码分别

28、为：0、00、1、01，则上述电文可改为：“000011010”，长度仅为9。但这样的电文无法翻译，例如前四个字符“0000”就可有多种译法，或是“AAAA”，或是“ABA”，也可以是“BB”。因此，要设计长短不等的编码，则要求任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。可以利用二叉树来设计二进制的前缀编码。约定二叉树的左分支表示字符0，右分支表示字符1，树叶代表给定的字符，则可以从树根到叶子的路径上分支字符组成的字符串作为该叶子字符的编码。如图7.8.5所示。而哈夫曼树可使电文总长最短。以字符出现的频率为权，设计一棵哈夫曼树，由此得到的二进制前缀编码称为哈夫曼编码。下面讨

29、论具体的做法：设需要编码的字符集Dd1,d2,dn，设Wi 为di 在文本中出现的次数，则权值WW1,W2,Wn。将权值作为外部结点构造成哈夫曼树，取左支为0，右支为1，从根至叶路径上0、1组成的二进制串作为该叶结点字符的编码。将编码存入D对应的编码表。发送：根据字符从编码表中找到相应的编码发送出去，如发送abcbc字符串，发出的二进制串是111101100110。接收译码：对收到的二进制串，按顺序从哈夫曼树根走到叶结点，0走左支，1走右支，一直走到叶结点，就可译出一个字符。下次再从根开始对后续二进制位串进行译码，译出下一个字符，如此下去，直至译完为止。【练习】已知某系统在通信联络中只可能出现

30、八种字符 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行为字母B或Y，B代表进行报文编码，Y代表进行译码。第2行为整数n，代表报文/电文行数第3到n3行为报文/电文内容 输出格式：输出文件名：hfm.out 第1行为报文/电文行数n 第2到n+2行为报文/电文内容 （若非报文字符则该行输出error） 输入输出举例：输入：B2debbdhd输出：21111110101011110101111输入：Y1000101111输出：1fhd

31、【综合练习】1、 中序遍历问题描述按先序输入一棵二叉树，请输出其中序遍历。（树结点用不同的小写字母表示，“*”表示子树为空）。abcde样例输入：abc*d*c*输出：cbdae2、 求先序排列(NOIP2001普及组)问题描述给出一棵二叉树的中序和后序排列，求出它的先序排列。（约定树结点用不同的大写字母表示，长度8）。样例输入：BADC BDCA输出：ABCD3、有根树的同构（GDOI2003 day2-4）4、二叉树（GDKOI2005 day1-1）§7.9 树与并查集§7.8.1 引例【例】亲戚若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某

32、个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。数据输入：第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。数据输出：P行，每行一个Yes或No。表示第i个询问的答案为“具有”或“不具有”亲戚关系。样例：input.

33、txt6 5 31 21 53 45 21 31 42 35 6output.txtYesYesNo§7.8.2 并查集并查集是一种树形数据结构，用于集合的合并和查找。并查集的主要操作有： 1）判断两个元素是否属于同一个集合2）合并两个不相交集合3）路径压缩7.9.1判断两个元素是否属于同一个集合；合并两个不相交集用Si.father表示元素i的父亲结点S1.father=1S2.father=1S3.father=1S4.father=3S5.father=3S6.father=5123456由此用某个元素所在树的根结点表示该元素所在的集合。判断两个元素时候属于同一个集合的时候，只

34、需要判断他们所在树的根结点是否一样即可；也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可7.9.2路径压缩如果我们每次判断两个元素是否属于同一个集合，都采用寻根判断的话，当树是链的时候，需要O(N)的时间，于是可以采用“路径压缩”的方法，提高效率。123456123456路径压缩是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。之后，对任意两个元素是否属于同一个集合的判断，复杂度则降为O(1)。 参考程序：function getfather(v:integer):integer;beginif (fatherv=0) then getfather:

35、=velse beginfatherv:=getfather(fatherv);getfather:=fatherv;end;end;function judge(x,y:integer):boolean;var fx,fy : integer;beginfx := getfaher(x);fy := gefather(y);If fx=fy then judge := exit(true)else judge := false;fatherfx := fy;合并两个集合end;严歌苓说，人之间的关系不一定从陌生进展为熟识，从熟识走向陌生，同样是正常进展。人与人之间的缘分，远没有想像中的那么牢固，也许前一秒钟还牵手一起经历风雨，后一秒就说散就散，所以，你要懂得善待和珍惜。人与人相处，讲究个真心，你对我好，我就对你好，你给予真情，我还你真意，人心是相互的。两个人在一起，总会有人主动，但主动久了，就会累，会伤心，心伤了就暖不回来了，凡事多站在对方的角度想一想，多一份忍耐和谦就，就不会有那么多的怨气和误解，也少了一