庄朝晖-数据结构参考讲义

1、数据结构第6章 树和二叉树 - 2第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树与等价问题 6.6 赫夫曼树及其应用 6.7 回溯法与树的遍历 6.8 树的计数6.4 树和森林树的存储结构森林和二叉树的转换树和森林的遍历1、树的存储结构树的双亲表示法树的孩子表示法树和森林的孩子兄弟表示法树的双亲表示法和二叉树的双亲链表相类似，结点中只设一个指向双亲的指针，并对无序树不需要设子树位置的标志。所有结点存储在一个地址连续的存储空间中。树的双亲表示法indexdataParent0A-11B02E13H24I25J26C07

2、D08F79G710K911树的双亲表示法#define MAX_TREE_SIZE 100typedef struct / 结点结构ElemType data;int parent;/ 双亲位置域 PTNode;typedef struct / 树结构PTNode nodesMAX_TREE_SIZE;int r, n;/ 根的位置和结点数 PTree;树的孩子表示法让每个结点的“子树根”构成一个线性表，以链表作它的存储结构，令其头指针和结点的数据元素构成一个结点，并将所有这样的结点存放在一个地址连续的存储空间里，所构成的树的存储结构称为树的孩子链表。当然，在需要的情况下，也可以如同双亲链表

3、，在结点结构中加上双亲的地址号。树的孩子表示法J树的孩子表示法typedef struct CTNode / 孩子结点int child;struct CTNode *next; *ChildPtr;typedef struct ElemType data; / 结点的数据元素ChildPtr firstchild; / 孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n, r;/ 结点数和根结点的位置 CTree;树和森林的孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。树中每个结点都设有两个指针，其一，firstchil

4、d 指向该结点的“第一个”子树根结点，其二，nextsibling 指向它的下一个兄弟结点。这里的第一个和下一个都没有逻辑上的含义，只是在构造存储结构时自然形成的次序。树和森林的孩子兄弟表示法树和森林的孩子兄弟表示法对森林来说，可认为各棵树的根结点之间是一个 “兄弟”关系右图是上例中的数去掉根之后的森林对应的二叉链表树和森林的孩子兄弟表示法typedef struct CSNodeElemType data;struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;2、森林和二叉树的转换由于二叉树和树都可用二叉链表作为存储结构，以二叉链表

5、作为媒介可导出树与二叉树之间的一个对应关系。给定一棵树（森林），可以找到唯一的一棵二叉树与之对应，反之亦然。2、森林和二叉树的转换设森林* F= T1, T2, , Tn ;其中第一棵树T1由根结点 ROOT(T1)和子树森林 t11, t12, , t1m 构成。则可按如下规则转换成一棵二叉树B =( LBT, Node(root), RBT )：若森林 F 为空集，则二叉树 B 为空树；否则，由森林中第一棵树的根结点 ROOT(T1) 复制得二叉树的根 Node(root)，由森林中第一棵树的子树森林 t11, t12, , t1m转换得到二叉树中的左子树LBT，由森林中删去第一棵树之后由

6、其余树构成的森林 T2, , Tn 转换得到二叉树中的右子树RBT。2、森林和二叉树的转换反之，对于任意一棵二叉树B =( LBT, Node(root), RBT )，可按如下规则转换得到由 n 棵树构成的森林 F= T1, T2, , Tn ;其中第一棵树T1由根结点 ROOT(T1) 和子树森林 t11, t12, , t1m构成：若二叉树 B 为空树, 则与其对应的森林 F 为空集；否则，由二叉树的根结点 Node(root) 复制得森林中第一棵树的根结点 ROOT (T1)，由二叉树中的左子树 LBT 转换构造森林中第一棵树的子树森林t11, t12, , t1m ，由二叉树中的右子

7、树 RBT 转换构造森林中其余树构成的森林 T2, , Tn 。3、树和森林的遍历两个树的遍历方法：一、先根(次序)遍历树 若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；二、后根(次序)遍历树若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。3、树和森林的遍历森林是树的集合，由此可以对森林中的每一棵树依次从左到右进行先根遍历或者后根遍历。又森林中的（第一棵树的根）、（第一棵树的子树森林）及（其余树构成的森林），分别对应为（二叉树的根）、（二叉树的左子树）和（二叉树的右子树）。由此可如下定义森林的这两种遍历

8、。一、先序遍历森林 -若森林不空，则可依下列次序进行遍历(1) 访问森林中第一棵树的根结点；(2) 先序遍历第一棵树中的子树森林；(3) 先序遍历除去第一棵树之后剩余的树构成的森林。二、中序遍历森林 -若森林不空，则可依下列次序进行遍历：(1) 中序遍历第一棵树中的子树森林；(2) 访问森林中第一棵树的根结点；(3) 中序遍历除去第一棵树之后剩余的树构成的森林。3、树和森林的遍历容易看出，树的先根遍历即森林的先序遍历可对应到二叉树的先序遍历，树的后根遍历即森林的中序遍历可对应到二叉树的中序遍历。换句话说，若以孩子-兄弟链表作树（或森林）的存储结构，则树的先根遍历（或森林的先序遍历）的算法和二叉

9、树的先序遍历算法类似，而树的后根遍历（或森林的中序遍历）的算法和二叉树的中序遍历算法类似。6.5 树与等价问题离散数学中的概念：集合S上的关系R定义为SxS的一个子集。等价关系是具有自反、传递、对称的关系。若R是S上的等价关系，由R可以产生这个集合S的一个唯一的划分S1,S2,这些集合互不相交，其并为S，分别属于不同的等价类。6.5 树与等价问题确定等价类的问题假设集合S有n个元素，已知m个形如(x,y) (x,y S)的等价偶对确定了等价关系R，求S的划分。6.5 树与等价问题确定等价类的算法：令S中每个元素各自形成一个只含单个成员的子集，记作S1,S2,Sn重复读入m个关系（偶对），对每个

10、读入的偶对(x,y)，判定x和y所属的子集，若这两个子集不相等，则合并它们并取代这两个子集当所有的m个关系处理完后，剩下的这些非空子集即为S的R等价类。6.5 树与等价问题划分等价类需对集合进行的三个基本操作：构造只含一个元素的集合判定某个元素所在的子集合并两个互不相交的集合约定：利用树型结构表示集合，每个节点表示集合的元素根节点的成员兼作子集的名称6.5 树与等价问题集合的表示用树Ti表示每个子集Si，森林F表示集合S，每个节点代表每个元素，每棵树的根节点同时用来表示子集Si两种关键的基本操作：查找某个元素是否属于某个集合，合并两个集合。采用何种树、森林的存储方式可以有效地实现这些基本操作？

11、集合的并：将一子树的根指向另一子树的根即可是否属于集合：从该节点出发，逐级查找父节点到根节点为止。6.5 树与等价问题typedef PTree MFSet;int find_mfset( MFSet S, int i) /查找i所属子集if( iS.n) return -1;for( j=i; S.nodesj.parent0; j=S.nodesj.parent);return j;/ find_mfsetStatus merge_mfset( MFSet &s, int i, int j) /集合的并if( iS.n|jS.n) return ERROR;S.nodesi.parent=

12、j;return OK;/ merge_mfsetO( d) d树的深度O( 1)6.5 树与等价问题上述实现对于这样的例子：假设n个集合S1,S2,Sn, 每个子集只有一个元素Si=i，用n棵只有一个根节点的树表示，做n-1次并操作后，最后得到的集合的深度为n，加上每次进行查找成员“1”所在子集的操作，全部操作时间是O(n2)。123n12123123n6.5 树与等价问题Status mix_mfset( MFSet &S, int i, int j)if(iS.n|jS.n) return ERROR;if( S.nodesi.parentS.nodesj.parent)S.nodesj

13、.parent+=S.nodesi.parent;S.nodesi.parent=j;elseS.nodesi.parent+=S.nodesj.parent;S.nodesj.parent=i;return OK;/ mix_mfset改进“并”操作的算法，令成员少的子集树根节点指向成员多的子集的根；修改存储结构令根节点的parent与存储子集中所含成员数目的负值。深度不超过 log2n+1 6.5 树与等价问题一个实例假设集合S=x|1x n是正整数，R是S上的一个等价关系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求S的等价类12345678

14、n-1-1-1-1-1-1-1-1-112345678n-21-23-25-27-1处理(1,2),(3,4),(5,6),(7,8)之后6.5 树与等价问题一个实例假设集合S=x|1x n是正整数，R是S上的一个等价关系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求S的等价类12345678n-4113-4557-1处理(1,3),(5,7)之后12345678n-21-23-25-27-16.5 树与等价问题一个实例假设集合S=x|1x n是正整数，R是S上的一个等价关系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7

15、),(1,5),求S的等价类12345678n-81131557-1处理(1,5)之后12345678n-4113-4557-16.5 树与等价问题改进查找子集算法，增加“压缩路径”功能int fix_mfset( MFSet &S, int i)if(iS.n) return -1;for(j=i;S.nodesj.parent0;j=S.nodesj.parent);for(k=i;k!=j;k=t)t=S.nodesk.parent;S.nodesk.parent=j;return j;/ fix_mfset经过这些改进后，划分等价类的时间复杂度为O(n(n)，其中(n)46.6 赫夫曼

16、树及其应用Huffman（霍夫曼、哈夫曼）树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。最优二叉树Huffman编码1、最优二叉树概念结点的路径长度定义为从根结点到该结点的路径上分支的数目。树的路径长度定义为树中每个结点的路径长度之和。结点的带权路径长度定义为从树根到该结点之间的路径长度与该结点上所带权值的乘积。树的带权路径长度定义为树中所有叶子结点的带权路径长度之和* WPL(T)= wklk (对所有叶子结点)其中lk为带权wk的叶子结点的带权路径长度1、最优二叉树概念在所有含 n 个叶子结点、并带相同权值(n个确定的数)的 m 叉树中，必存在一棵其带权路径长度取最小值的树，

17、称为“最优树”。对于二叉树而言，称为最优二叉树。1、最优二叉树右图中的四棵二叉树，都有5个叶子结点且带相同权值2、5、6、7、9，它们的带权路径长度分别为：WPL=7*3+9*3+5*2+6*2+2*2=74 (左上图)WPL=2*1+6*3+7*4+9*4+5*2=94 (右上图)WPL=6*2+7*2+5*3+2*3+9*2=65 (左下图)WPL=2*1+5*3+7*3+9*3+6*3=83 (右下图)其中以左下图中二叉树的带权路径长度为最小。可以验证，它恰为最优二叉树，即在所有叶子结点带权为5、6、2、9、7的二叉树中，带权路径长度的最小值为65。1、最优二叉树一个应用例子：将成绩的百

18、分制(a: 0-100)转换为五级分制(b: ABCDE)。一般算法if( a60)b = E;else if( a70)b = D;else if( a80)b = C;else if( a90)b = B;elseb = A;60E70D80C90BA1、最优二叉树一个应用例子（续一）：如果成绩的分布是这样的：则平均需要的比较次数为：0.05*1+0.15*2+0.40*3+0.30*4+0.10*4= 3.15次分数0-5960-6970-7980-8990-100比例.05.15.40.30.101、最优二叉树一个应用例子（续二）：如果程序改一下：if( a80) if( a70)if

19、( a60) b = E;else b = D; else b = C;elseif( a90) b = B;else b = A;则平均需要的比较次数为：0.05*3+0.15*3+0.40*2+0.30*2+0.10*2= 2.2次分数0-5960-6970-7980-8990-100比例.05.15.40.30.1060EDC807090BA1、最优二叉树Huffman树的构造方法（最优二叉树）：根据给定的 n 个权值 w1, w2, , wn，构造 n 棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树;在 F 中选取

20、两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；在 F中删除这两棵树，同时将新得到的二叉树加入 F 中。重复(2)和(3)，直到 F 只含一棵树为止。这棵树便是所求的赫夫曼树。1、最优二叉树Huffman树的构造实例：权值2、5、6、7、9256725672567131、最优二叉树Huffman树的构造实例：权值2、5、6、7、92567132567131625671316292、Huffman编码表示一个消息文本，通常有两类二进制编码：一类为等长编码，这类编码的二进制串的长度取决于电文中不同的字符个数，假设需传送的电文中

21、只有四种字符，只需两位字符的串便可分辨，但如果电文中可能出现26种不同字符，则等长编码串的长度为5。另一类是不等长编码，即各个字符的编码长度不等。2、Huffman编码不等长编码的好处是，可以使传送电文的字符串的总长度尽可能地短。因为通常各个字符在电文中出现的次数是不相同的，若对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但在实用的不等长编码中，任意一个字符的编码都不能是另一个字符的编码的前缀，这种编码称为前缀编码。2、Huffman编码可以利用二叉树来设计二进制的前缀编码。假设有一棵如右图所示的二叉树，其四个叶子结点分别表示A、B、C和D四个字符，且约定左分支表示字符0，

22、右分支表示字符1，则以由从根到叶子的路径上的分支表示的字符组成的字符串作为该叶子结点字符的编码。如右图中A、B、C和D的二进制前缀编码分别为0、10、110和111。容易证明，如此得到的必为二进制前缀编码。并且，若以字符出现的次数为权，构造一棵赫夫曼树，由此得到的二进制前缀编码便为最优前缀编码(赫夫曼编码)。即以这组编码传送电文可使电文总长最短(对所有其它前缀编码而言)。A01B01DC01DAABABCBCA编码 0译码DAABABCBCA2、Huffman编码假设电文总只有5个字符，且在电文中出现的频率分别为：5/29，6/29，2/29，9/29，7/29。则所构造的最优前缀编码如右图所

23、示。于是对应的编码分别为：100, 00, 101, 11, 01The Huffman tree after two passesThe Huffman Algorithm exampleSymbolCountA15B7C6D6E5The final Huffman treeHuffman Code TableA0B100C101D110E111Total number of bits = 87基于Huffman编码的文件压缩一般的文件有一个个的字节组成，每个字节（8bit，最多有256种，称为原始符号）可以用Huffman编码表示（不等长），基于Huffman编码的文件压缩可以将每个原始符

24、号赋予不同的Huffman编码，将原始文件变换到一个新的文件，由于每个Huffman编码是一段（不等长的）01串，所以新的文件是由01组成的二进制序列，如果将它们8位一组构成字节重新写入一个文件，就得到所谓的压缩文件。还原（译码、解压缩）的过程正好相反基于Huffman编码的文件压缩基本的思路和考虑为了建立Huffman树、得到Huffman编码，首先需要有原始符号的权值，可以事先统计文件中各原始符号的频率作为权值。（权值越大，将会给与越短的编码）有了Huffman树，就可以得到编码表，即每个原始字符所对应的编码（01序列），压缩的过程就是一次读入文件中的每个字节，输出它对应的编码即可。解压缩

25、可以从Huffman树根开始，依次读入01序列，一直到叶节点为止，得到每个对应的原始符号。为了使解压缩程序得到相同的Huffman树，无需传递（在压缩文件中保留）整个Huffman树，只需传递各原始符号的频率（或者只是频数），然后采用与压缩算法同样的建树函数即可。基于Huffman编码的文件压缩Huffman树的建立节点表示：typedef struct tree_node unsigned int count; unsigned int saved_count; int child_0; int child_1; NODE;基于Huffman编码的文件压缩Huffman树的建立节点表示：ty

26、pedef struct tree_node unsigned int count;/ 权值 unsigned int saved_count;/ int child_0;/ 左子节点 int child_1;/ 右子节点 NODE;整个Huffman树可以存放在一个数组 nodes 中，其中前面部分分别代表各个原始符号（最终Huffman树的叶结点），在统计频率时建立（压缩）或从文件中读取（解压缩）。基于Huffman编码的文件压缩Huffman树的建立nodes 513 .count = 0 xffff;for ( next_free = END_OF_STREAM + 1 ; ; next_free+ ) 查找两个权重最小的自由节点（如果没有，结束） 将这两权重最小的自由节点合并得到一新的自由节点next_free-;nodes next_free .saved_count = nodes next_free .count;最后，next_free 为