第六章 树（算法设计） 

*6.22 【答案】二叉树的遍历算法可写为通用形式。例如通用的中序遍历为：
　void Inorder(BinTree,T,void(* visit)(DataType x)){
  　　if (T){
    　　Inorder(T->lchild,Visit);//遍历左子树
   　　 Visit(T->data);//通过函数指针调用它所指的函数来访问结点
  　　  Inorder(T->rchild,Visit);//遍历右子树
 　　 }
　}
　　其中Visit是一个函数指针，它指向形如void f(DataType x)的函数。因此我们可以将访问结点的操作写在函数f中通过调用语句Inorder(root,f)将f的地址传递给Visit,来执行遍历操作。请写一个打印结点数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。

6.23 【答案】以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。

6.24 【答案】以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。

6.25 【答案】以二叉链表为存储结构， 写一算法交换各结点的左右子树。

6.26 【答案】以二叉链表为存储结构，写一个拷贝二叉树的算法void CopyTree(BinTree root, BinTree *newroot),其中新树的结点是动态申请的，为什么newroot要说明为BinTree型指针的指针? 

6.27 【答案】以二叉链表为存储结构，分别写出在二叉树中查找值为x的结点及求x所在结点在树中层数的算法。

6.28 【答案】一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。

6.29 【答案】以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示：应使用队列来保存各层的结点。 

6.30 【答案】以二叉链表为存储结构，写一算法用括号形式(key LT,RT)打印二叉树，其中key是根结点数据，LT和RT是括号形式的左子树和右子树。并且要求空树不打印任何信息，一个结点x的树的打印形式是x而不是(x,)的形式。

6.31 【答案】以线索链表作为存储结构。分别写出在前序线索树中查找给定结点*p的前序后继，以及在后序线索树中查找 *p的后序前趋的算法。

6.32 【答案】完成6.6.1节算法CreatHuffmanTree中调用的三个函数：InitHuffmanTree,InputWeight 和SelectMin。

6.33 分别写出对文件进行哈夫曼编码的算法，以及对已编码文件进行解码的算法。为简单起见，可以假设文件是存放在一个字符向量中。
　答：
　　具体参见严蔚敏，吴伟民的《数据结构》第二版