数据结构第三章 树（三）本章节知识脉络：1．堆与优先队列；2．Human 树及其应用；3. 树与森林的转换；4. 数的周游；5. 森林的周游；6. 树的存储。重点和难点：1．重点：掌握树与二叉树的相互转换；掌握霍夫曼树的实现方法。2．难点：构造霍夫曼编码的方法及带权路径长度的计算，会用霍夫曼树进行编码和解码。一、 树1. 堆与优先队列 堆定义1）最小堆：最小堆是一个关键码序列{K0，K1，...Kn-1}。它具有如下特性：Ki≤K2i+1(i=0,1,...,n/2-1)；Ki≤K2i+22）堆的性质：① 从逻辑的角度来讲，堆是一种树形结构，而且是一种特殊的完全二叉树。此完全二叉树的每个结点对应于序列中的一个关键码，根结点对应于关键码 K0，按层次从左至右依次类推。② 堆的特殊主要是因为堆序只是局部有序，即最小堆对应的完全二叉树中所有内部结点的值均不大于其左右孩子的关键码值，而一个结点与其兄弟之间没有必然的联系。③ 最小堆不像二叉搜索树那样实现了关键码的完全排序。相比较而言，只有当结点之间是父子关系的时候，才可以确定这两个结点关键码的大小关系。3）堆的另一个定义： 最大树（最小树）是每个结点的值都大于（小于）或等于其子结点（如果有的话）值的树；最大堆（最小堆）是最大（最小）的完全二叉树。 堆的插入操作1）新元素添加到末尾（保持完全二叉树的性质）；2）为了保持堆的性质，沿着其祖先的路径，自下而上依次比较和交换该结点与父结点的位置，直到重新满足堆的性质位置；3）在插入过程中，总是自下而上逐渐上升，最后停留在某个满足堆的性质的位置，故此过程又称为“筛选”。 堆的初始化操作1）堆的建立：建堆过程，首先将所有关键码放到一维数组中，这时形成的完全二叉树并不具备堆的特性，但是仅包含叶子结点的子树已经是堆（即在有 n 个结点的完全二叉树中，当 i>[n/2]-1 时，以关键码 Ki 为根的子树已经是堆）。2）调整过程：这时从含有内部结点数最少的子树（这种子树在完全二叉树的倒数第二层，此时 i=[n/2]-1）开始，从右至左依次调整。对这一层调整完成之后，继续对上一层进行同样的工作，直到整个过程到达树根时 ，整棵完全二叉树就成为一个堆了。 堆的删除操作1）把最末端结点填入删除产生的空位（保持完全二叉树的性质）。2）为了保持堆的性质，沿着其后继结点的路径，自上而下依次比较和交换该结点与子结点的位置，直到重新满足堆的性质位置。3）堆排序① 按顺序构造完全二叉树；② 把完全二叉树改造成最小堆，从下向上，父子交换；③ 取得最小值； ④ 删除最小值，重新改造成新堆；⑤ 取次小元素；⑥ 删除次小元素，重新改造成新堆；⑦ 取次次小值，继续类似的操作，直到结束。4）建堆效率-建堆算法的时间复杂度是 O(n)。这就说明可以在线性时间内把一个无序的序列转化成堆序。-由于堆有 logn 层深，插入结点、删除普通元素和删除最小元素的平均时间代价和最差时间代价都是O(logn)。 优先队列1）优先队列（priority queue）是一种有用的数据结构。它是 0 个或多个元素的集合，每个元素都有一个关键码值，执行的操作有查找、插入和删除一个元素。2）优先队列的主要特点是支持从一个集合中快速地查找并移出具有最大值或最小值的元素。最小优先队列，适合查找和删除最小元素；最大优先队列，适合查找和删除最大元素。3）堆是一种很好的优先队列实现方法。 作业书面作业：·P142:13上机作业：·定义堆，封装初始化、插入、删除堆顶元素的操作。2. Human 树及其应用 Human 树1）要求给出一个具有 n 个外部结点的扩充二叉树 -每个外部结点 Ki 有一个 wi 与之对应，作为该外部结点的权 -叶结点带权外部路径长度最小 -权越大的叶结点离根越近；如果某个叶结点的权较小，可能就会离根较远。 2）Human 树定义：假设有 n 个权值{w0,w1,...wn-1}，试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 wi，则其中带权路径长度 WPL 最小的二叉树称作最优二叉树，Human 树是最优二叉树。3）构造 Human 树的算法步骤：① 根据给定的 n 个权值{w1,w2,...wn}构成 n 棵二叉树的集合 F={T1,T2,...Tn}，其中每棵二叉树 Ti中只有一个权值为 wi 的根结点。② 在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。③ 在 F 中删除这两棵树，同时将新得到的二叉树加入集合 F 中。④ 重复②和③，直到 F 中只含一棵树为止。 Human 编码1）什么是编码 为电文编码时，总是希望总长越短越好，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用较短的编码，则可以减短电文的总长。2）前缀编码：若设计长短不等的编码，满足任一个编码都不是另一个编码的前缀，则这样的编码称为前缀编码。利用二叉树设计二进制前缀编码，做分支表示“0”，有分支表示“1”；从根结点到叶子结点的路径上经过的二进制符号串作为该叶子结点字符的编码；路径长度为编码长度。3）Human 编码：设每种字符在电文中出现的概率为 wi，则依此 n 个字符出现的概率做权，可以设计一棵 Human 树，使得 最小，其中，wi 为叶子结点的出现概率（权），li 为根结点到叶子结点的路径长度。4）译码步骤：① 从根结点出发，从左至右扫描编码，② 若为“0”则走左分支，若为“1”则走右分支，直至叶结点为止，③ 取叶结点字符为译码结果，返回重复执行①、②和③，直至全部译完为止。 二、 树与森林1. 树转换为二叉树 树转换为二叉树的方法如下：1）在所有相邻兄弟结点之间加一条水平连线。2）对每个非叶结点 k，除了其最左边的孩子结点外，删去 k 与其他孩子结点的连线。3）整理由 1）、2）两步所得到的二叉树，使之结构层次分明。树做这样的转换所构成的二叉树是唯一的。2. 森林转换为二叉树 森林转换为二叉树的方法如下：1）将森林中的每棵树转换成相应的二叉树。2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。3. 二叉树还原为树或森林 二叉树还原为树或森林的具体方法：1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子......都与该结点的双亲结点用线连起来。2）删掉原二叉树中所有双亲结点与右孩子结点的连线。3）整理由 1）、2）两步所得到的树或森林，使之结构层次分明。4. 树的周游 深度优先周游1）先根次序 若树非空，则遍历方法为： ① 访问根结点。 ② 从左到右，依次先根遍历根结点的每一棵子树。 将树进行先根次序周游等同于转换的二叉树进行先序周游 2）后根次序 若树非空，则遍历方法为： ① 从左到右，依次后根遍历根结点的每一棵子树。 ② 访问根结点。 后根次序周游序列等同于转换的二叉树进行中序周游 广度优先周游1）宽度优先周游（层次周游） 从上到下，从左到右的周游5. 森林的周游 深度优先1）先根次序 若森林非空，则遍历方法为： ① 访问森林中第一棵树的根结点。 ② 先根次序周游第一棵树的根结点的子树森林。 ③ 先根次序周游其他的树。 对于森林的先根周游的序列等同于将它转换的二叉树进行先序周游2）后根次序 若森林非空，则遍历方法为： ① 后根次序周游森林中第一棵树的根结点的子树森林。 ② 访问第一棵树的根结点。 ③ 后根次序周游其他的树。 后根周游的序列等同于将其转换的二叉树进行中序遍历 广度优先1）宽度优先周游（层次周游） 对森林中进行从上到下从左到右的遍历 6. 树的存储 孩子表示法（孩子链表表示法） 每个结点包含两个域：一个数据域，一个指向孩子链表的指针域 孩子兄弟表示法（二叉树表示法）每个结点包含三个域：数据域，指向第一个孩子的指针域，指向它的下一个兄弟的指针域 该存储结构的操作方便，存储密度较高。 双亲表示法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置。这种存储结构利用了每个结点只有唯一双亲的性质，求结点的双亲方便，也容易求取树的根，但是在求某个结点的孩子结点时需要遍历整个存储空间。三、 本节例题1．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）答案：对2．在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（）答案：错四、 思考题1. 通 信 报 文 中 出 现 的 字 符 A 、 B 、 C 、 D 、 E ， 在 报 文 中 出 现 的 频 率 分 别 为0.23、0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。参考答案如下：为处理方便，关键字都乘以 100，为{23，20，32，12，13}。构造哈夫曼树为：所以编码为： A：01 B：00 C：11 D：100 E：101