文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
叉树只有根或树中任一结点均无右子树时，进行遍历才不用栈，其遍历程序段如下： 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 Ltag 0 Fch 2 Rtag 1 B 1 0 C 0 0 4 D 0 7 1 1 E 0 8 0 6 F 1 5 1 3 G 0 11 1 4 H 1 2 0 9 I 1 8 0 10 J 1 9 1 5 K 1 3 1 7 null 5 Nsib null 3 77. 1虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。本题中各字母编码如下：0Ac1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011 0101F78. 字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1B，B:000，C:01，D:001 nullnullc712536G010179．（2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229 c2EC1 c510011HJ01D(3) 编码为：015:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01 1c6011 00 c4(4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。36 145c316 77题中序线索树 1由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的9 I170 c80c111 0“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。 1514 77“虚权值”题哈码树5 9夫曼编80．首先确定是否需加（即权值为0）,对m个权值，建k叉树，若（m-1）%(k-1)=0,010 1 则不需要加“虚权值”，否则，第一次归并时需（m-1）%(k-1)+1个权值归并。建立k叉树 63 1 的过程如下： 10（1）将m个权值看作m棵只有根结点的k叉树的集合F={T1，T2，…，Tm} 。 78题哈夫曼编码树 23（2）从F中选k（若需加虚权值，则第一次选（m-1）%(k-1)+1）个权值最小的树作子树， 构成一棵k叉树，k叉树根结点的权值为所选的k个树根结点权值之和，在F中 385删除这k棵子树，并将新k叉树加入到F中。 79题（1）（3）从F中选k个权值最小的树作子树，构成一棵k叉树，其根 10091结点权值等于所选的k棵树根结点权值之和，在F中删除这k棵树， 并将新得到的树加到F中。 25493036(4) 重复（3），直到F中只有一棵树为止，这就是最优的k叉树。 对本题10个权值，构造最优三叉树。 5169因（10-1）%(3-1)=1， 所以第一次用2个权值合并。 14最小加权路径长度： 11文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
1946481文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
（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 82．前缀码是一编码不是任何其它编码B 12 0 0 0 0 0 2 12 前缀的编码。例如，0和01就不是前缀C 7 0 0 0 0 0 3 10 码，因为编码0是编码01的前缀。仅从D 4 0 0 0 0 0 4 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 码。 0 0 5 0 1 8 5 9 利用二叉树可以构造前缀码，例如， 0 0 4 0 8 9 9 11 以A，B，C，D为叶子可构成二叉树，将
10 0 0 3 0 6 15 12 左分枝解释为0，右分枝解释成1，从根
11 0 0 9 0 7 20 13 结点到叶子结点的0、1串就是叶子的前
12 0 0 2 0 10 12 27 13 缀码。用哈夫曼树可构造出最优二叉树，
13 0 0 11 0 12 13 47 0 使编码长度最短。
83．哈夫曼树只有度为0的叶子结点和度为2的分枝结点，设数量分别为n0和n2，则树的结点数n为n=n0+n2。 另根据二叉树性质：任意二叉树中度为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); }
12文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
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’; //给后缀表达式加上结束标记
13文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
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[])
//L[]和R[]是含有N个元素且指示二叉树结点i左儿子和右儿子的一维数组，
//本算法据此建立结点i的双亲数组T，并判断结点U是否是结点V的后代。 {for(i=1;i<=N;i++) T[i]=0; //T数组初始化
for (i=1;i<=N;i++) //根据L和R填写T
if(L[i]!=0) T[L[i]]=i; //若结点i的左子女是L，则结点L的双亲是结点i for(i=1;i<=N;i++)
if (R[i]!=0) T[R[i]]=i; //i的右子女是r，则r的双亲是i int parent=U; //判断U是否是V的后代 while (parent!=V && parent!=0) parent=T[parent];
14文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
if (parent==V){printf(“结点U是结点V的后代”);return(1);} else{ printf(“结点U不是结点V 的后代”);return(0);} }结束Generation
6．[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。
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
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
[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。 7．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。
15文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.