文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
p=p->rchild;//转向右子树 } }//结束InOrderThread
72.[题目分析]若使新插入的叶子结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左面的结点（设为p）处插入，使S成为结点p的左子女。则S的前驱是T，后继是p.
void ThrTreeInsert(BiThrTree T,S)
//在中序线索二叉树T的右子树上插入结点S，使S成为T右子树中序遍历第一个结点
{p=T->rchild; //用p去指向T的右子树中最左面的结点 while(p->ltag==0) p=p->lchild;
S->ltag=1;S->rtag=1; //S是叶子，其左右标记均为1
S->lchild=T;S->rchild=p;//S的前驱是根结点T，后继是结点p
p->lchild=S;p->ltag=0; //将p的左子女指向S ，并修改左标志为0 }//结束 ThrTreeInsert
73．BiThrTree InOrder(BiThrTree T,ElemType x)
//先在带头结点的中序线索二叉树T中查找给定值为x的结点，假定值为x的结点存在
{p=T->lchild;//设p指向二叉树的根结点 while(p!=T)
{while(p->ltag==0 && p-data!=x) p=p->lc; if(p->data==x)return(p);
while(p->rtag==1 && p->rc!=T) {p=p->rc; if(p->data== x) return(p);} p=p->rc; } }//结束InOrder
BiThrTree AfterXNode(BiThrTree T)//在中序线索二叉树T中，求给定值为 x的结点的后继结点
{BiThrTree p=InOrde(T,x); //首先在T 树上查找给定值为x 的结点，由p指向
if(p->rtag==1) return(p->rc); //若p 的左标志为1，则p的rc指针指向其后继 else {q=p->rc; while(q->ltag==0)q=q->lc; return(q); }
//结点p的右子树中最左面的结点是结点p的中序后继 } }//结束AfterXnode
74．[题目分析]后序遍历是“左-右-根”，因此，若结点有右子女，则右子女是其后序前驱，否则，左子女（或左线索）指向其后序前驱。
BiThrTree PostSucc (BiThrTree T,p)//在后序线索二叉树T中，查找指定结点p的直接前驱q
{if(p->Rtag==0) q=p->Rchild;//若p有右子女，则右子女为其前驱
else q=p->Lchild; //若p无右子女，左子女或左线索就是p的后序前驱 return (q); }//结束PostSucc
75．BiThrTree InSucc(BiThrTree T,p) //在对称序穿线树T中，查找给定结点p的中序后继
{if（p->rtag==1）q=p->rchild; //若p的右标志为1，用其右指针指向后继 else {q=p->rchild; while(q->ltag==0) q=q->lchild; }//p的后继为其右子树中
41文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
最左下的结点
return (q); }//结束InSucc
76．[题目分析]在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，结点p在中序和后序下均无前驱。
BiThrTree InPostPre (BiThrTree t,p)
//在中序线索二叉树t中，求指定结点p在后序下的前驱结点q {BiThrTree q;
if (p->rtag==0) q=p->rchild; //若p有右子女，则右子女是其后序前驱 else if (p->ltag==0) q=p->lchild; //若p无右子女而有左子女，左子女是其后序前驱。
else if(p->lchild==null) q=null;//p是中序序列第一结点，无后序前驱 else //顺左线索向上找p的祖先，若存在，再找祖先的左子女 {while(p->ltag==1 && p->lchild!=null) p=p->lchild;
if(p->ltag==0) q=p->lchild; //p结点的祖先的左子女是其后序前驱 else q=null; //仅右单枝树（p是叶子），已上到根结点，p结点无后序前驱
}
return(q); }//结束InPostPre
77．[题目分析]在中序穿线二叉树中，求某结点p的后序后继q，需要知道p的双亲结点f的信息。（中序线索树的性质；若p是f的左子女，则f是p的最右子孙的右线索；若p是f的右子女，则f是p的最左子孙的左线索。）找到f后，若p是f的右子女，则p的后继是f；若p是f的左子女，且f无右子女，则p的后继也是f；若p是f的左子女，且f有右子女，则f的右子树中最左边的叶子结点是p的后继。因此，算法思路是，先找p的双亲f，根据p是f的左/右子女再确定p的后序后继。 BiThrTree InThrPostSucc(BiThrTree r,p)
//在中序线索二叉树r上，求结点p（假定存在）的后序后继结点q） {if(p==r)return(null) //若p为根结点，后序后继为空 T=p
while(T->LT==1) T=T->LL; //找p的最左子孙的左线索
q=T->LL; //q是 p最左子孙的左线索,是p的祖先 if(q->RL==p) return(q); //p是q的右子女，则q是p后序后继。 T=p;
while(T->RT==1) T=T->RL; //找p的最右子孙的右线索 q=T->RL; //q是p最右子孙的右线索 if(q->LL=p) //若p是q的左子女 if(q->RT==0) return(q);//若p是q的左子女且q无右子女，则p的后序后继是q else //p的双亲q有右子树，则q的右子树上最左下的叶子结点是p的后继 {q=q->RL;
while(q->LT==1||q->RT==1) //找q右子树中最左下的叶子结点
42文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
{while(q->LT==1) q=q->LL; //向左下
if(q->RT==1) q=q->RL; //若q无左子女但有右子女，则向右下，直到叶子结点 }
return(q); //q是的p后继 }
} //结束InThrPostSucc
[算法讨论] 请注意本题条件：标记为0时是线索，而为1时是指向子女。
78．[题目分析]第77题已讨论了在中序线索树中查找结点p的后序后继问题，本题要求在中序线索树上进行后序遍历。因后序遍历是“左右根”，最后访问根结点，即只有从右子树返回时才能访问根结点，为此设一标志returnflag,当其为1时表示从右侧返回，可以访问根结点。为了找当前结点的后继，需知道双亲结点的信息，在中序线索树中，某结点最左子孙的左线索和最右子孙的右线索均指向其双亲，因此设立两个函数LeftMost和RightMost求结点的最左和最右子孙，为了判定是否是从右子树返回，再设一函数IsRightChild。
BiThrTree LeftMost(BiThrTree t) //求结点t最左子孙的左线索 {BiThrTree p=t;
while(p->ltag==0) p=p->lchild; //沿左分枝向下
if (p->lchild!=null) return(p->lchild); else return(null); }//LeftMost
BiThrTree RightMost（BiThrTree t）//求结点t最右子孙的右线索
{BiThrTree p=t;
while(p->rtag==0) p=p->rchild; //沿右分枝向下
if (p->rchild!=null) return (p->rchild); else return(null); }//RightMost
int IsRightChild(BiThrTree t,father) //若t是father 的右孩子，返回1,否则返回0
{father=LeftMost(t);
if(father &&f ather->rchild==t) return(1); else return(0); }//Is RightChild;
void PostOrderInThr (BiThrTree bt) //后序遍历中序线索二叉树bt
{BiThrTree father, p=bt; int flag;
while(p!=null)
{while(p->ltag==0 ) p=p->lchild; // 沿左分枝向下
if(p->rtag==0) flag=0;//左孩子为线索，右孩子为链，相当从左返回 else flag=1; //p为叶子，相当从右返回 while(flag==1)
{visit(*p);//访问结点
if(IsRightChild(p,father)) {p=father; flag=1;} //修改p指向双亲 else //p是左子女，用最右子孙的右线索找双亲 {p=RightMost(p);
if(p&&p->rtag==1) flag=1; else flag=0;
}
}// while(flag==1)
43文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
if(flag==0 && p!=null) p=p->rchild; //转向当前结点右分枝 } }//结束PostOrderInThr
79．（1）哈夫曼树的构造过程
① 根据给定的n个权值{W1,W2,W3,…,Wn}构成n棵二叉树的集合F={T1,T2,…，Tn},其中每棵二叉树Ti只有权值为Wi的根结点，其左右子树均为空。
② 在F中选取两棵根结点的权值最小的树作左右子树构造一棵新二叉树，新二叉树根结点的权值为其左右子树上根结点的权值之和。
③ 在F中删除这两棵树，同时将新得到的二叉树加入F中。
④ 重复②和③，直到F中只剩一棵树为止。这棵树便是哈夫曼树。
（2）含有n个叶子结点的哈夫曼树共有2n-1个结点，采用静态链表作为存储结构，设置大小为2n-1的数组。现将哈夫曼树的结点及树的结构定义如下： typedef struct{float weight ; //权值
int parent,lc,rc;//双亲、左、右子女 }node ; typedef node HufmTree[2*n-1];
void Huffman(int n,float w[n],HufmTree T)
//构造n个叶子结点的哈夫曼树T，n个权值己放在W[n]数组中 {int i,j,p1,p2 //p1,p2为最小值和次最小值的坐标
float small1,small2; //small1和small2为权值的最小值和次小值 for(i=0;i<2*n-1;i++) //置初值，结点的权、左、右子女，双亲 {T[i].parent=-1; T[i].lc=-1; T[i].rc=-1;
if(i for (i=n ;i<2*n-1;i++) //构造新二叉树 {p1=p2=0;small1=small2=maxint; //初值 for(j=0;j if(T[j].weight else if(T[j].weight T[i].weight=T[p1].weight+T[p2].weight; //合并成一棵新二叉树 T[i].lc=p1; T[i].rc=p2; //置双亲的左右子女 T[p1].parent=i; T[p2].parent=i; //置左、右子女的双亲 }//for(i=0;i<2*n-1;i++) }//结束huffman 求哈夫曼编码的算法 typedef struct {char bit[n]; int start;}codetype; void HuffmanCode(CodeType code[n],HufmTree T) //哈夫曼树T已求出，现求其哈夫曼编码 {int i,j,c,p; CodeType cd; for(i=0;i {cd.start=n;c=i;p=T[i].parent; while(p!=-1) {cd.start--; if(T[p].lc==c) cd.bit[cd.start]=‘0’//左分枝生成代码‘0’ 44文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. else cd.bit[cd.start]=‘1’; // 右分枝生成代码‘1’ c=p; p=T[p].parent; //双亲变为新子女，再求双亲的双亲 } code[i]=cd; //成组赋值，求出一个叶子结点的哈夫曼编码 }//for }//结束HuffmanCode 80．[题目分析] 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下： typedef struct { int lvl; //层次序列指针，总是指向当前“根结点”在层次序列中的位 置 int l,h; //中序序列的下上界 int f; //层次序列中当前“根结点”的双亲结点的指针 int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数 {if (n<1) {printf(“参数错误\\n”); exit(0);} qnode s,Q[]; //Q是元素为qnode类型的队列，容量足够大 init(Q); int R=0; //R是层次序列指针，指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据 for (i=0; i if (i==0) //根结点无左子树，遍历序列的1—n-1是右子树 {p->lchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信 息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信 息入队列 } while (!empty(Q)) //当队列不空，进行循环，构造二叉树的左右子树 45文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.