更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
24.树的存储结构：
1.双亲链表表示法：双亲链表表示法利用树中每个结点的双亲唯一性，在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parent，惟一地表示任何-棵树。 （1）双亲链表表示法的实现 方法① 用动态链表实现 方法② 用向量表示——更为方便
分析：E和F所在结点的双亲域是1，它们的双亲结点在向量中的位置是1，即B是它们的双亲。 注意：
① 根无双亲，其parent域为-1。
② 双亲链表表示法中指针parent向上链接，适合求指定结点的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能要遍历整个数组。
2.孩子链表表示法：孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。
注意：
① 孩子结点的数据域仅存放了它们在向量空间的序号。
② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。
③ 将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。
3.孩子兄弟链表表示法：在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
注意：
这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。
25. 树的遍历：
1．树T的前序遍历定义： ①访问根结点R； ②依次前序遍历根R的各子树T1，T2，…，Tk。 2．树的后序遍历定义： ①依次后序遍历根T的各子树Tl，T2，…，Tk； ②访问根结点R。
对下面的(a)图中的树进行前序遍历和后序遍历，得到的前序序列和后序序列分别是ABCDE和BDCEA。
① 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树 ② 后序遍历树恰好等价于中序遍历该树对应的二叉树。 26. 森林的两种遍历方法
1．前序遍历森林：①访问森林中第一棵树的根结点；②前序遍历第一棵树中根结点的各子树所构成的森林③前序遍历除第一棵树外其它树构成的森林。
2．后序遍历森林：①后序遍历森林中第一棵树的根结点的各子树所构成的森林；②访问第一棵树的根结点；③后序遍历除第一棵树外其它树构成的森林。
对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFIGJH和BDCAIFJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH和BDCAIFJGHE。
① 前序遍历森林等同于前序遍历该森林对应的二叉树 ② 后序遍历森林等同于中序遍历该森林对应的二叉树
27.树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
树的带权路径长度：定义为树中所有叶结点的带权路径长度之和，通常记为：
其中：n表示叶子结点的数目，wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。树的带权路径长度亦称为树的代价。
28．最优二叉树或哈夫曼树：在权为wl，w2，?，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。
给定4个叶子结点a,b,c,d,分别带权7,5,2,4。构造如下图所三棵二叉树(还有许多棵)，它们的带权路径长度分别为： (a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35
其中(c)树的WPL最小，可以验证，它就是哈夫曼树。
示的
① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 ② 最优二叉树中，权越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，WPL最小
29. 哈夫曼算法: 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。其基本思想是：
(1)根据给定的n个权值wl，w2，?，wn构成n棵二叉树的森林F={T1，T2，?，Tn}，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。
(2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值。
(3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。
注意：
① 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子
② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。 ③ 哈夫曼树是严格的二叉树，没有度数为1的分支结点。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
第一次：0，1->6；第二次：2,6->7；第三次：3,4->8；第四次：5,7->9；第五次：8,9->10。
（1） 哈夫曼树的存储结构
用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为： #define n 100 //叶子数目
#define m 2*n-1//树中结点总数 typedef struct { //结点类型
float weight； //权值，不妨设权值均大于零
int lchild，rchild，parent； //左右孩子及双亲指针 }HTNode；
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
注意：
因为C语言数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。
这里设置parent域有两个作用：其一是使查找某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。 哈夫曼算法的简要描述
在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)： (1)初始化 将T[0．．m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。 (2)输人
读人n个叶子的权值存于向量的前n个分量(即T[0．．n-1])中。它们是初始森林中n个孤立的根结点上的权值。
(3)合并
对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n≤i≤m-1)。每次合并分两步：
①在当前森林T[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。
② 将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。具体操作： 将T[p1]和T[p2]的parent置为i，
将T[i]的lchild和rchild分别置为p1和p2
新结点T[i]的权值置为T[p1]和T[p2]的权值之和。 注意：
合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。 30.哈夫曼编码：
数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进制位串。数据解压过程称为解码。即将二进制位串转换为对应的字符。
对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码，等长编码是前缀码。
平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩效果亦最佳。
利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。 1． 具体做法
（1）用字符ci作为叶子，pi或fi做为叶子ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；
（2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称哈夫曼编码）。
2． 由哈夫曼树求得编码为最优前缀码的原因：
① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li，平均码长(或文件总长)又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树，因此编码的平均码长(或文件总长)亦最小。
② 树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。 3． 求哈夫曼编码的算法 （1）思想方法
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子T[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。 第八章 排序
1. 所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。
被排序的对象--文件由一组记录组成。记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。排序运算的依据--关键字，在不易产生混淆时，将关键字项简称为关键字。
2. 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；
若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
自考数据结构重点（珍藏版）
