数据结构-考研复习题答案第6和二叉树

6章树和二叉CBDDBFBCBDCBAGDDCDFHI由二叉树结点的：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1010n=501，因此选以本题的AB均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。AB4452．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。√5.√√××××√××√×√×√××√×××××√×××√√×××√√×√×××√√24.i2i(2i<=n)37.其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无 ，38 3．p->lchild==null&&p->rchlid==null 4.(1)++a*b3*4-cd(2)18 7. 8.(1)2k-1(2)2k- 点。设编号为i和j的结点在顺序中的下标为s和t,则结点i和j在同一层上的条 12.(1)0(2)(n-1)/2(3)(n+1)/2(4)log2n14. 15.(1)2K+1-1(2) 16. 17.2k- 19. 20. 21.(1)n1-1222.(1)2k-2+1（k12H-12H-1/2=2k-2）(2)log224. 26. 27.28.(1)完全二叉树(2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左或29.N+130.(1)128(第七层满，加第八层１个 (2)1。 (2)n- (3) (4) (5) (6)n-34.(1)FEGHDCB 36.(1)EACBDGF（2）2 37.任何结点至多只有右38.(1)a(2)dbe(3) 39.(1).D.G.B.A.E.H.C.F.(2) （2） 43.二叉44.45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱(2)后 (6) 54.(1)655.(1)802)001（不唯一）56.2n0-则结束。否则分成四种情况讨论：x (2)Postorder_eval(t^.Rchild) 58.(1)IFt=NILTHENnum:=0ELSEIF(t=NIL)AND(m≤n)OR(t<>NIL)AND(m>n)THENELSEBEGINchk(t^.l,2*m);chk (7)rh+1 (2)p=stack[tp--] 64.①②(1)new(s) //初始化，申请结点(2)s^.next=NIL (3)s^.next^.data//取栈顶元素 (4)s^.next:=p^.next 栈(7)push(s,p^.rchild)//先沿树的左分支向下，将p的右入栈保(8)NOT (9)finishe:=true//已完 (10)finish=true（ (5)ins>>ch (3)q:=q^.pre（２（３）顺序可变） 69．(1)(i<=j)AND (3)k- (5)70. （3）push(s,p^.rchild)p71．(1)p=p->lchild//沿左子树向下（2）p=p->rchild 73. (2)t*2//沿左分枝向 （3）top-1//退 2（3）:=S.daa[stop]^.rchid(1)*ppos//根结 (3)nd^.left<>NIL(4)top:=top+1(1)p<>thr//未循环结束 (4)p->rtag=1&&p->rchild!=thr(5)p=p->rchild p^.rtag=1,p^.rchild为后继，否则pp (3)q^.lchild79（1）tre- (5)pre->right=tree;(6)tree->right(注（4）和（5）顺80（1）noe- (3)*x=node-树之分，即使在只有一个分枝的情况下，也必须是左子树还是右子树，树无此限制；每个元素有唯一后继树是一种层次结构有且只有一个根结点每个结点可以有多个，但只有一个双亲（根无双亲，从这个意义上说存在一（双亲）对多（）的关系。广义1按根结点运算符（+、-、*、/等）进行最后求值。 第5题nd-(n-1)=n(d-1)+1702n0n2nn=n0+n2…再设二叉树的分支数为 除根结点外，每个结点都有一个分支所指，n=B+1…… （1（1，并由（2）因为该树每层上均有Kh-1个结点，从根开始编号为1，则结点i的从右向左数第２个孩子的结点编号为ki。设n为结点i的，则关系式(i-1)k+2<=n<=ik+1成立，因i是nin-2)/k+1。1)*k+1第i(n-1)*k+1+i。1)%k!=0，n+1。各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1<n<=2h-1关系式。解O(logn)。10．2n-1n叶子，其余54个结点均为分支结点。它在第八层上有108个叶子结点。所以该二叉树的结812n1n2nn=m+n1+n2…………12120的nB （2中有（m-1）21。根据顺序的完全二叉树的性质，编号为i的结点的双亲的编号是i/2，故A[i]和if(i>j)i=i/2;else退出while后，若i/2=0,则最近公共祖先为根结点，否则最近公共祖先是i/2Ki(1<=i<=HKi-1N=1+k+k2+…+kH-1H=log(N(K-1)+1)K 另外从树的分枝数 与结点的关系 由（1）和（2）n0=n-nk=(n(K-用顺序结构n个结点的完全二叉树。编号为i的结点，其双亲编号是i/2(i=1时无双亲)，其左是2i(若2i<=n,否则i无左)，右是2i+1(若2i+1<=n,否则无右)。n/2+1设树的结点数为n，B， n=B+1= log2n 该结论不成立。对于任一a€A,可在B中找到最近祖先f。a在f的左子树上。对于从f到根结点路径上b€Bfb的右子树上，因而ab子树上，这时a＞b，a＜bb<ca∈A,c∈Ca<c。n个结点的m次树，共有n*m个指针。除根结点外，其余n-1个结点均有指针所指，故n*m-(n-1)=n*(m-1)+1。证毕。证明设度为12及叶子结点数分别为n0，n1n2，则二叉树结点数nn=n0+n1+n2n=B+112120（2设完全二叉树中叶子结点数为n，则根据完全二叉树的性质，度为2的结点数是n-1，而完全二叉树中，度为1的结点数至多为1，所以具有n个叶子结点的完全二叉树结点数是n+(n-1)+1=2n或2n-1（有或无度为1的结点。由于具有2n(或2n-1)个结点的完全二叉树>=2(1)根据二叉树度为2结点个数等于叶子结点个数减1的性质，故具有n个叶子结点且2n-1。(2)证明：当i=1时，2-（1-1）=20=1，成立。设当i=n-1时成立，证明当i=n时个新叶子结点，反映到中，因为2-(t-1)=2-(t+1-1)+2-(t+1-1)，所以结果不变，这就证明当i=n时仍成立。证毕．31（1）k(u-1)+1+i(2)(v-2)/k+1(参见第833（1）设有n个结点时，成立，即 现在要证明，当有n+1个结点时成立。l，则 （2，则s=（1+1/n）*u-1栈状态访栈状态访 栈状 问问问问问空空空空空1111121空 123 12123空2 12323空1空 2 3空2lrrn=m-1n=m设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一个元素PmSi(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，Si+1,Si+2,…,Sm若i=1，则S1时二叉树的左子树为树的结点数是m-1,则{S2，S3，…，若i=m,则Sm这时二叉树的右子树为的结点数是m-1，则{S1，S2，…，最后，当1<i<m时，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由P1P2…Pi- BB{Pi,Pi+1,…，Pm-1

B B 第40题41ABDCABDCEGFHILJMPNO 为独 分枝切掉（３）旋转（45。（２45（1）①tree[p]·l→p② ③ AA FC G

DGL

KJK

ABEIDHGABEIDHGLCFJKABDCABDCEFGIHP1，P2，…，PmS1,S2,…，Sm。因为（P1Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有：i=1S1=P1，，S1,S2,…,Si-1P2,P3，…，Pii=mSm=P1,,Si+1,Si+2,…，SmPi+1,Pi+2,…,Pm,去构造该二叉树的右子树。算法描56若前序序列是abcd，并非由这母的任意组合（4!=24）都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14种，即以abcd为前序序dcabFCDIAHEGB FCDIAHEGB

50分—左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子1空，ABECABECFGDHA EFGHIIABCDIABCDEFIGHJ

(52题(1)对应森林ABFGABFGCD JKLNO

53ABCDABCDEABCDEABABH1CIK25DJL46E3F7GAABGBCCHDDFEGIJEFK J剩“左右三种遍历的差别就根结点的机不同。叉树是递归“须先定义结点间相互关系的“左右。本解答中将N是M的左，当作N在M的左边，而N是M的右，当作N在M的右边。若定义P是M和N的最近公共祖先，N在P的左子树中，MPNM的左边，那时的答案是不一样的。先根遍历时n问中根遍历时n问后根遍历时n问NMNMNMNMAABCGH FIL 历的第一个结点。下面的语句段说明了这一过程（设p。{while(p->lchild!=null||p-{while(p->lchild!=null)p=p->lchild;if(p->rchild!=null)p=p->rchild;}} n1n2n1n2n1n2n1n2根据这条规则来判断若结点n1序序列中在n2之前，在后序序列中又在n2之后，则它n2 （2）前序序列：ABCEDFHGIJ （递归）消除。如中序遍历递归算法中，最后的递归语句inorder(bt->rchild)可改为下列语句段：bt=bt-while(bt-{inorder(bt->lchild);printf(“%c”,bt->data);//根结点，假定结点数据域为bt=bt->rchild;若知道各结点的后继二叉树的遍历就变成非常简单。二叉链表结构查结点的左右非常ltag和rtag，规定ltag=0，lchild指向左,ltag=1时,lchild指向前驱；当rtag=0时,rchild指向右，rtag=1时，rchild指向后继。这样，索二叉树（特别是中序KK OPABABCD 67题（2）BiTreeINORDER-PRIOR(N,X)N{if(n->ltag==1){X=N->lchild;return(X);}else{p=N->lchild;while(p->rtag==0)p=p->rchild;X=p;return(p);}}FHFHIABABDGCE70题中序序列：ECBHFDJIGA71题71while（p->ltag==0）p==p->lchild;//找最左下叶子结点while（p->rchild!=null）{visit(p->data);//结点；p=p->rchild;}//沿线索向上（ltag=0，否则若结点有右（rtag=0则右是后继若无右（rtag=1右是线索，if(p->ltag==0)return(p->lchild);//左不空，左为直接后继结elsereturn(p->rchild);//左空，右（或右线索）为后ABCDEFGHIJK010001011112578528931001011001134.c1:0110c2:10c3:0010c4:0111c5:000c6:010c7:1178.字符A，B，C，D出现的次数为9,1,5,3。其编码如下A:1，B:000，C:01，79（2）wp=(2+3)*+6*4+(914+15)*+(16+1)*2229001019015 78 编码编码为：15:111,3:1010114:1102:10100,6:1011,9:100,16:00,常用树为通讯用的字符编码本题中集合的数值解释为字符发生的频（次数。由树构造出编码。译码时，进行编码的“匹配，即从左往右扫描对方发来的（Fk（若需加虚权值，则第一次选（m-1）%(k-1)+1）个权值最小的树作子树，k，kkFkkFFkk结点权值等于所选的kFk并将新得到的树加到F（3102最小路径长度：1A30002B0003C70004D40005E2000660000000B00000C70000010D4000011E2000012F80000013G000008595360

81．初态图前缀的编码。例如，001不是前缀从编码来看，001但因历一编码不是另一编码前缀的编码称为结点到叶子结点的0、1串就是叶子的前缀码。用树可构造出最优二叉83．树只有度为0的叶子结点和度为2的分枝结点，设数量分别为n0和n2，则树的结点数nn=n0+n2。另根据二叉树性质：任意二叉树中度为0的结点数n02的结n2n2=n0-1n=n0+n2=2n0-1。84（1）T85（1） （3）错误（4）正确 深度少1。1．[题目分析]以二叉树表示算术表达式，根结点用于运算符。若能先分别求出左子树typedefstruct{ElemTypedata;floatcharoptr‘*structnode*lchild，*rchildfloatPostEval(BiTreebt){floatlv,rv;{lv=PostEval(bt->lchild);rv=PostEval(bt->rchild);{case‘+’:value=lv+rv;break;case‘-’:value=lv-rv;break;case‘*’:value=lv*rv;break;case‘/’:value=lv/rv;}}return(value);2.[intPrecede(char//比较运算符级别高低，optr1optr21，0，低于时返

cas‘*cas‘/if(optr=‘*||opt2=‘/)return(0)else}voidInorderExp(BiTree{intbracket;{if(bt-{bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左运算符优if(bracket==1) if(bracket==1)printf(‘)’)；}printf(bt if(bt- if(bracket==1)printf(“(”)；//右级别低，加括InorderExp(bt->rchild);}InorderintvoidPostOrder(BiTreett{PostOrder(t->lchild);PostOrder(b->rchild)；ar[i++]=b->data;PostOrdervoidEXPVALUE(){ar[i]=‘\0’;//给后缀表达式加上结束标记charvalue[];//存放操作数及部分运算结果i=1;ch=ar[i++];{casechinop:opnd1=pop(value);opnd2=pop(value); } } 1，其细节不再深入讨论。typedefstruct{ElemTypedata;/structnode*fch*nsib*Tree;intLeaves(Treet) return(1+Leaves(t->nsib));//返回叶子结点和其兄树中的叶子结点数elsereturn(Leaves(t->fch)+Leaves(t->nsib));//孩子子树和 树中叶5．[iL[i]R[i]，很容易建立指iT[iTUV为判断结点VUintGeneration(int//L[R[]NiiT，并判断结点UV{for(i=1;i<=N;i++)T[i]=0;//Tfor if(L[i]!=0)T[L[i]]=i; //若结点i的左是L，则结点L的双亲是结点iif(R[i]!=0)T[R[i]]=i; //i的右是r，则r的双亲是iintparent=U; //判断U是否是V的后代while(parent!=V&&parent!=0)if(parent==V){printfUVreturn(1);}else{printf(“UV的后代”);return(0);}BiTreeCreat()//建立二叉树的二叉链表形式的结{ElemTypex；BiTreescanf(“%d”,&x);//本题假定结点数据域为整型if(x==0)bt=null;else{bt=(BiNodebt->data=x;bt->lchild=creat();bt-}elseerror(“输入错误”)； plete(BiTreebt)1，否0{inttag=0;BiTreep=bt,Q[];//Qif(p==null)returnQueueInit(QQueueIn(Q,p);//初始化队列，根结点指针入队while(!QueueEmpty(Q)) if(p->lchild&&!tag)QueueIn(Q,p->lchild);//左入else{if(p->lchild)return0; elsetag=1; if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右入队elseif(p->rchild)return0;else}return1; BiTreeCreat(ElemTypeA[],int//nA{BiTreeif(i<=n){tree=(BiTree)malloc(sizeof(BiNode));tree->data=A[i];if(2*i>n)tree->lchild=null；elsetree->lchild=Creat(A,2*i)；if(2*i+1>n)tree->rchild=null；elsetree->rchild=Creat(A,2*i+1)；}return(tree)；}//Creat树的高度等于左右子树高度的大者加1这里二叉树为空的标记不是null而是0。设根结点1，1。现将二叉树的结构定义如下:typedefstructnode{intL[]iintR[];//iintD[];//iinti;//结点的顺序号（下标）intHeight(tnodet,inti{intif(i==0)return(0);else{lh=Height(t,t.L[i]);rh=Height(t,t.R[i]);if(lh>rh)return(lh+1);else}intLevel（tnodet）//11for(i=1;i<=n;i++){depth=t.D[i]； t.D[t.R[i]]=depth+1;}//itypedef{BiTreebt;intnum;}tnode//numtnodeQ[maxsize];//循环队列,容量足够大voidcreat(BiTreeT,ElemTypeBT[]){tnode intlen=2h-1; T=(BiTree)malloc(sizeof(BiNode));//申请结点 tq.bt=T;tq.num=1; {front=(front+1)%maxsizetq=Q[front];p=tq.bt;i=tq.num; if(BT[2*i]==‘#’||2*i>len)p->lchild=null;//左子树为空，‘#’表示虚 //建立左结点并入队{p->lchild=(BiTree)malloc(sizeof(BiNode));//申请结点空间p- //左数tq.bt=p->lchild;tq.num=2*i;rear=(rear+1)%maxsize;//计算队尾位置 }if(BT[2*i+1]==‘#’||2*i+1>len)p->rchild=null;//右子树为空 {p->rchild=(BiTree)malloc(sizeof(BiNode);//申请结点空间p->rchild->data=BT[2*i+1];tq.bt=p->rchildrear=(rear+1)%maxsize; }}[算法讨论]本题中的虚结点用‘#’表示。应根据二叉树的结点数据的类型而定。dataQ，lchildrchildtypedefstruct {ElemTypedata; introw,lchild,rchildcomponentst[];//ststructnode{BiTreet;intidx;}qbt;staticintnum=0;voidPreOrder(BiTree{if{st[++num].data=bt->data;st[num].row=num;PreOrder(bt->lchild);PreOrder(bt->rchild);}intLocate(ElemType{for(i=1;i<=num;i++)if(st[i].data==x)return}voidDynaToST(BiTreebt){int if{QueueInit(Q);//Qqbtqbt.t=bt;qbt.idx=1;QueueIn(Q,qbtst[1].data=bt->data; p=qbt.t if(p- //若左存在,查其在静态链表中的下标,lchildqbt.t=p->lchild;qbt.idx=lch;QueueIn(Q,qbt);}else if(p- //若右存在,查其在静态链表中的下标，rchildqbt.t=p->rchild;qbt.idx=rch;QueueIn(Q,qbt);else 11.[题目分析]由于以双亲表示法作树的结构，找结点的双亲容易。因此我们可求出intDepth(Ptree {intmaxdepth=0;{temp=0;while(f>0){temp++;f=t.nodes[f].parent;} 1,并取新的双亲if(temp>maxdepth)maxdepth=temp;//最大深度更新}return(maxdepth);//返回树的深12.intHeight(btrebt)/bt{intif(bt==null)else{hl=Height(bt->lch);hr=Height(bt->rch);if(hl>hr)return(hl+1);elsereturn(hr+1);}13．[intWidth(BiTreebt)/bt{if(bt==null)return(0);//空二叉树宽度为0front=1;rear=1;last=1;//front,rear,lasttemp=0;maxw=0; //temp记局部宽度,maxw记最大宽度 {p=Q[front++];temp++;if(p->lchild!=null)Q[++rear]=p- //左入if(p->rchild!=null)Q[++rear]=p- //右入if if(temp>maxw)maxw=temp;//lastreturn(maxw);第一为空，高度为1和兄树的高度的大者；否则，高度为第一树高度加1和兄intHeight(CSTreebt)//递归求以孩子兄弟链表表示的树的深度{intif(bt==null)returnelseif(!bt->firstchild)return(1+height(bt->nextsibling);//空，查兄else//结点既有第一又有兄弟，高度取高度+1和兄树高度的者{hc=height(bt->firstchild)；//第一树高if(hc+1>hs)return(hc+1);elsereturn(hs);}intheight(CSTree {if(t==null)else{intfront=1,rear=1;//front,rearint 度 {if(t->firstchild)Q[++rear]=t->firstchild;//第一入t=t->nextsibling;} //的祖先。本题要找pq的最近共同祖先结点r,不失一般性pq左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点pqtypedef{BiTreet;inttag;//tag=0表示结点的左已被，tag=1表示结点的右被stacks[],s1[];//BiTreeAncestor(BiTreeROOT,p,q,r)/pqr{top=0;bt=ROOT;while(bt!=null||top>0){while(bt!=null&&bt!=p&& {s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}if(bt==p)pqpp点{for(i=1;i<=top;i++)s1[i]=s[i];top1=top;ss1存if(bt==q)qfor(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹for(j=top1;j>0;j--｝while(top!=0&&s[top].tag==1)top if(top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝while(bt!=null||top>0)return(null);//ｑ、p无公｝//16.[题目分析]二叉树顺序，是按完全二叉树的格式，利用完全二叉树双亲结点与voidAncestor(ElemTypeA[],int//二叉树顺序在数组A[1..n]中，本算法求下标分别为i和j的结点的最近公共祖先结if(i>j else }//成兄弟（即父的所有儿子兄弟结点又成为新的父，其左是兄弟（父的儿子）妻，妻BiTreeSearch(BiTreet,ElemTypefather)/father{if(t==null)return elseif(t->data==father)return(t); p=Search(t->lchild,father);p=Search(t->rchild,father);voidPrintSons(BiTreet,ElemTypep)p {q=p->lchild;q=q->rchild; while(q!=null){printf(q->data);q=q->rchild;}//输出父的所有儿子}18.[题目分析]后序遍历最后根结点，当到值为x的结点时，栈中所有元素均为该voidSearch(BiTreebt,ElemTypex)btx{typedef{BiTreet;inttag;}stack;//tag=0表示左被，tag=1表示右stacks[];//栈容量足够大{while(bt!=null&&bt {s[++top].t=bts[top].tag=0;bt=bt->lchild;} //找xfor(i=1;i<=top;i+printf(s[i].t->data);return;while(top!=0&&s[top].tag==1)top--; if(top!=0){s[top].tag=1;bt=s[top].t->rchild;}//沿右分枝向下遍历}//O(logn)voidPreOrder(Bitreebtbt{inttop=0;Bitrees[];//topswhile(bt!=null||{printf(bt->data);//根结if(bt->rchlid)s[++top]=bt->rchild;//若有右，则右进bt=bt->lchild;if(top>0)bt=s[top--}C,H,K,F20.[题目分析]二叉树的顺序是按完全二叉树的顺序格式，双亲与结点下标间voidPreOrder(ElemTypebt,intn)//对以顺序结构的完全二叉树bt进行前序遍{inttop=0,s[];//tops{ if(2*i+1<=n) i=2*i; if(top>0)i=s[top 下标，而且用正或负表示该结点是双亲的右或左。该类结构不适于直接进行前序女的顺序结构，即Tree2=ARRAY[1..max]OFRECORDdata:char;lc,rc:integer;END;//结点的左 voidChange(Treet,Tree2bt,int*root)t{for(i=1;i<=max;i++){bt[i].lc=bt[i].rc=0;}//先将结点的左右初始化为0 //填入结点数据，和结点左右的信息if(t[i].parent<0)bt[-t[i].parent].lc=i;//左elseif(t[i].parent>0)bt[t[i].parent].rc=i;//右else*root=i;//root}voidPreOrder(Tree2 {int*root,top=0;ints[];//schange(t,bt,root);inti=*root;{while{printf(bt[i].data)；if(bt[i].rc!=0)s[++top]=bt[i].rc;//右进}if(top>0)i=s[top--voidPreOrder(introot)//root是二叉树根结点在顺序中的下标，本算法前序遍历bt的数据结构，以便于运算。象上面第5题也是这样，先根据L和R数组，构造一个结点的双T。BiTreeLastNode(BiTreebt)bt{BiTreeif(bt==null)return(null);elsewhile(p)if(p->rchildp=p->rchild;elseif(p->lchild)p=p->lchild;//右子树空，左子树不空，沿左子树向下elsereturn(p); //p即为所求23.[题目分析]高度为K的二叉树，按顺序方式，要占用2K–1个单元，与实际结intm=2K–1;voidPreOrder(ElemTypebt[],i1{if {printf(bt[i])；//根结if(2*i<=m&&bt[2*i]!=0)PreOrder(bt,2*i); if(2*i+1<=m&&bt[2*i+1]!=0)PreOrder(bt,2*i+1} voidAncesstor(ElemType {c=m;while(bt[c]==0)c-- //cwhile(f!=0)//从结点c{printf(bt[f]);f=f/2;24.voidInOrder(BiTree{BiTrees[],p=bt;//sinttop=0;while(p||top>0){while(p){s[++top]=p;bt=p->lchild;} if(top>0){p=s[top--];printf(p->data);p=p->rchild;}//退栈， 25.[题目分析]二叉树用顺序方式，其遍历方法与用二叉链表方式类似。判空时，在二叉链表方式下用结点指针是否等于null，在顺序方式下，一是下标是否是“虚结点二是下标值是否超过最大值（高为H的二叉树要有2H-1个单元，与实际结点个数关系不大。当然，顺序方式下，要告诉根结点的下标。voidInOrder(inti)//对顺序的二叉树进行中序遍历，i是根结点的下 printf(ar[i].data);//根结点 }voidInvertLevel(biTreebt){StackInit(s);//栈初始化，栈中存放二叉树结点的指针QueueInit(Q); {p=QueueOut(Q); if(p->lchild)QueueIn(Q,p->lchild);//若左不空，则入队if(p->rchild)QueueIn(Q,p->rchild);}//若右不空,则入队while(!StackEmpty(s)){p=pop(s);printf(p->data);}//自下而上,从右到左的27.intLevel(BiTreebt)1{intnum=0;//num1{p=QueueOut(Q);printf(p- 结if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度为1if(p->lchild)QueueIn(Q,p->lchild);//非空左入if(p->rchild)QueueIn(Q,p->rchild);//非空右入}return(num128.voidexchange(BiTreebt)/bt{if(bt){BiTrees=bt->lchild;bt->lchild=bt->rchild;bt->rchild=s;//左右交换exchange(bt->lchild);//交换左子树上所有结点的左右子树exchange(bt->rchild);//交换右子树上所有结点的左右子树}voidexchange(BiTree {inttop=0;BiTree {t=s[top--if(t->lchild||t->rchild){p=t->lchild;t->lchild=t->rchild;t-if(t->lchild)s[++top]=t->lchild;//左入if(t->rchild)s[++top]=t->rchild;//右入 voidPreToPost(ElemTypepre[],post[],int//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2 PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)//将左子树先序序列转为PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)//将右子树先序序列转为}BiTreeIntoPost(ElemTypein[],post[],int//inpost,l1,h1,l2,h2for(i=l1;i<=h1;i++)if(in[i]==post[h2])break;//在中序序列中查找根结点if(i==l1)bt->lchild=null;//处理左子树elsebt->lchild=IntoPost(in,post,l1,i-1,l2,l2+i-l1-1)；if(i==h1)bt->rchild=null;//处理右子树elsebt->rchild=IntoPost(in,post,i+1,h1,l2+i-l1,h2-1);return(bt);}TYPEbinode=RECORDdata:ElemType;lchild,rchlid:bitreptrEND;PROCPreOrder(bt:bitreptr);//非递归前序遍列二叉树VARS:ARRAY[1..max]OF WHILE(bt<>NIL)OR(NOTempty(S))DO[WHILE(bt<>NIL)DO[write(bt↑data);push(S,bt->rchild);bt:=bt↑.lchild;]//结点,右栈WHILE(NOTempty(S)ANDtop(S)=NILbt:=pop(SIFNOTempty(S)THEN]0。叶子和双亲结点下标间的关系满足完全二叉树的性质。intLeaves(inth)//求深度为h以顺序结构的二叉树的叶子结点{intBT[intlen=2h-1,count=0;//BT2hfor(i=1;i<=len;i++)1if(BT[i]!=0)0if(i*2)>len) //第i个结点没，肯定是子elseif(BT[2*i]==0&&2*i+1<=len&&BT[2*i+1]==0)count++;//无左右return33.[题目分析]计算每层中结点值大于50应按层次遍设一队列Qfronttypedefstruct{intlevel,value,idx;}node;//元素所在层号、值和本层中的序号nodea[],s;voidValueGT50(BiTreebt50BiTreeQ[];Q[1]=bt;//根结点入队 if(front==last){last=rear;level++;i=0for(i=1;i<=num;i++)data50data=%3da].level,a[].idx,ai].valu);PROC//将二叉树逆时针旋转90度打印，xy是根结点基准坐标，调用时xy=40IFbt<>NILTHEN[print(bt↑.rchild,xy+5); wrin(bt- //根结 BiTreecreat()/BiTree {s=(BiTree)malloc(sizeof(BiNode));s->data=ch;s->lchild=s->rchild=null;if(bst==null) if(ch>p->data)f=p;p=p- else{f=pp=p if(f->data<ch)f->rchild=selsef->lchild=s;}//sscanf(“%c”,&ch);}//while(ch!=‘#’)return(bstcreatvoidInOrder(BiTree {InOrder(bst->lchild);printf(bst->data);InOrder(bst->rchild);36.[题目分析]二叉树结点p所对应子树的第一个后序遍历结点q的求法如下：若p有左子qp的左子树上最左下的叶子结点p左子树，仅有右子树qp的右子BiTree{BiTreeif(!q)return(null);while(q->lchild||q->rchild);if(q->lchild)q=q- 点elseq=q->rchild; }voidPreInCreat(ElemTypeA[],B[]，intA[1..n]B[1..n]建立二叉树,l1,h1,l2,h2。{typedefstruct{intl1,h1,l2,h2;BiTreet;}node;BiTreebt;inttop=0,i;node //申请结点空间p.l1=l1;p.h1=h1;p.l2=l2;p.h2=h2;p.t=bts[++top]=p;{p=s[top--];bt=p.t;l1=p.l1;h1=p.h1;l2=p.l2;h2=p.h2;//取出栈顶数据for(i=l2;i<=h2;i++)if(B[i]==A[l1])break; if(i==l2)bt->lchild=null; //bt无左子树 {bt->lchild=(BiTree)malloc(sizeof(BiNode));p.t=bt->lchild;p.l1=l1+1;p.h1=l1+i-l2;p.l2=l2;p.h2=i-1;s[++top]=p;if(i==h2)bt->rchild=null;btelse{bt->rchild=(BiTree)malloc(sizeof(BiNode));p.t=bt->rchild;p.l1=l1+i-l2+1;p.h1=h1;p.l2=i+1p.h2=h2;s[++top]=p;nvoidInPostCreat(ElemTypeIN[],POST[],intIN[]POST[]建立二叉树，l1,h1l2,h2{typedefstruct{intl1,h1,l2,h2;BiTreetnode;nodes[],p;//sBiTreebt=(BiTree)malloc(sizeof(BiNode));intp.l1=l1;p.h1=h1;p.l2=l2;p.h2=h2;p.t=bts[++top]=p;//初始化{p=s[top--];bt=p.t;l1=p.l1;h1=p.h1;l2=p.l2;h2=p.h2;//取出栈顶数据for(i=l1;i<=h1;i++)if(IN[i]==POST[h2])breakPOST[h2] if(i==l1)bt->lchild=null; //bt无左子树 {bt->lchild=(BiTree)malloc(sizeof(BiNode));p.t=bt->lchild;p.l1=l1;p.h1=i-1;p.l2=l2;p.h2=l2+i-l1-1;s[++top]=p;}if(i==h1)bt else{bt->rchild=(BiTree)malloc(sizeof(BiNode));p.t=bt->rchild;p.l1=i+1;p.h1=h1;p.l2=l2+i-l1;p.h2=h2-1;s[++top]=p;}//右子树}//39．BiTreeCopy(BiTreet)//二叉树{BiTreeif(t==null)bt=null;else{bt=(BiTree)malloc(sizeof(BiNode));bt->data=t->data;}return(bt);结点的分支个数B，而分支数B与树的结点数N的关系是N=B+1（除根结点外，任何一个结点都有一个分支所指E[i]的第一个单元将值累加到第i个单元，其值正好等于i-1时，就是第一棵树。接着，用相同方法，将其它树分开，进行到第n个单8（=B+1）时，正好结束第一棵树。i123456789ABDGLHEICFJK322000000100void(ElemTypeH[],intH[i]FE[i]H[i]所指结点的次数，本算法//FF{inti=1,sum=0,j=0,m=0;//sum，j，m数inttree[]; //treeH[i]中的地址while(i<=n)//n{sum+=E[i];if(sum+1==m&&i<=n){sum=0;m=0;tree[++j]=i;}if(j==1)return(1); elsereturn(tree[j-1]+1)rchildrchildLinkedList LinkedListInOrder(BiTree if(bt->lchild==null&&bt->rchild==null)if(pre==null){head=bt;pre=bt;}//处理第一个叶子结点else{pre->rchild=bt;pre=bt; }return(head);}40右子树。如先序序列AB和后序序列BA，A是根，但B可以是左，也可以是右。43.[2个则入队列如此下去直到碰到叶子结点或只有一个的结点再重复上述动作，typedefstruct{ElemTypedata;structnode*firstchild,*secondchild;*Tree;voidTreeTravers(Treet)//按字母顺序输出树中各结点的值{Tree if{QueueInit(Q);QueueIn(Q,t while(p->firstchild&&p- p=p->firstchild;}//沿第一向if(p->firstchild){printf(p->data);QueueIn(Q,p->firstchild)}if(!p->firstchild&&!p->secondchild)printf(p->data);//叶子结44.[bfintHeight(BiTreebt)/bt{intif(bt==null)else{hl=Height(bt->lchild);hr=Height(bt->rchild);if(hl>hr)return(hl+1);elsereturn(hr+1);}}//HeightvoidBalance(BiTreebt){if{Balance(bt->lchildBalance(bt->rchildhl=Height(bt->lchild);hr=Height(bt->rchild);//求左右子树的高度bt->bf=hl-hr;bf 用树T的顺序结构A[1..n]作队列，队头指针front，队尾指针rear，元素最大下标voidTraverse(BiTreebt,int//求二叉树bt的顺序结构A[1..n]，下标超过n报错，给出实际的最大下{BiTreeA[],p;{intfront=0,rear=1,last=1;A[1]=bt;{p=A[++front];if(p)last=front;last标if printf(“%c结点无左”);elseA[rear]=p->lchild;}else//p{if(rear<=n)A[rear]=null;if(rear+1<=n)A[rear+1]=null;}// intSimilar(BiTreep,q)pq{if(p==null&&q==null)returnelseif(!p&&q||p&&!q)return 47.[CSTreePtreeToCstree(PTreept,intpt，root{CSTreechild,sibling;intCSTreecst=(CSTree)malloc(sizeof(CSNode for(i=1;i<=pt.n;i++)root else//childroot}//endreturncst;空，用层次遍历易于找到某结点的父结点。本题要求删除树中每一个元素值为xvoidDeleteXTree(BiTreebt)bt(bt); voidSearch(B:Treebt,ElemType{if(bt->data==x){DeleteXTree(bt);exit(0)x，则删除整{QueueInit(Q);QueueIn(Q,bt);if(p- //若 非if(p->lchild- //左结点值为x,应删除当前结点的左树{DeleteXTree(p->lchild);p->lchild=null;}//父结点的左置elseEnqueue(Q,p->lchild);//左入队if(p- //若右非if(p->rchild- //右结点值为x,应删除当前结点的右树 p->rchild=null;}//父结点的右置elseEnqueue(Q,p->rchild);//右入队}//if(bt)49.[48（xx4848的关系，成双亲和间指针的#’是输结束标志‘$’{BiTreep,Q[]，root;//Qcharch;intrear=0;p->data=ch;p->lchild=p->rchild=null;Q[++rear]=p;if(p){if(rear==1){root=p;root->parent=null;}//根结点else{Q[rear]->parent=Q[rear/2];/双亲结点和结点用指针链上 }return(rootintBTLC(BiTreeT,int*c)/TBTLC(T->lchild,&c);BTLC(T->rchild,&c);Count,调用时intCount(CSTreet){if(t==null)elseif(t->firstlchild==null)//左为空，结点必为叶 elsereturn(Count(t->firstchild)+Count(t->nextsibling));//子树兄voidCount(BiTreebt,int*n0,*n)btn0n{if(bt->lchild==null&&bt->rchild==null)*n0++；//叶子结点else*n++;//非叶结点 intCount(BiTreebt){intBiTrees[//swhlie(bt!=null||{while(bt!=null)push(s,bt)；bt=bt->lchild；}//沿左分支向下}}intLeafKlevel(BiTreebtintk)btk(k>1){if(bt==null||k<1)BiTreep=bt,Q[]; //Qintfront=0,rear=1,leaf=0;//frontrearleafintlast=1,level=1;Q[1]=p;lastlevelif(level==k&&!p->lchild&&!p->rchild)leaf++;//叶子结点if(p->lchild)Q[++rear]=p- //左入if(p->rchild)Q[++rear]=p- //右入if(front==last){level++; last=rear;} //last移到指向下层最右一元素if(level>k)return k}//whiletypedefstruct{ElemTypedata;intnum;structnode*lchild,*rchild;voidPostOrder(Btree//对二叉树从1开始编号，结点编号大于其左右结点编号，结点的左编号小于其右编号{typedefstruct{Btreet;inttag; Btreep=t;nodesn,s[]; //sintk=0,top=0;//ktopwhile(p!=null||top>0){while(p){sn.t=p;sn.tag=0;s[++top]=sn;p=p->lchild;}//沿左分枝向下while(top>0&&s[top].tag==1){sn=s[top--];sn.t->num=++k;}//左右孩子已遍历,if(top>0){s[top].tag=1;p=s[top].t-}//while(p!=null||voidPreInCreat(BiTreeroot,ElemTypepre[],in[],int{root=(BiTree)malloc(sizeof(BiNoderoot->data=pre[l1];//pre[l1]是根for(i=l2;i<=h2;i+if(in[i]==pre[l1])breakif(i==l2)root->lchild=null;elsePreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)；//递归建立左树if(i==h2)root->rchild=null;elsePreInCreat((root)->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2)//递归建立右57（1）23038voidPrintPath(BiTreebt,p)btp{BiTreeq=bt,s//sinttop=0;tag[];//tag是数组，元素值为0或1，左、右子树的标志，tagsif(q==p){printf(q->data);returnwhile(q!=null||top>0){while(q!=null)//左入栈，并置标 ppfor(i=1;i<=top;i++)printf(s[i]->data);printf(q->data);}else{s[++top]=q;tag[top]=0;q=q—>lchild;}if(top>0){q=s[top];q=q->rchild;tag[top]=1;}//沿右分支向下}//while(q!=null||for(i=1;i<=top;i++)printf(s[i]->data);//qprintf(q->data);voidLongestPath(BiTreebt)/{BiTreep=bt,l[],s[];l,slinti，top=0,tag[],longest=0;while(p||top>0)while(p){s[++top]=p；tag[top]=0;p=p->Lcif(tag[top]==1)//当前结点的右分枝已遍历{if(!s[top]->Lc&&!s[top]->Rc)//只有到叶子结点时，才查看路径长度if(top>longestfor(i=1;i<=top;il[i]=s[ilongest=top;top}elseif(top>0){tag[top]=1; 61.[题目分析]索二叉树上插入结点,破坏了与入结点的线索因此,插入结点时,必须修复线索。在结点y的右侧插入结点x，因为是后序线索树，要区分结点y有无左子树的voidTreeInsert(BiTreet,y,x)ty{if(y->ltag==0)//y{p=y->lchild;if(p->rtag==1)p->rchild=x;//x是y的左的后序后x->ltag=1;x->lchild=p;//xy}else//y; //若y的后序前驱的右标记为1 }x->rtag=1;x->rchild=y;y->rtag=0;y->rchild=x//xy}//结束62.[题目分析]在中序全线索化T树的P结点上，插入以X为根的中序全线索化二叉树，要对X有无左右子树进行讨论，并修改X左(右)子树上最左结点和最右结点的线索。在中序线索树上查找某结点p的前驱的规律是：若p->ltag=1，则p->lchild就指向前驱，否则，其前驱是p的左子树上按中序遍历的最后一个结点；查找某结点p的后继的规律是：若p->rtag=1，则p->rchild就指向后继，否则，其后继是p的右子树上按中序遍历的第一个intTreeThrInsert(BiThrTree//在中序全线索二TPX的中序全线索二叉树，返回插入{if(P->ltag==0&&P->rtag==0){printf(“P有左右，插入失败\n”)；return(0);if(P->ltag==0)//P有左，将X插为P的{if(X->ltag==1X->lchild=P;//若XXPelseX（下）边的结点{q=X-while(q->ltag==0)q=q->lchild;}if(X- X->rchild=P->rchild;PXelseX{q=X->rchild;while(q->rtag==0)q=q->rchild;} XP //P有右，将X插入为P的左{if(X- X->lchild=P->lchild;PX //X有左，找X左子树上最左边的结{q=X-while(q->ltag==0)q=q->lchild;}if(X->rtag==1)X- {q=X-while(q->rtag==0)q=q->rchild;}P->ltag=0;P0P->lchild=X;//P的左到XP}TreeP）并将数据域为x的Q结点插入到左子树中。若P无左，则Q成为P的左,原P的左线索成为Q的左线索，Q的右线索为P；若P有左子树，设P左子树中最右结点的右线索Q，QP。voidInThrInsert(BiThrTreeT,Q;ElemType{BiThrTreeP=T;{while(P->LT==0&&P->data!=A)P=P->LL;if(P->data==A while(P->RT==1)P=P->RL;AP=P- }if(P->LT==1)//PQP{Q->LL=P->LL;Q->LT=1；PQ}else//PP{Q->LL=P->LL;Q->LT=0;//QPs=Q- while(s->RT==0)s=s->RL;Ps- }P->LT=0;P->LL=Q;PQ->RT=1;Q->RL=P;//将Q链为P的左,其中序后继是BiTreehead=null,pre;voidCreatLeafList(BiTreebt)//将BiTree树中所有叶子结点链成结点的双 if(bt->lchild==null&&bt->rchild==null)//叶子结点if(head==null)//第一个叶子结//生成头结点head->lchild=null;head->rchild=bt;

bt->lchild=head;pre=bt;//第一个叶子结点左链指向头结点，pre} {pre->rchild=bt;bt->lchild=pre;pre=btCreatLeafList(bt->rchild);//中序遍历右子树pre->rchild=null;//最后一个叶子结点的右链置空（链表结束标记}//if(bt)}//结束65.[题目分析]求中序全线索树任意结点p的前序后继，其规则如下：若p有左，则左就是其前序后继；若p无左而有右，则p的右就是p的前序后继；若p无左右，这时沿p的右线索往上，直到p的右标志为0（非线索这时若p的右if(p->ltag==0&&p->lchild!=null)return(p->lchild);//p的左是p的前序elseif(p->rtag==0)&&p->rchild!=null)return(p->rchild);//p右是其前 0{while(p->rtag==1)p=p-if(p->rchild)return(p->rchild);elsereturn(null);对应指针为空，pBiTreeAfter(BiThrTreet)t{if(t->rtag==1)return(t->rchild);while(p->ltag==0)p=p->lchild;/ppreturn(p);}voidInOrder(BiThrTree{p=bt->lchild;//pif(p!=bt){while(p->ltag==0)p=p->lchildwhile(p!=bt)//没回到头结点，就一直找后继并遍历{visit(*p);p=After(p);}//if中序穿线树中线索“向上”指向祖先的特点：若结点p是结点q右子树序遍历最左下的结点，p的左线索指向q；若结点p是结点q左子树上中序遍历最右下的结点，p的右线索指向是q。反过来，通过祖先找就容易了。另外，若结点q的后继是中序穿线树的头结voidFFA(BiThrTreet,p,qtp{q=p;while(q->RTAG==0)q=q->RLINK;pq=q- if(q==t)q=t->LLINK;if(q==p){printf(“根结点无双亲\n”)；return;}if(q->LLINK==p)return(q);elseq=q->LLINKwhile(q->RLINK!=pq=q->RLINK；return(qp后一个结点的rchild指向头结点。故从头结点找到根结点后，顺“后继”二叉树。在65voidPreorderInThreat(BiTrhTree{while(bt->ltag==0){printf(bt->data);bt=bt->lchild;}//沿左分枝向下 //遍历其左标志为1的结点，准备右转while(bt->rtag==1&&bt->rchild!=tbt)bt=bt->rchild;//沿右链向上if(bt->rchild!=tbt)bt=bt->rchild;//沿右分枝向下}在“根结点”处进行加线索的改造，就可实现前序，中序和后序的线索化BiThrTreepre=null;//设置前驱voidPreOrderThreat(BiThrTreeBT){if{if(BT->lchild==null){BT->ltag=1;BT->lchild=pre;}//if(pre!=null&&pre->rtag==1)pre->rchild=BT; if(BT->rchild==null)BT->rtag=1; if(BT->ltag==0)PreOrderThreat(BT->lchild); }//if(BT!=null)BiThrTreevoidInOrderThreat(BiThrTreeT){if if(T->lchild==null{T->ltag=1;T->lchild=pre;if(pre!=null&&pre->rtag==1)pre if(T->rchild==null)T->rtag=1; }voidInOrderThreat(BiThrTree{p=thrt->lchild;//ppthrtwhile(p->rtag==1&&p->rchild!=thrt){p=p->rchild;visit(*p);}//沿右线索}72.[题目分析]若使新插入的叶子结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左面的结点（设为p）处插入，使S成为结点p的左。则S的前驱是T，后继p.voidThrTreeInsert(BiThrTree//在中序线索二叉树T的右子树上插入结点S，使S成为T右子树中序遍历第一个{p=T- while(p->ltag==0)p=p- S->lchild=T;S->rchild=p;//STp->lchild=S;p->ltag=0;//将p的左指向S，并修改左标志为}//结束73．BiThrTreeInOrder(BiThrTreeT,ElemType//先 {while(p->ltag==0&&p-data!=x)p=p->lc;while(p->rtag==1&&p->rc!=T){p=p->rc;if(p->data==x)return(p);}p=p->rc;}{BiThrTree Txif(p->rtag==1)return(p- p1，prc继else{q=p->rc;while(q->ltag==0)q=q->lc;return(q);}否则，左（或左线索）指向其后序前驱。BiThrTreePostSucc(BiThrTreeT,pTpq{if(p->Rtag==0)q=p->Rchild;//若p有右，则右为其前elseq=p- return75．BiThrTreeInSucc(BiThrTreeT,p)//在对称序穿线树Tp p1，用其右指针指向后继else{q=p->rchild;while(q->ltag==0)q=q->lchild;}//preturn是f右子树中按中序遍历的第一个结点，若f有左，则其左是结点p在后序下的BiThrTreeInPostPre(BiThrTreetp{BiThrTreeif(p->rtag==0)q=p->rchild; //若p有右，则右是其后序前驱elseif(p->ltag==0)q=p->lchild;//若p无右而有左，左是其后elseif(p->lchild==null)q=null;//pelsep{while(p->ltag==1&&p->lchild!=null)p=p-if(p->ltag==0)q=p->lchild;//p结点的祖先的左是其后序前else