数据结构与算法“二叉树”教学设计 北京大学信息科学技术学院王腾蛟 1、二叉树在课程中的定位和前测知识点 二叉树是非常重要的树形数据结构。很多从实际问题中抽象出来的数据是二叉树形 的;而且许多算法如果采用二叉树形式解决则非常方便、高效。此外,以后将看到一般 树或森林都可通过简单的转换,得到与之相对应的二叉树,从而为一般树和森林的存储 和处理提供了有效方法 二叉树一章主要介绍了二叉树的周游,包括前序法、中序法、后序法,希望学生能 够掌握二叉树的周游算法及从二叉树周游结果得到二叉树的方法,并能根据要求,编写 合适的递归算法。 前测知识点要求如下,可以根据需要给学生补充 (1)线性表的实现和优缺点。 (2)栈与递归。 (3)队列的实现和比较 2、学习目标 (1)理解二叉树的主要概念与相关性质 (2)掌握二叉树的抽象数据类型、存储表示与实现效率 (3)熟练掌握二叉树的周游策略 (4)掌握二叉搜索树及其应用。 (5)理解堆的概念、性质,重点掌握堆的构造。 (6)理解 Huffman树的主要思想与具体应用。 3、知识点和学时分配 理论授课6学时,建议安排实验12学时。 各知识点建议授课时间如下 二叉树的基本概念 0.5小时 二叉树的抽象数据类型15小时 二叉树的存储结构 0.5小时
1 数据结构与算法“二叉树”教学设计 北京大学信息科学技术学院 王腾蛟 1、二叉树在课程中的定位和前测知识点 二叉树是非常重要的树形数据结构。很多从实际问题中抽象出来的数据是二叉树形 的；而且许多算法如果采用二叉树形式解决则非常方便、高效。此外，以后将看到一般 树或森林都可通过简单的转换，得到与之相对应的二叉树，从而为一般树和森林的存储 和处理提供了有效方法。 二叉树一章主要介绍了二叉树的周游，包括前序法、中序法、后序法，希望学生能 够掌握二叉树的周游算法及从二叉树周游结果得到二叉树的方法，并能根据要求，编写 合适的递归算法。 前测知识点要求如下，可以根据需要给学生补充 （1） 线性表的实现和优缺点。 （2） 栈与递归。 （3） 队列的实现和比较。 2、学习目标 （1） 理解二叉树的主要概念与相关性质。 （2） 掌握二叉树的抽象数据类型、存储表示与实现效率。 （3） 熟练掌握二叉树的周游策略。 （4） 掌握二叉搜索树及其应用。 （5） 理解堆的概念、性质，重点掌握堆的构造。 （6） 理解 Huffman 树的主要思想与具体应用。 3、知识点和学时分配 理论授课 6 学时，建议安排实验 12 学时。 各知识点建议授课时间如下： 二叉树的基本概念 0.5 小时 二叉树的抽象数据类型 1.5 小时 二叉树的存储结构 0.5 小时
叉搜索树 1小时 堆与优先队列 0.5小时 Huffman树及其应用 1小时 排序算法的时间代价 0.5小时 叉树知识点总结 0.5小时 4、重点难点 (1)二叉树的各种存储方法及效率分析。 (2)二叉树的周游策略。 (3)堆的建立与 Huffman编码树的基本思想。 (4)二叉树的非递归周游算法 5、授课提示 采用灵活的教学方式,通过提出问题、分析问题、解决问题这样的基本流程,加深学生 对重难点知识的理解,并培养其创新意识和创新能力 下面是二叉树的重点和难点内容的讲授注意事项 (1)二叉树的性质 性质7.对于具有n个结点的完全二叉树,结点按层次由左到右编号,则对任一 结点i(0≤i≤n-1)有 (1)如果i=0,则结点i是二叉树的根结点;若1>0,则其父结点编号是(i-1)2」。 (2)当2i+1≤n-1时,结点i的左子结点是2i+1,否则结点i没有左子结点。 当2i+2≤n-1时,结点i的右子结点是2i+2,否则结点i没有右子结点。 (3)当i为偶数且0<i<n时,结点i的左兄弟是结点i-1,否则结点i没有左兄弟。 当i为奇数且计1<n时,结点i的右兄弟是结点i+1,否则结点i没有右兄弟。 这个性质的证明,只需证明(2),(1)和(3)即可由结论(2推得。 (2)二叉树的前序、中序、后序周游的递归算法和使用栈的非递归算法 基于二叉树的递归定义,这三种深度优先周游的递归定义是 (1)前序法其递归定义是:访问根结点;按前序周游左子树:按前序周游右子树 (2)中序法其递归定义是:按中序周游左子树;访问根结点;按中序周游右子树 (3)后序法其递归定义是:按后序周游左子树;按后序周游右子树;访问根结点
2 二叉搜索树 1 小时 堆与优先队列 0.5 小时 Huffman 树及其应用 1 小时 排序算法的时间代价 0.5 小时 二叉树知识点总结 0.5 小时 4、重点难点 （1） 二叉树的各种存储方法及效率分析。 （2） 二叉树的周游策略。 （3） 堆的建立与 Huffman 编码树的基本思想。 （4） 二叉树的非递归周游算法。 5、授课提示 采用灵活的教学方式，通过提出问题、分析问题、解决问题这样的基本流程，加深学生 对重难点知识的理解，并培养其创新意识和创新能力。 下面是二叉树的重点和难点内容的讲授注意事项 （1）二叉树的性质 性质 7. 对于具有 n 个结点的完全二叉树，结点按层次由左到右编号，则对任一 结点 i（0 ≤ i ≤ n - 1）有 （1）如果 i = 0，则结点 i 是二叉树的根结点；若 i＞0，则其父结点编号是(i - 1)/2。 （2）当 2i + 1 ≤ n - 1 时，结点 i 的左子结点是 2i + 1，否则结点 i 没有左子结点。 当 2i + 2 ≤ n - 1 时，结点 i 的右子结点是 2i + 2，否则结点 i 没有右子结点。 （3）当 i 为偶数且 0 < i < n 时，结点 i 的左兄弟是结点 i - 1，否则结点 i 没有左兄弟。 当 i 为奇数且 i+1 < n 时，结点 i 的右兄弟是结点 i + 1，否则结点 i 没有右兄弟。 这个性质的证明，只需证明(2)，(1) 和(3)即可由结论(2)推得。 （2）二叉树的前序、中序、后序周游的递归算法和使用栈的非递归算法 基于二叉树的递归定义，这三种深度优先周游的递归定义是： (1) 前序法其递归定义是：访问根结点；按前序周游左子树；按前序周游右子树。 (2) 中序法其递归定义是：按中序周游左子树；访问根结点；按中序周游右子树。 (3) 后序法其递归定义是：按后序周游左子树；按后序周游右子树；访问根结点
这三种周游算法都是递归算法。递归算法虽然简洁,但是有时程序设计不允许用递 归,这时就存在如何把递归程序转化成等价的非递归算法的问题。解决这个问题的关键 是设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理,可以写出非递归周游 叉树的算法。 (3)二叉树的广度优先周游算法 对二叉树进行广度优先(层次)周游的过程是:首先访问第0层,也就是根结点所在 的层,然后从左到右依次访问第一层两个结点,以此类推,当第i层的所有结点访问完 之后,再从左至右依次访问第计1层的各个结点。 根据层次周游二叉树的性质,这里需要使用一个队列作为辅助的存储结构。层次周 游过程的实现就是从根结点开始逐层逐个地访问各个结点。在周游开始的时候,首先将 根结点放入队列:然后每次从队列中取出队头元素处理,每处理一个结点时,按从左至 右的顺序把它的所有子结点放入队列。这样,上层结点总是排在下一层结点的前面,从 而实现了二叉树的广度优先周游。 (4)二叉树的链式存储结构 所谓链式存储方式,是指二叉树的各结点随机的存储在内存空间中,结点之间的关 系用指针表示。 在用链接方式存储二又树时,对于每一个结点,除了存储结点本身的信息外,还要 设置两个指向左右孩子的指针。即表示二叉树的链表的结点包含三个域:数据域和左 右指针域。用info域存储结点的数据元素,另外再设置两个指针域lett和 right,分别 指向结点的左子结点和右子结点。当结点的某个子结点为空时,相应的指针为空指针。 有时候为了便于查找二叉树中某个结点的父结点,还可以在结点结构中加入一个指向其 父结点的指针域。这方面的内容,需要用图片进行形象的展示。 (5)二叉树的顺序存储结构 叉树的顺序存储是指按照一定次序,用一组地址连续的存储单元存储二叉树上的 各个结点元素 由于二叉树是一种非线性结构,因此必须将二叉树的结点排成一个线性序列,使得 通过结点在这个序列中的相对位置就能够确定结点之间的逻辑关系。通常情况下,只通 过相应位置不足以刻化整个树形结构。而对于一棵具有n个结点的完全二叉树,可以从 根结点起自上而下,从左至右地把所有的结点编号,得到一个足以反映整个二叉树结构 的线性序列。采用这种方式,线性序列里存储的结点就是按照层次周游二叉树得到的排
3 这三种周游算法都是递归算法。递归算法虽然简洁，但是有时程序设计不允许用递 归，这时就存在如何把递归程序转化成等价的非递归算法的问题。解决这个问题的关键 是设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理，可以写出非递归周游 二叉树的算法。 （3）二叉树的广度优先周游算法 对二叉树进行广度优先(层次)周游的过程是：首先访问第 0 层，也就是根结点所在 的层，然后从左到右依次访问第一层两个结点，以此类推，当第 i 层的所有结点访问完 之后，再从左至右依次访问第 i+1 层的各个结点。 根据层次周游二叉树的性质，这里需要使用一个队列作为辅助的存储结构。层次周 游过程的实现就是从根结点开始逐层逐个地访问各个结点。在周游开始的时候，首先将 根结点放入队列；然后每次从队列中取出队头元素处理，每处理一个结点时，按从左至 右的顺序把它的所有子结点放入队列。这样，上层结点总是排在下一层结点的前面，从 而实现了二叉树的广度优先周游。 （4）二叉树的链式存储结构 所谓链式存储方式，是指二叉树的各结点随机的存储在内存空间中，结点之间的关 系用指针表示。 在用链接方式存储二叉树时，对于每一个结点，除了存储结点本身的信息外，还要 设置两个指向左右孩子的指针。即表示二叉树的链表的结点包含三个域：数据域和左、 右指针域。用 info 域存储结点的数据元素，另外再设置两个指针域 left 和 right，分别 指向结点的左子结点和右子结点。当结点的某个子结点为空时，相应的指针为空指针。 有时候为了便于查找二叉树中某个结点的父结点，还可以在结点结构中加入一个指向其 父结点的指针域。这方面的内容，需要用图片进行形象的展示。 （5）二叉树的顺序存储结构 二叉树的顺序存储是指按照一定次序，用一组地址连续的存储单元存储二叉树上的 各个结点元素。 由于二叉树是一种非线性结构，因此必须将二叉树的结点排成一个线性序列，使得 通过结点在这个序列中的相对位置就能够确定结点之间的逻辑关系。通常情况下，只通 过相应位置不足以刻化整个树形结构。而对于一棵具有 n 个结点的完全二叉树，可以从 根结点起自上而下，从左至右地把所有的结点编号，得到一个足以反映整个二叉树结构 的线性序列。采用这种方式，线性序列里存储的结点就是按照层次周游二叉树得到的排
列。这方面的内容,需要用图片进行形象的展示。 (6)二叉搜索树 叉搜索树是一类满足以下属性的特殊二叉树:二叉搜索树中的每个非空结点表示 一个记录:某结点左子树不空,则左子树上所有结点的值均小于该结点的关键码值;若 其右子树不为空,则右子树上所有结点的值均大于该结点的关键码值。二叉搜索树可以 是一棵空树,任何结点的左右子树都是二叉搜索树。按照中序周游整个二叉树得到一个 由小到大有序排列。 叉搜索树的检索过程:将给定值key与根结点的关键码比较,如果key小于根结 点的值,则只需要检索左子树;如果key大于根结点的值,就只检索右子树。这个过程 一直持续到key被匹配成功或者遇到叶结点为止。如果遇到叶结点仍没有发现key,那 么key就不在这棵二叉搜索树中。 二叉搜索树插入操作:将待插入结点的关键码与根结点的关键码相比较,若待插入 的关键码小于根结点的关键码,则进入左子树,否则进入右子树。按照同样的方式沿检 索路径直到叶结点,确定插入位置,把待插入结点作为一个新叶结点插入到二叉搜索树 中 改进的二叉搜索树结点删除算法的思想为:若结点 pointer没有左子树,则用 pointer 右子树的根代替被删除的结点 pointer;若结点 pointer有左子树,则在左子树里找到按 中序周游的最后一个结点 temppointer(即左子树中的最大结点)并将其从二叉搜索树 里删除,由于 temppointer没有右子树,删除该结点只需用 temppointer的左子树代替 temppointer,然后用 temppointer结点代替待删除的结点 pointer. (7)霍夫曼树的构造方法 霍夫曼树的构造过程是 (1)对于给定的n个权值wo,w,…,wn-(n≥2),构成n棵二叉树的集合T={To Tn-},使得每一棵扩充二叉树只具有一个带权为w;的根结点。 (2)构造一棵新的扩充二叉树,在集合T中找出两个权值最小的树作为新树根结点 的左右子树,把新树根结点的权值赋为其左右子树根结点的和。 (3)在集合T中删除这两棵树,并把得到的新扩充二叉树加入到集合中 (4)重复步骤(2)、(3)的操作,直到集合T中只含有一棵树为止。 对于构造过程的讲解,最好是通过自定义动画进行逐步展示,这样更形象一些。从 Huffman树的构建过程也可以看出,结点的权值越大,那么它到根结点的路径就越短; 权值越小,结点就会放到离根结点较远的位置上
4 列。这方面的内容，需要用图片进行形象的展示。 （6）二叉搜索树 二叉搜索树是一类满足以下属性的特殊二叉树：二叉搜索树中的每个非空结点表示 一个记录；某结点左子树不空，则左子树上所有结点的值均小于该结点的关键码值；若 其右子树不为空，则右子树上所有结点的值均大于该结点的关键码值。二叉搜索树可以 是一棵空树，任何结点的左右子树都是二叉搜索树。按照中序周游整个二叉树得到一个 由小到大有序排列。 二叉搜索树的检索过程：将给定值 key 与根结点的关键码比较，如果 key 小于根结 点的值，则只需要检索左子树；如果 key 大于根结点的值，就只检索右子树。这个过程 一直持续到 key 被匹配成功或者遇到叶结点为止。如果遇到叶结点仍没有发现 key，那 么 key 就不在这棵二叉搜索树中。 二叉搜索树插入操作：将待插入结点的关键码与根结点的关键码相比较，若待插入 的关键码小于根结点的关键码，则进入左子树，否则进入右子树。按照同样的方式沿检 索路径直到叶结点，确定插入位置，把待插入结点作为一个新叶结点插入到二叉搜索树 中。 改进的二叉搜索树结点删除算法的思想为：若结点 pointer 没有左子树，则用 pointer 右子树的根代替被删除的结点 pointer；若结点 pointer 有左子树，则在左子树里找到按 中序周游的最后一个结点 temppointer（即左子树中的最大结点）并将其从二叉搜索树 里删除，由于 temppointer 没有右子树，删除该结点只需用 temppointer 的左子树代替 temppointer，然后用 temppointer 结点代替待删除的结点 pointer。 （7）霍夫曼树的构造方法 霍夫曼树的构造过程是： (1) 对于给定的 n 个权值 w0，w1，„，wn－1(n≥2)，构成 n 棵二叉树的集合 T = { T0， T1，T2，„，Tn－1}，使得每一棵扩充二叉树只具有一个带权为 wi的根结点。 (2) 构造一棵新的扩充二叉树，在集合 T 中找出两个权值最小的树作为新树根结点 的左右子树，把新树根结点的权值赋为其左右子树根结点的和。 (3) 在集合 T 中删除这两棵树，并把得到的新扩充二叉树加入到集合中。 (4) 重复步骤(2)、(3)的操作，直到集合 T 中只含有一棵树为止。 对于构造过程的讲解，最好是通过自定义动画进行逐步展示，这样更形象一些。从 Huffman 树的构建过程也可以看出，结点的权值越大，那么它到根结点的路径就越短； 权值越小，结点就会放到离根结点较远的位置上
6、课后练习和实习 将书本上的理论知识与最前沿的技术知识融为一体,设计验证型、探索型、应用型的 实习题和上机题,帮助同学更好的理解书本上的基本原理,锻炼学生的思维能力、实践能力。 叉树这章可以安排7-10道书面作业,3-4道综合上机实习题。安排一到两次习题讲评 例如:对递归函数方面的考察 (1)编写一个递归函数 search,传入参数为一棵二叉树(不是二叉搜索树BST) 一个值K,如果值K出现在树中则返回tue,否则返回 false相应地,请写出一个 等价的非递归函数 (2)编写一个递归函数 smallcount,传入一棵二叉搜索树BST的根和值K,返 回值小于或等于K的结点数目。函数 smallcount应尽可能少地访问BST的结点。相应 地,请写出一个等价的非递归函数 smallcount (3)编写一个递归函数 printRange,传入一个BST,一个较小的值和一个较大的 值,按照顺序打印出介于两个值之间的所有结点。函数 print Range应尽可能少地访问 BST的结点。 7、教学案例 霍夫曼树的构造方法。 描述如下 (1)对于给定的n个权值w,w,…,wn-n≥2),构成n棵二叉树的集合T={To T1,T2,…,Tn-},使得每一棵扩充二叉树只具有一个带权为w的根结点。 (2)构造一棵新的扩充二叉树,在集合T中找出两个权值最小的树作为新树根结点的左 右子树,把新树根结点的权值赋为其左右子树根结点的和 (3)在集合T中删除这两棵树,并把得到的新扩充二叉树加入到集合中。 (4)重复步骤(2)、(3)的操作,直到集合T中只含有一棵树为止。 算法代码如下: class HuffmanTree i Huffman Node"root ∥ Huffman树的根结点 void Merge Tree( Huffman Tree Node &htl, Huffman Tree Node &ht2, Huffman Tree Node ∥把以htl和ht2为根的两棵 Huffman树合并成一棵以 parent为根的二叉树 void Delete Tree(Huffman TreeNode *root); ∥删除 Huffman树或其子树
5 6、课后练习和实习 将书本上的理论知识与最前沿的技术知识融为一体，设计验证型、探索型、应用型的 实习题和上机题，帮助同学更好的理解书本上的基本原理，锻炼学生的思维能力、实践能力。 二叉树这章可以安排 7-10 道书面作业，3-4 道综合上机实习题。安排一到两次习题讲评。 例如：对递归函数方面的考察 （1） 编写一个递归函数 search，传入参数为一棵二叉树（不是二叉搜索树 BST） 和一个值 K，如果值 K 出现在树中则返回 true，否则返回 false。 相应地，请写出一个 等价的非递归函数 search。 （2） 编写一个递归函数 smallcount，传入一棵二叉搜索树 BST 的根和值 K，返 回值小于或等于 K 的结点数目。函数 smallcount 应尽可能少地访问 BST 的结点。相应 地，请写出一个等价的非递归函数 smallcount。 （3） 编写一个递归函数 printRange，传入一个 BST，一个较小的值和一个较大的 值，按照顺序打印出介于两个值之间的所有结点。函数 printRange 应尽可能少地访问 BST 的结点。 7、教学案例 霍夫曼树的构造方法。 描述如下： (1) 对于给定的 n 个权值 w0，w1，„，wn－1(n≥2)，构成 n 棵二叉树的集合 T = { T0， T1，T2，„，Tn－1}，使得每一棵扩充二叉树只具有一个带权为 wi的根结点。 (2) 构造一棵新的扩充二叉树，在集合 T 中找出两个权值最小的树作为新树根结点的左 右子树，把新树根结点的权值赋为其左右子树根结点的和。 (3) 在集合 T 中删除这两棵树，并把得到的新扩充二叉树加入到集合中。 (4) 重复步骤(2)、(3)的操作，直到集合 T 中只含有一棵树为止。 算法代码如下： template class HuffmanTree { private: HuffmanTreeNode *root; // Huffman 树的根结点 void MergeTree ( HuffmanTreeNode &ht1, HuffmanTreeNode &ht2, HuffmanTreeNode *parent); // 把以 ht1 和 ht2 为根的两棵 Huffman 树合并成一棵以 parent 为根的二叉树 void DeleteTree(HuffmanTreeNode *root); // 删除 Huffman 树或其子树 public:
Huffman Tree(T weight[, int n),∥构造 Huffman树,参数 weight为权值数组,n为数组长度 virtual -Huffman TreeO! Delete Tree(root); ∥析构函数 Huffman Tree HuffmanTree(T weight, int n)i MinHeap> heap(n) ∥最小值堆 Huffman TreeNode*parent, firstchild, secondchild; Huffman TreeNode *Node list= new Huffman TreeNodeIn] (int 1=0, i<n; i++)i ∥初始化 NodeList. info= weight NodeList]- parent=Nodelist.left=NodeList]. right= NULL; heap. Insert(NodeList); ∥向堆中添加元素 (=0;i<n-1;i+){ ∥通过n-1次合并建立 Huffman树 parent=new Huffman TreeNodes ∥申请一个分支结点 firstchild=heap. RemoveMin(; ∥选择权值最小的结点 ∥选择权值次小的结点 Merge Tree(firstchild, secondchild, parent); ∥将权值最小的两棵树合并到 parent树 插入到堆中去 root- parent; ∥ Huffman树的根结点赋为 parent delete [NodeList; 讲解算法时,注意展示自定义动画,有利于更形象的表述。 ⑥②③④ (b) 图519 Huffman树的构造过程 代码给出了 Huffman树的类定义,构造函数实现了 Huffman树的构造。其中类
6 HuffmanTree(T weight[],int n); // 构造 Huffman 树，参数 weight 为权值数组，n 为数组长度 virtual ~HuffmanTree(){DeleteTree(root);}; // 析构函数 }; template HuffmanTree::HuffmanTree(T weight[], int n) { MinHeap > heap(n); // 最小值堆 HuffmanTreeNode *parent, firstchild, secondchild; HuffmanTreeNode *NodeList = new HuffmanTreeNode[n]; for (int i = 0;i ; // 申请一个分支结点 firstchild = heap.RemoveMin(); // 选择权值最小的结点 secondchild = heap.RemoveMin(); // 选择权值次小的结点 MergeTree(firstchild,secondchild,parent); // 将权值最小的两棵树合并到 parent 树 heap.Insert(*parent); // 把 parent 插入到堆中去 root = parent; // Huffman 树的根结点赋为 parent } delete []NodeList; } 讲解算法时，注意展示自定义动画，有利于更形象的表述。 代码给出了 Huffman 树的类定义，构造函数实现了 Huffman 树的构造。其中类 图 5.19 Huffman 树的构造过程 6 2 3 4 5 2 3 (a) (b) 6 4 5 2 3 (c) 6 4 9 5 2 3 (d) 4 6 9 15
Huffman TreeNode继承自 Binary TreeNode类,只是增加了父指针成员变量。算法使用最小 堆选出权值最小的两个结点 8、总结 叉树是一种特殊的树形结构,在计算机领域里应用广泛。二叉树的周游算法,它 们与许多以此为基础的递归算法都必须认真学习。堆是一种二叉树的应用,可以用它作 为优先级队列的实现。它的存储表示是完全二叉树的顺序存储方式,它的定义不要求堆 中的数据有序,但要求双亲结点与子女结点必须满足某种关系。霍夫曼树是扩充二叉树, 要求在外结点上带有权值,在构造霍夫曼树时必须注意一个新结点的左子女上所带的权 值小于右子女上所带的权值,这不是霍夫曼树必须这样,而是实现算法造成这种结果 此外,作为霍夫曼树的应用,引入霍夫曼编码。通常让霍夫曼树的左分支代表编码“0”, 右分支代表编码“1”,得到霍夫曼编码。这是一种不等长编码,可以有效地实现数据压 缩 参考文献: 张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—一普 通高等教育“十一五”国家级规划教材。 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pku.educn/pkujpk/course/sjjg/ 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3。 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
7 HuffmanTreeNode 继承自 BinaryTreeNode 类，只是增加了父指针成员变量。算法使用最小 堆选出权值最小的两个结点。 8、总结 二叉树是一种特殊的树形结构，在计算机领域里应用广泛。二叉树的周游算法，它 们与许多以此为基础的递归算法都必须认真学习。堆是一种二叉树的应用，可以用它作 为优先级队列的实现。它的存储表示是完全二叉树的顺序存储方式，它的定义不要求堆 中的数据有序，但要求双亲结点与子女结点必须满足某种关系。霍夫曼树是扩充二叉树， 要求在外结点上带有权值，在构造霍夫曼树时必须注意一个新结点的左子女上所带的权 值小于右子女上所带的权值，这不是霍夫曼树必须这样，而是实现算法造成这种结果。 此外，作为霍夫曼树的应用，引入霍夫曼编码。通常让霍夫曼树的左分支代表编码“0”， 右分支代表编码“1”，得到霍夫曼编码。这是一种不等长编码，可以有效地实现数据压 缩。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91
