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<t>"root ∥ Huffman树的根结点 void Merge Tree( Huffman Tree Node<t> &htl, Huffman Tree Node<t> &ht2, Huffman Tree Node<t> ∥把以htl和ht2为根的两棵 Huffman树合并成一棵以 parent为根的二叉树 void Delete Tree(Huffman TreeNode<t> *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 T> class HuffmanTree { private: HuffmanTreeNode<T> *root; // Huffman 树的根结点 void MergeTree ( HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T> *parent); // 把以 ht1 和 ht2 为根的两棵 Huffman 树合并成一棵以 parent 为根的二叉树 void DeleteTree(HuffmanTreeNode<T> *root); // 删除 Huffman 树或其子树 public: