华东理工815数据结构Chap4_树和二叉树精要.ppt

译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束 电文为“1101000”，则其译文只能是“CAT” C S 3 3 6 4 2 2 4 8 14 T ; A 0 0 1 1 0 1 1 0 T : 00 ; : 01 A : 10 C : 110 S : 111 译 码 堆 ( Heap ) 设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 0 开始连续编号。若满足 Ki ? K2i+1 Ki ? K2i+2 或 Ki ? K2i+1 Ki ? K2i+2, 则称该关键字集合构成一个堆。 前者称为最小堆（小根堆），后者称为最大堆（大根堆）。 例1： (96, 83, 27, 38, 11, 09) 例2： (13, 38, 27, 49, 76, 65, 49, 97) 96 27 09 11 38 83 13 27 38 49 65 76 49 97 由完全二叉树，则： k2i+1 是 ki 的左孩子； k2i+2 是 ki 的右孩子。 所有分支结点的值均不大（小）于其左右孩子结点的值。 堆顶元素必为序列中 n 个元素的最小值或最大值。 最小堆的定义 #define MaxHeapSize 100; typedef int DataType; typedef struct { //堆元素的定义 DataType key; //元素关键字 OtherData; //元素其他数据 } HeapElem; typedef struct { //最小堆定义 HeapElem data[MaxHeapSize]; //存放数组 int CSize; //最小堆当前元素个数 } MinHeap; 81 73 64 27 98 12 从无序序列的第 ?n/2? 个元素（即无序序列对应的完全二叉 树的最后一个内部结点）起，至第一个元素止，进行从上到下的反复筛选。 排序之前的关键字序列为：( 40, 55, 49, 73, 12, 27, 98, 81, 64, 36) 40 55 49 36 12 36 73 49 98 81 98 49 40 现在，左/右子树都已经调整为堆，最后只要调整根结点，使 整个二叉树是个“堆”即可。(对应P157程序代码） 81 73 55 堆的建立：将一组用数组存放的任意数据调整成堆 在堆中插入新元素 11 53 17 17 78 78 09 23 45 65 87 i 09 23 45 65 87 j 11 53 j 11 23 i 堆的插入和向上调整算法思想（对应P158程序算法 53 17 11 78 78 09 45 65 87 09 17 45 65 87 j 11 53 23 i 23 17 j i 　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种有哪些信誉好的足球投注网站策略进行的遍历。 　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 　　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　　6. 学会编写实现树的各种操作的算法。 　　7. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。 为方便起见，每个节点的数据元素用单个字母表示 * * * 实际应用中通常采用二叉链表 * * Start from here * 先复制左子树，再复制右子树，最后生成根节点 * * * B中序遍历下的前驱为空。 * 遍历到p时修改p的线索 * * （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。 4．二叉排序树的删除算法 可分三种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二