6.33设树形T在后根次序下的结点排列和各结点相应的度数如下： 后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次 数：００００３０００２０２４ 请画出Ｔ的树形结构图。
【解答】在树在后根遍历次序下，根结点在最后，任何结点的子树的所有结点都直接排在该结点之前。例如，挨着根结点的是根结点的最右边的子女。每棵子树的所有结点都聚集在一起，中间不会插入其它结点，也不会丢掉子树的任何结点。 按照这种理论解答本题，在遍历次序中从右到左分析，A是根，它有4个子女，H是它的最右边的子女（第4子女）。H有2个子女，L是H的最右边的子女，L无子女，故I是H的第1子女。I又有2个子女：K和J，二者均无子女。由此推断出下一个结点G是根结点A的第3子女。??，继续构造，直至最左面的结点B，结果树形如下：
6.34 若森林共有n个结点和b条边(b 森林的n个结点开始可看作是n个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b条边将减少b个连通分量，因而n个结点b条边的森林有n-b棵树。 6.35 求高度为k的完全二叉树至少有多少个叶结点？ 【解答】当高度为k的完全二叉树的第k层只有一个结点时，结点数达到最少，这也是高度为k的完全二叉树具有的最少叶结点数，我们知道，第k-1层有2k-2-1个叶结点，第k层只有一个叶结点，但这个结点的双亲已不再是叶子结点，故高度为k的完全二叉树至少有2k-2-1个叶结点。 6.36 某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16，5，9，3，20，1。试画出其哈夫曼树并确定其对应的哈夫曼编码。 【解答】答案不唯一，其中一个解答如下 对应的哈夫曼编码: A—10, B—1101, C—111, D—11001, E—0, F—11000 二、算法设计题 6.37以二叉链表作为存储结构，设计算法求出二叉树T中度为0、度为1和度为2的结点数。 【题目分析】结点计数可以在遍历中解决。根据“访问根结点”在“递归遍历左 子树”和“递归遍历右子树”中位置的不同，而有前序、后序和中序遍历。 【算法6.37】 int n2,n1,n0; ∥设置三个全局变量，分别记度为2，1和0的结点个数 void Count(BiTree t) {if(t) {if(t->lchild && t->rchild) n2++; else if(t->lchild && !t->rchild || !t->lchild && t->rchild) n1++; else n0++; if(t->lchild!=null) Count(t->lchild); if(t->rchild!=null) Count(t->rchild); }∥Count 6.38一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先序遍历。 【题目分析】二叉树的顺序存储是按完全二叉树的顺序存储，双亲与子女结点下标间有确定关系。顺序存储结构的二叉树用结点下标大于n（完全二叉树）或0（对一般二叉树的“虚结点”）判空。本题是完全二叉树。 【算法6.38】 void PreOrder(ElemType bt[],int n) ∥对以顺序结构存储的完全二叉树bt进行前序遍历 {int i=1,top=0,s[]; ∥top是栈s的栈顶指针，栈容量足够大 while(i<=n || top>0) {while(i<=n) {printf(bt[i]); ∥访问根结点； if(2*i+1<=n) s[++top]=2*i+1; ∥右子女的下标位置进栈 i=2*i; ∥沿左子女向下 } if(top>0) i=s[top--]; ∥取出栈顶元素 }∥while }∥结束PreOrder 6.39以二叉链表作为存储结构的二叉树，按后序遍历时输出的结点顺序为a1， a2，?，an。试编写一算法，要求输出后序序列的逆序an，an-1?，a2 ，a1 。 【题目分析】二叉树后序遍历是按“左子树－右子树－根结点”的顺序遍历二叉树，根据题意，若将遍历顺序改为“根结点－右子树－左子树”，就可以实现题目要求。 【算法6.39】 void PostOrder(BiTree bt) //对二叉树bt进行先右后左的“先根”遍历 {if(bt) {printf(bt->data); //访问根结点 PostOrder(bt->rchild); //先根遍历右子树 PostOrder(bt->lchild); //先根遍历左子树 } } 6.40以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。 【算法6.40】 void exchange(BiTree bt) ∥将二叉树bt所有结点的左右子树交换 {if(bt){BiTree s； s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; ∥左右子女交换 exchange(bt->lchild); ∥交换左子树上所有结点的左右子树 exchange(bt->rchild); ∥交换右子树上所有结点的左右子树 }∥if }∥结束 【算法讨论】将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历方式不适合本题。 6.41以二叉链表为存储结构，写出在二叉树中求值为x的结点在树中层次数的算法。 [题目分析] 按层次遍历，设一队列Q，用front和rear分别指向队头和队尾元素，last指向各层最右结点位置。 【算法6.41】 int Level_x(BiTree bt，ElemType x)∥求值为x的结点在树中层次数 {if(bt!=null) {int front=0,last=1,rear=1,level=1;∥level记层次数 BiTree Q[];Q[1]=bt;∥根结点入队 while(front<=last) {bt=Q[++front]; if(bt->data==x) {printf(“=\\n”,level); return level;}∥值为x的结点在树中层次数 if(bt->lchild!=null) Q[++rear]=bt->lchild;∥左子女入队列 if(bt->rchild!=null) Q[++rear]=bt->rchild;∥右子女入队列 if(front==last) {last=rear; level++; }∥本层最后一个结点已处理完 } } }∥算法结束 6.42已知深度为h的二叉树以一维数组作为存储结构。试编写算法求该二叉树中叶子的个数。 【题目分析】按完全二叉树形式顺序存储二叉树时，无元素的位置要当作“虚结点”。设虚结点取二叉树结点以外的值（这里设为0）。设结点序号为i,则当i<=(2h-1)/2时，若其2i和2i+1位置为虚结点，则i为叶子结点；当i>(2h-1)/2时，若i位置不是虚结点，则必为叶子结点。 【算法6.42】 int Leaves(int BT[],int n) ∥计算深度为h以一维数组BT作为存储结构的二叉树的叶子结点数，n为数组长度