北京大学：《数据结构与算法》课程教学资源（教学设计）二叉树（王腾蛟）.pdf_大学文库

这三种周游算法都是递归算法。递归算法虽然简洁,但是有时程序设计不允许用递归,这时就存在如何把递归程序转化成等价的非递归算法的问题。解决这个问题的关键是设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理,可以写出非递归周游叉树的算法。 (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 树的构建过程也可以看出，结点的权值越大，那么它到根结点的路径就越短；权值越小，结点就会放到离根结点较远的位置上

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: