内容发布更新时间 : 2024/12/23 1:55:07星期一 下面是文章的全部内容请认真阅读。

文档来源为:从网络收集整理.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版本可编辑.欢迎下载支持.