67题(1)
68. （1）前序序列：ABDEHCFG
（2）中序序列：DHEBAFCG （3）后序序列：HEDBFGCA
69.（1）
（2）BiTree INORDER-PRIOR(N,X) //在中序线索二叉树上查找结点N的前驱结点X
{if(n->ltag==1){X=N->lchild; return (X);} else {p=N->lchild;
while (p->rtag==0) p=p->rchild; X=p;return(p);} }
70.
A F C
B H E D G
70题（3）
I 71.
71题（3） 72. 后序线索树中结点的后继，要么是其右线索（当结点的rtag=1时），要么是其双亲结点右子树中最左下的叶子结点。所以，只有当二叉树只有根或树中任一结点均无右子树时，进行遍历才不用栈，其遍历程序段如下：
while（p->ltag==0）p==p->lchild; //找最左下叶子结点 while（p->rchild!=null）{visit(p->data); //访问结点；
p=p->rchild;} //沿线索向上
对前序线索二叉树，当二叉树非空时，若其结点有左子女（ltag=0），左子女是后继；否则，若结点有右子女（rtag=0），则右子女是后继；若无右子女（rtag=1），右子女是线索，也指向后继。所以，对任何前序线索二叉树进行前序遍历均不需使用栈。
73．左右子树均不空的二叉树先序线索化后，空指针域为1个（最后访问结点的右链为空）。 74．if(p->ltag==0) return(p->lchild);//左子女不空，左子女为直接后继结点
else return(p->rchild); //左子女空，右子女（或右线索）为后继 75. 后序线索树中结点的后继（根结点无后继），要么是其右线索（当结点的rtag=1时），要么是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点，若其左标记等于1,则左子女为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。 76. 树的后根遍历（对应二叉树的中序遍历）全线索链表 Data A B C D E F G H I J K Ltag 0 1 0 0 0 1 0 1 1 1 1 Fch 2 null 5 7 8 5 11 2 8 9 3 Rtag 1 0 0 1 0 1 1 0 0 1 1 Nsib null 3 4 1 6 3 4 9 10 5 7
77.
虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。本题中各字母编码如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011
78. 字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001 前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ
71题（2）
79．（2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229
1 0
9 0 1
5 0 1
3 1
78题哈夫曼编码树
(3) 编码为：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01
(4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。 80．首先确定是否需加“虚权值”（即权值为0）,对m个权值，建k叉树，若（m-1）%(k-1)=0,则不需要加“虚权值”，否则，第一次归并时需（m-1）%(k-1)+1个权值归并。建立k叉树的过程如下： （1）将m个权值看作m棵只有根结点的k叉树的集合F={T1，T2，?，Tm}。
（2）从F中选k（若需加虚权值，则第一次选（m-1）%(k-1)+1）个权值最小的树作子树，构成一棵k叉树，k叉树根结点的权值为所选的k个树根结点权值之和，在F中 删除这k棵子树，并将新k叉树加入到F中。
（3）从F中选k个权值最小的树作子树，构成一棵k叉树，其根 结点权值等于所选的k棵树根结点权值之和，在F中删除这k棵树， 并将新得到的树加到F中。 (4) 重复（3），直到F中只有一棵树为止，这就是最优的k叉树。
对本题10个权值，构造最优三叉树。 因（10-1）%(3-1)=1，
所以第一次用2个权值合并。 最小加权路径长度：
（1+4）*4+(9+16)*3+(25+36+49+64+81)*2+100*1=705 字符 weight Parent rch parent lch lch rch
81．初态图 A 3 0 0 0 0 0 1 8 终态图 B 12 0 0 0 0 0 2 12 82．前缀码是一编码不是任何其它编码前缀的编码。例如，3 C 7 0 0 0 0 0 10 0和01就不是前缀码，因为编码0是编码01的前缀。仅4 D 4 0 0 0 0 0 9 从编码来看，0和01 是前缀码，但因历史的原因，它不被E 2 0 0 0 0 0 5 8 称为前缀码，而是把一编码不是另一编码前缀的编码称为F 8 0 0 0 0 0 6 10 前缀码。 G 11 0 0 0 0 0 7 11 利用二叉树可以构造前缀码，例如，以A，B，C，D为 0 0 5 0 1 8 5 9 叶子可构成二叉树，将左分枝解释为0，右分枝解释成1， 0 0 4 0 8 9 9 11 从根结点到叶子结点的0、1串就是叶子的前缀码。用哈夫
10 0 0 3 0 6 15 12 曼树可构造出最优二叉树，使编码长度最短。
11 0 0 9 0 7 20 13 83．哈夫曼树只有度为0的叶子结点和度为2的分枝结点，
12 0 0 2 0 10 12 27 13 设数量分别为n0和n2，则树的结点数n为n=n0+n2。 另
13 0 0 0 13 47 0 11 12 根据二叉树性质：任意二叉树中度为0的结点数n0和度为2的结点数n2间的关系是n2=n0-1,代入上式，则n=n0+n2=2n0-1。 84．（1）T树的最大深度Kmax=6（除根外，每层均是两个结点）
T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态）
（2）非叶子结点数是5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度wpl=51
85．（1）错误，循环结束条件top=0不能满足，因为在top>1情况下，执行top:=top-1
(2)错误 （3）错误 （4）正确 （5）结点的深度与其右孩子深度相同，比左孩子深度少1。
五．算法设计题
1．[题目分析]以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值，最后就可以根据根结点的运算符的要求，计算出表达式的最后结果。 typedef struct node
{ElemType data; float val;
char optr; //只取‘+’， ‘-’， ‘*’，‘/’ struct node *lchild，*rchild }BiNode,*BiTree;
float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值 {float lv,rv;
if(bt!=null)
{lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch(bt->optr)
{case ‘+’: value=lv+rv; break; case ‘-’: value=lv-rv;break; case ‘*’: value=lv*rv;break; case ‘/’: value=lv/rv; } } return(value); }
2.[题目分析] 本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。
int Precede(char optr1,optr2)
// 比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回-1 {switch(optr1)
{case‘+’:case‘-’:if(optr2==‘+’||optr2==‘-’)return(0);else return(-1); case‘*’:case‘/’:if(optr1==‘*’||optr2==‘/’)return(0);else return(1);
} }
void InorderExp (BiTree bt)
//输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名 {int bracket; if(bt)
{if(bt->lchild!=null)
{bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左子女运算符优先级
if(bracket==1) printf(‘(’)；
InorderExp(bt->lchild); //输出左子女表示的算术表达式 if(bracket==1)printf(‘)’)； //加上右括号 }
printf(bt->data); //输出根结点
if(bt->rchild!=null) //输出右子树表示的算术表达式 {bracket=Precede(bt->data,bt->rchild->data)
if (bracket==1)printf(“(”)； //右子女级别低，加括号 InorderExp (bt->rchild);
if(bracket==1)printf(“)”)； } }
}//结束Inorder Exp
3．[题目分析]首先通过对二叉树后序遍历形成后缀表达式，这可通过全局变量的字符数组存放后缀表达式；接着对后缀表达式求值，借助于一栈存放运算结果。从左到右扫描后缀表达式，遇操作数就压入栈中，遇运算符就从栈中弹出两个操作数，作运算符要求的运算，并把运算结果压入栈中，如此下去，直到后缀表达式结束，这时栈中只有一个数，这就是表达式的值。
char ar[maxsize];//maxsize是后缀表达式所能达到的最大长度 int i=1;
void PostOrder(BiTree t )//后序遍历二叉树t,以得到后缀表达式 {if(t)
{PostOrder(t->lchild); PostOrder(b->rchild)；ar[i++]=b->data; } }//结束PostOrder void EXPVALUE()
//对二叉树表示的算术表达式，进行后缀表达式的求值 {ar[i]=‘\\0’; //给后缀表达式加上结束标记 char value[]; //存放操作数及部分运算结果 i=1; ch=ar[i++]; while(ch!=‘\\0’)
{switch(ch)
{case ch in op: opnd1=pop(value);opnd2=pop(value); //处理运算符
push(operate(opnd2,ch,opnd1));break;
default: push(value,ch); //处理操作数，压入栈中 }
ch=ar[i++]; //读入后缀表达式
} printf(value[1]); //栈中只剩下一个操作数，即运算结束。 } //结束EXPVALUE
[算法讨论] 根据题意，操作数是单字母变量，存放运算结果的栈也用了字符数组。实际上，操作数既可能是变量，也可以是常量。运算中，两个操作数（opnd1 和opnd2）也不会直接运算，即两个操作数要从字符转换成数（如‘3’是字符，而数值3=‘3’-‘0’）。数在压入字符栈也必须转换，算法中的operate也是一个需要编写的函数，可参见上面算法设计题1，其细节不再深入讨论。
4．[题目分析]当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=null）,则它必是叶子，总的叶子结点个数是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶结点个数之和。
typedef struct node
{ElemType data;//数据域
struct node *fch, *nsib;//孩子与兄弟域 }*Tree; int Leaves (Tree t)
//计算以孩子-兄弟表示法存储的森林的叶子数 {if(t)
if(t->fch==null) //若结点无孩子，则该结点必是叶子
return(1+Leaves(t->nsib)); //返回叶子结点和其兄弟子树中的叶子结点数
else return (Leaves(t->fch)+Leaves(t->nsib)); //孩子子树和兄弟子树中叶子数之和 }//结束Leaves
5．[题目分析]由指示结点i 左儿子和右儿子的两个一维数组L[i]和R[i]，很容易建立指示结点i 的双亲的一维数组T[i]，根据T数组，判断结点U是否是结点V后代的算法，转为判断结点V是否是结点U的祖先的问题。
int Generation (int U,V,N,L[],R[],T[])