后序线索树中结点的后继（根结点无后继），要么是其右线索（当结点的rtag=1时），要么是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点，若其左标记等于1,则左子女为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。
31．假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。 参考答案：
各字母编码如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011 注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。
32．设有正文AADBAACACCDACACAAD，字符集为{A,B,C,D}，试设计一套二进制编码，使得上述正文的编码最短。 参考答案：
字符A、B、C、D出现的次数分别为9、1、5、3，其哈夫曼编码如下A:1、B:000、C:01、D:001。
33．设T是一棵二叉树，除叶子结点外，其它结点的度皆为2，若T中有6个叶结点，试问：(1)树T的最大深度和最小可能深度分别是多少？(2)树T中共有多少非叶结点？(3)若叶结点的权值分别为1、2、3、4、5、6，请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 参考答案：
(1)最大深度6，最小深度4； (2)非叶结点数5；
(3)哈夫曼树见下图，其带权路径长度wpl=51。
34．一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，问：(1)第ｉ层上有多少个结点？(2)编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？(3)编号为ｐ的结点的双亲结点（若存在）的编号是多少？ 参考答案： (1)ki?1个
(2)（１＋（ｐ－１）＊ｋ）＋ｉ (3)??p?k?2?（ｐ≠１） 】 ?k??
三、算法设计题
1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。 参考答案：
以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值，最后就可以根据根结点的运算符的要求，计算出表达式的最后结果。 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, char 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．要求二叉树按二叉链表形式存储，(1)写一个建立二叉树的算法；(2)写一个判别给定的二叉树是否是完全二叉树的算法。 参考答案： (1)
BiTree Creat() //建立二叉树的二叉链表形式的存储结构
{ElemType x;BiTree bt;
scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0)
{bt=(BiNode *)malloc(sizeof(BiNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat(); }
else error(“输入错误”)； return(bt); }//结束 BiTree
(2)int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0
{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q))
{ p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0; //前边已有结点为空，本结点不空
else tag=1; } //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0;
else tag=1; } //while return 1;
} //JudgeComplete
4．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 参考答案：
方法一：BiTree Creat(ElemType A[],int i)
//n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树 {BiTree tree;
if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];
if(2*i>n) tree->lchild=null;else tree->lchild=Creat(A,2*i);
if(2*i+1>n) tree->rchild=null;else tree->rchild=Creat(A,2*i+1); }
return (tree); }//Creat 初始调用时i=1。
5．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注：树中结点数已知。 参考答案：
由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。
int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材 {int maxdepth=0; for(i=1;i<=t.n;i++) {temp=0; f=i;
while(f>0) {temp++; f=t.nodes[f].parent; } // 深度加1,并取新的双亲
if(temp>maxdepth) maxdepth=temp; //最大深度更新 }
return(maxdepth);//返回树的深度 } //结束Depth 6．二叉树采用二叉链表存储：(1)编写计算整个二叉树高度的算法；(2)编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 参考答案： (1)
int Height(BiTree bt)//求二叉树bt的深度 {
int hl,hr;
if (bt==null) return(0); else {
hl=Height(bt->lch); hr=Height(bt->rch); if(hl>hr) return (hl+1); else return(hr+1); } }
(2)求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。
int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else
{ BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大
front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)
{p=Q[front++]; temp++; //同层元素数加1
if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队
if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear;
if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度
temp=0;
}//if }//while
return (maxw); }//结束width
7．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。 参考答案：
二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。 void Ancestor(ElemType A[],int n,int i,int j)
//二叉树顺序存储在数组A[1..n]中，本算法求下标分别为i和j的结点的最近公共祖先结点的值。 {while(i!=j)
if(i>j) i=i/2; //下标为i的结点的双亲结点的下标 else j=j/2; //下标为j的结点的双亲结点的下标
printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,A[i]);//设元素类型整型。 }// Ancestor
8．在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度（若不加分析，直接写出结果，按零分算）。 参考答案：
后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。 void Search(BiTree bt,ElemType x) //在二叉树bt中，查找值为x的结点，并打印其所有祖先 {typedef struct
{BiTree t; int tag; }stack;//tag=0表示左子女被访问，tag=1表示右子女被访问 stack s[]; //栈容量足够大 top=0;
while(bt!=null||top>0)
{while(bt!=null && bt->data!=x) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt->data==x)
{ printf(“所查结点的所有祖先结点的值为:\\n”); //找到x for(i=1;i<=top;i++) printf(s[i].t->data);
return;
} //if输出祖先值后结束