西北大學(xué)《數(shù)據(jù)結(jié)構(gòu)》典型例題(6-10章)

西北大學(xué)《數(shù)據(jù)結(jié)構(gòu)》典型例題（6-10章）西北大學(xué)《數(shù)據(jù)結(jié)構(gòu)》各章典型例題第六章樹與二叉樹6.27［問題］假設(shè)一棵二叉樹的先序序列為EBADCFH6IKJ和中序序列為ABCDEFGHIJK。請(qǐng)畫出該樹。］［解答6.29［問題］假設(shè)一棵二叉樹的層序序列為ABCDEFGHIJ和中序序列為DBGEHJACIF。請(qǐng)畫出該樹。［問題］試?yán)脳５幕静僮鲗懗鱿刃虮闅v二叉樹的非遞歸算法。［解答提示］改寫教材p.130-131算法6.2或6.3o將if(ivisit(p->data))returnERROR;提前。6.43［問題］編寫遞歸算法，將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換。StatusExchange-lr(Bitreebt){〃將bt所指二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換if(bt&&(bt->lchild||bt->rchild)){bt->Ichiid<->bt->rchi1d;Exchange-lr(bt->lchiId);Exchange-lr(bt->rchiId);returnOK;}//Exchange-Ir6.45［問題］編寫遞歸算法，對(duì)于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。［解答］StatusDel-subtree(Bitreebt){〃刪除bt所指二叉樹，并釋放相應(yīng)的空間if(bt){Del-subtree(bt->lchiId);Del-subtree(bt->rchiId);free(bt);}returnOK;}//Del-subtreeStatusSearch-del(Bitreebt,TelemTypex){〃在bt所指的二叉樹中，查找所有元素值為x的結(jié)點(diǎn)，并刪除以它為根的子樹if(bt){if(bt->data=x)Del-subtree(bt);else{Search-Del(bt->lchild,x);Search-Del(bt->rchild,x);returnOK;}//Search-Del第六章樹和二叉樹6.33intIs_DescendantC(intu,intv)〃在孩子存儲(chǔ)結(jié)構(gòu)上判斷u是否v的子孫，是則返回1,否則返回0{if(u==v)return1;elseiif(L[v])if(Is_Descendant(u,L[v]))return1;if(R[v])if(IsDescendant(u,R[v]))return1;〃這是個(gè)遞歸算法}return0;}//Is_Descendant_C6.34intIs_Descendant_P(intu,intv)〃在雙親存儲(chǔ)結(jié)構(gòu)上判斷u是否v的子孫，是則返回1,否則返回0(for(p=u;p!=v&&p;p=T[p]);if(p==v)return1;elsereturn0;}//Is_Descendant_P6.35這一題根本不需要寫什么算法,見書后注釋：兩個(gè)整數(shù)的值是相等的.6.36intBitree_Sim(BitreeBl,BitreeB2)//判斷兩棵樹是否相似的遞歸算法(if(!Bl&&!B2)return1;elseif(Bl&&B2&&Bitree_Sim(Bl->lchild,B2->lchiId)&&Bitree_Sim(Bl->rchiId,B2->rchild))return1;elsereturn0;}//Bitree_Sim6.37voidPreOrderNotRecurve(BitreeT)〃先序遍歷二叉樹的非遞歸算法{InitStack(S);Push(S,T);〃根指針進(jìn)棧while(!StackEmpty(S)){while(Gettop(S,p)&&p)(visit(p->data);push(S,p->lchild);)〃向左走到盡頭pop(S,p);if(IStackEmpty(S))pop(S,p);push(S,p->rchild);〃向右一步}}//while}//PreOrder_NotRecurve6.38typedefstruct{BTNode*ptr;enum(0,1,2}mark;}PMType;〃有mark域的結(jié)點(diǎn)指針類型voidPostOrder_Stack(BiTreeT)〃后續(xù)遍歷二叉樹的非遞歸算法，用棧{PMTypea;InitStack(S);//S的元素為PMType類型Push(S,{T,0});〃根結(jié)點(diǎn)入棧whi1e(!StackEmpty(S)){Pop(S,a);switch(a.mark)!case0:Push(a.ptr,1);//修改mark域if(a.ptr->lchild)Push({a.ptr->lchild,0});//訪問左子樹break;Push(a.ptr,2);//修改mark域if(a.ptr->rchild)Push({a.ptr->rchi1d,0});〃訪問右子樹break;visit(a.ptr);〃訪問結(jié)點(diǎn)，返回}}//while}//PostOrder_Stack分析:為了區(qū)分兩次過棧的不同處理方式,在堆棧中增加一個(gè)mark域,mark=0表示剛剛訪問此結(jié)點(diǎn),mark=l表示左子樹處理結(jié)束返回,mark=2表示右子樹處理結(jié)束返回.每次根據(jù)棧頂元素的mark域值決定做何種動(dòng)作.6.39typedefstruct{intdata;EBTNode*IchiId;EBTNode*rchild;EBTNode*parent;enum{0,1,2}mark;}EBTNode,EBitree;〃有mark域和雙親指針域的二叉樹結(jié)點(diǎn)類型voidPostOrder_NotRecurve(EBitreeT)〃后序遍歷二叉樹的非遞歸算法，不用棧{P二T;while(p)switch(p->mark)case0:p->mark=l;if(p->lchild)p=p->lchild;〃訪問左子樹break;p->markz:2;if(p->rchild)p=p->rchild;〃訪問右子樹break;visit(p);p->mark=0;〃恢復(fù)mark值p=p->parent;〃返回雙親結(jié)點(diǎn)}}//PostOrder_NotRecurve分析:本題思路與上一題完全相同,只不過結(jié)點(diǎn)的mark值是儲(chǔ)存在結(jié)點(diǎn)中的,而不是暫存在堆棧中,所以訪問完畢后要將mark域恢復(fù)為0,以備下一次遍歷.6.40typedefstruct{intdata;PBTNode*lchild;PBTNode*rchiId;PBTNode*parent;}PBTNode,PBitree;〃有雙親指針域的二叉樹結(jié)點(diǎn)類型voidInorder_NotRecurve(PBitreeT)〃不設(shè)棧非遞歸遍歷有雙親指針的二叉樹{P=T;while(p->lchild)p=p->lchild;//向左走到盡頭while(p)(visit(p);if(p->rchild)〃尋找中序后繼:當(dāng)有右子樹時(shí)!p=p->rchiId;while(p->lchild)p=p->lchild;〃后繼就是在右子樹中向左走到盡頭}elseif(p->parent->lchild==p)p=p->parent;〃當(dāng)自己是雙親的左孩子時(shí)后繼就是雙親else{p=p->parent;while(p->parent&&p->parent->rchild=p)p=p->parent;p=p->parent;}〃當(dāng)自己是雙親的右孩子時(shí)后繼就是向上返回直到遇到自己是在其左子樹中的祖先}//while}//Inorder_NotRecurve6.41intc,k；〃這里把k和計(jì)數(shù)器c作為全局變量處理voidGet_PreSeq(BitreeT)〃求先序序列為k的結(jié)點(diǎn)的值if(T)(C++;〃每訪問一個(gè)子樹的根都會(huì)使前序序號(hào)計(jì)數(shù)器加1if(c=k)(printf(''Valueis%d\nz，,T->data);exit(1);}else(Get_PreSeq(T->lchiId);〃在左子樹中查找Get_PreSeq(T->rchiId);〃在右子樹中查找}}//if}//Get_PreSeqmain(){scanf&k);c=0;〃在主函數(shù)中調(diào)用前，要給計(jì)數(shù)器賦初值0Get_PreSeq(T,k);}//main6.42intLeafCount_BiTree(BitreeT)〃求二叉樹中葉子結(jié)點(diǎn)的數(shù)目(if(!T)return0;//空樹沒有葉子elseif(!T->lchild&&!T->rchiId)return1;〃葉子結(jié)點(diǎn)elsereturnLeaf_Count(T->lchild)+LeafCount(T->rchild);〃左子樹的葉子數(shù)加上右子樹的葉子數(shù)}//LeafCount_BiTree6.43voidBitreeRevolute(BitreeT)〃交換所有結(jié)點(diǎn)的左右子樹T->lchild<->T->rchild;〃交換左右子樹if(T->lchild)Bitree_Revolute(T->lchild);if(T->rchild)Bitree_Revolute(T-〉rchild);〃左右子樹再分別交換各自的左右子樹}//Bitree_Revolute6.44intGet_Sub_Depth(BitreeT,intx)〃求二叉樹中以值為x的結(jié)點(diǎn)為根的子樹深度(if(T->data==x)printf("%d\n",Get_Depth(T));〃找到了值為x的結(jié)點(diǎn)，求其深度exit1;else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_SubDepth(T->rchiId,x);〃在左右子樹中繼續(xù)尋找}}//Get_Sub_DepthintGet_Depth(BitreeT)〃求子樹深度的遞歸算法(if(!T)return0;else!m=GetDepth(T->1chi1d);n=Get_Depth(T->rchi1d);return(m>n?m:n)+l;}}//Get_Depth6.45voidDel_Sub_x(BitreeT,intx)〃刪除所有以元素x為根的子樹(if(T->data==x)Del_Sub(T);〃刪除該子樹elseiif(T->lchild)Del_Sub_x(T->lchild,x);if(T->rchild)Del_Sub_x(T->rchild,x);〃在左右子樹中繼續(xù)查找}//else}//Del_SubxvoidDel_Sub(BitreeT)〃刪除子樹Tif(T->lchild)Del_Sub(T->lchild);if(T->rchild)Del_Sub(T->rchild);free(T);}//Del_Sub6.46voidBitree_Copy_NotRecurve(BitreeT,Bitree&U)〃非遞歸復(fù)制二叉樹{InitStack(Sl);InitStack(S2);push(Sl,T);〃根指針進(jìn)棧U=(BTNode*)malloc(sizeof(BTNode));U->data=T->data;q=U;push(S2,U);while(!StackEmpty(S)){while(Gettop(SI,p)&&p)(q->lchild=(BTNode*)malloc(sizeof(BTNode));q=q->lchiId;q->data=p->data;push(SI,p->lchild);push(S2,q);)〃向左走到盡頭pop(SI,p);pop(S2,q);if(JStackEmpty(SI))pop(SI,p);pop(S2,q);q->rchild=(BTNode*)malloc(sizeof(BTNode));q=q->rchiId;q->data=p->data;push(SI,p->rchild);〃向右一步push(S2,q);}}//while}//BiTree_Copy_NotRecurve分析:本題的算法系從6.37改寫而來.6.47voidLayerOrder(BitreeT)〃層序遍歷二叉樹(InitQueue(Q);〃建立工作隊(duì)列EnQueue(Q,T);whi1e(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}//LayerOrder6.48intfound=FALSE;Bitree*Find_Near_Ancient(BitreeT,Bitreep,Bitreeq)〃求二叉樹T中結(jié)點(diǎn)p和q的最近共同祖先!Bitreepathp[100],pathq[100]〃設(shè)立兩個(gè)輔助數(shù)組暫存從根到p,q的路徑Findpath(T,p,pathp,0);found:FALSE;Findpath(T,q,pathq,0);〃求從根到p,q的路徑放在pathp和pathq中for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);〃查找兩條路徑上最后一個(gè)相同結(jié)點(diǎn)returnpathp[-i];}//Find_Near_AncientvoidFindpath(BitreeT,Bitreep,Bitreepath[],inti)〃求從T到p路徑的遞歸算法(if(T==p)(found=TRUE;return;〃找到}path[i]=T;〃當(dāng)前結(jié)點(diǎn)存入路徑if(T->lchild)Findpath(T->lchiId,p,path,i+1);〃在左子樹中繼續(xù)尋找if(T->rchild&&!found)Findpath(T->rchiId,p,path,i+1);〃在右子樹中繼續(xù)尋找if([found)path[i]=NULL;〃回溯}//Findpath6.49intIsFull_Bitree(BitreeT)〃判斷二叉樹是否完全二叉樹，是則返回1,否則返回0(InitQueue(Q);flag=O;EnQueue(Q,T);〃建立工作隊(duì)列while(!QueueEmpty(Q))!DeQueue(Q,p);if(!p)flag=l;elseif(flag)return0;else(EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);〃不管孩子是否為空,都入隊(duì)列}}//whilereturn1;}//IsFull_Bitree分析:該問題可以通過層序遍歷的方法來解決.與6.47相比，作了一個(gè)修改,不管當(dāng)前結(jié)點(diǎn)是否有左右孩子,都入隊(duì)列.這樣當(dāng)樹為完全二叉樹時(shí),遍歷時(shí)得到是一個(gè)連續(xù)的不包含空指針的序列.反之,則序列中會(huì)含有空指針.6.50StatusCreateBitree_Triplet(Bitree&T)〃輸入三元組建立二叉樹｛if(getcharO!='r)returnERROR;T=(BTNode*)malloc(sizeof(BTNode));p=T;p->data=getchar();getcharO;〃濾去多余字符InitQueue(Q);EnQueue(Q,T);while((parent=getchar())!='*&&(child=getchar())&&(side=getchar())){while(QueueHead(Q)!=parent&&!QueueEmpty(Q))DeQueue(Q,e);if(QueueEmpty(Q))returnERROR;〃未按層序輸入p=QueueHead(Q);q=(BTNode*)malloc(sizeof(BTNode));if(side=二'L')p->lchild=q;elseif(side=二'R')p->rchild=q;elsereturnERROR;〃格式不正確q->data=chiId;EnQueue(Q,q);}returnOK;}//CreateBitree_Triplet6.51StatusPrintExpression(BitreeT)〃按標(biāo)準(zhǔn)形式輸出以二叉樹存儲(chǔ)的表達(dá)式{if(T->data是字母)printf("%c”,T->data);elseif(T->data是操作符)if(!T->lchild||!T->rchild)returnERROR;〃格式錯(cuò)誤if(T->lchild->data是操作符&&T->lchild->data優(yōu)先級(jí)低于T->data){printf("(");if(!Print_Expression(T->1chi1d))returnERROR;printf(")");)〃注意在什么情況下要加括號(hào)elseif(!Print_Expression(T->lchiId))returnERROR;if(T->rchi1d->data是操作符&&T->rchild-〉data優(yōu)先級(jí)低于T->data){printf("(");if(!PrintExpression(T->rchild))returnERROR;printf(")”);}elseif(!PrintExpression(T->rchiId))returnERROR;)elsereturnERROR;〃非法字符returnOK;}//Print_Expression6.52typedefstruct{BTNodenode;intlayer;}BTNRecord;〃包含結(jié)點(diǎn)所在層次的記錄類型intFanMao(BitreeT)〃求一棵二叉樹的“繁茂度”intcountd;〃count數(shù)組存放每一層的結(jié)點(diǎn)數(shù)InitQueue(Q);〃Q的元素為BTNRecord類型EnQueue(Q,{T,0});while(!QueueEmpty(Q))(DeQueue(Q,r);count[r.layer]++;if(r.node->lchiId)EnQueue(Q,{r.node->lchild,r.layer+1));if(r.node->rchild)EnQueue(Q,{r.node->rchild,r.layer+1});}〃利用層序遍歷來統(tǒng)計(jì)各層的結(jié)點(diǎn)數(shù)h=r.layer;〃最后一個(gè)隊(duì)列元素所在層就是樹的高度for(maxn=count[0],i=l;count[i];i++)if(count[i]>maxn)maxn=count[i];〃求層最大結(jié)點(diǎn)數(shù)returnh*maxn;}//FanMao分析:如果不允許使用輔助數(shù)組,就必須在遍歷的同時(shí)求出層最大結(jié)點(diǎn)數(shù),形式上會(huì)復(fù)雜一些，你能寫出來嗎？6.53intmaxh;StatusPrintpath_MaxdepthSl(BitreeT)〃求深度等于樹高度減?的最靠左的結(jié)點(diǎn){Bitreepathd;maxh=Get_Depth(T);//Get_Depth函數(shù)見6.44if(maxh<2)returnERROR;〃無符合條件結(jié)點(diǎn)Find_h(T,1);returnOK;}//PrintpathMaxdepthS1voidFind_h(BitreeT,inth)〃尋找深度為maxhT的結(jié)點(diǎn)Ipath[h]=T;if(h==maxh-l)[for(i=l;path[i];i++)printf("%c”,path[i]->data)：exit;〃打印輸出路徑)else(if(T->lchild)Find_h(T->lchild,h+1);if(T->rchild)Find_h(T->rchild,h+1);)path[h]=NULL;〃回溯}//Find_h6.54StatusCreateBitreeSqList(Bitree&T,SqListsa)//根據(jù)順序存儲(chǔ)結(jié)構(gòu)建匯二叉鏈表Bitreeptr[sa.last+1];〃該數(shù)組儲(chǔ)存與sa中各結(jié)點(diǎn)對(duì)應(yīng)的樹指針if(!sa.last)T=NULL;〃空樹return;}ptr[1]=(BTNode*)malloc(sizeof(BTNode));ptr[1]->data=sa.elem[1];〃建立樹根T=ptr[1];for(i=2;i<=sa.last;i++)!if(!sa.elem[i])returnERROR;//順序錯(cuò)誤ptr[i]=(BTNode*)malloc(sizeof(BTNode));ptr[i]->data=sa.elem[i];j=i/2;〃找到結(jié)點(diǎn)i的雙親jif(i-j*2)ptr[j]->rchild=ptr[i];〃i是j的右孩子elseptr[j]->lchild=ptr[i];〃i是j的左孩子}returnOK;}//CreateBitree_SqList6.55intDescNum(BitreeT)〃求樹結(jié)點(diǎn)T的子孫總數(shù)填入DescNum域中，并返回該數(shù){if(!T)returnT;elsed=(DescNum(T->lchiId)+DescNum(T->rchiId)+2);〃計(jì)算公式T->DescNum二d;returnd;}//DescNum分析:該算法時(shí)間復(fù)雜度為0(n),n為樹結(jié)點(diǎn)總數(shù).注意:為了能用一個(gè)統(tǒng)一的公式計(jì)算子孫數(shù)目，所以當(dāng)T為空指針時(shí),要返回T而不是0.6.56BitreePreOrder_Next(Bitreep)〃在先序后繼線索二叉樹中查找結(jié)點(diǎn)p的先序后繼，并返回指針(if(p->lchild)returnp->lchild;elsereturnp->rchild;}//PreOrder_Next分析:總覺得不會(huì)這么簡(jiǎn)單.是不是哪兒理解錯(cuò)了？6.57BitreePostOrder^Next(Bitreep)〃在后序后繼線索二叉樹中查找結(jié)點(diǎn)p的后序后繼，并返回指針I(yè)if(p->rtag)returnp->rchild;//p有后繼線索elseif(!p->parent)returnNULL;〃p是根結(jié)點(diǎn)elseif(p==p->parent->rchiId)returnp->parent;〃p是右孩子elseif(p=p->parent->lchild&&p->parent->tag)returnp->parent;〃p是左孩子且雙親沒有右孩子else〃p是左孩子且雙親有右孩子(q=p->parent->rchild;while(!q->ltag||!q->rtag)if(!q->ltag)q=q->lchiId;elseq=q->rchild;)〃從p的雙親的右孩子向下走到底returnq;}//else}//PostOrder_Next6.58StatusInsert_BiThrTree(BiThrTree&T,BiThrTree&p,BiThrTree&x)〃在中序線索二叉樹T的結(jié)點(diǎn)p下插入子樹x(if(!p->ltag&a!p->rtag)returnINFEASIBLE;〃無法插入if(p->ltag)〃x作為p的左子樹is=p->lchild;〃s為p的前驅(qū)p->ltag=Link;p->lchild=x;q二x;while(q->lchild)q=q->lchild;q->lchild=s;〃找到子樹中的最左結(jié)點(diǎn)，并修改其前驅(qū)指向sq=x;while(q->rchild)q=q->rchild;q->rchild=p;〃找到子樹中的最右結(jié)點(diǎn),并修改其前驅(qū)指向pelse〃x作為p的右子樹s=p->rchild;〃s為p的后繼p->rtag=Link;p->rchild=x;q=x;while(q->rchild)q=q->rchild;q->rchild二s;〃找到子樹中的最右結(jié)點(diǎn)，并修改其前驅(qū)指向sq=x;while(q->lchild)q=q->lchild;q->lchild=p;〃找到子樹中的最左結(jié)點(diǎn),并修改其前驅(qū)指向p}returnOK;}//Insert_BiThrTree6.59voidPrint_CSTree(CSTreeT)〃輸出孩子兄弟鏈表表示的樹T的各邊{for(chiId=T->firstchiId;chiId;chiId=chiId->nextsib)(printf("(%c,%c),，z,T->data,child->data);Print_CSTree(child);}}//PrintCSTree6.60intLeafCount_CSTree(CSTreeT)//求孩子兄弟鏈表表示的樹T的葉子數(shù)目{if(!T->firstchiId)return1;〃葉子結(jié)點(diǎn)elsecount=0;for(child=T->firstchild;child;child=child->nextsib)count+=LeafCount_CSTree(child);returncount;〃各子樹的葉子數(shù)之和)}//LeafCount_CSTree6.61intGetDegree_CSTree(CSTreeT)〃求孩子兄弟鏈表表示的樹T的度{if(!T->firstchiId)return0;//空樹else(degree=0;for(p=T->firstchiId;p;p=p->nextsib)degree++;〃本結(jié)點(diǎn)的度for(p=T->firstchiId;p;p=p->nextsib){d=GetDegree_CSTree(p);if(d>degree)degree=d;〃孩子結(jié)點(diǎn)的度的最大值}returndegree;}//else}//GetDegree_CSTree6.62intGetDepth_CSTree(CSTreeT)〃求孩子兄弟鏈表表示的樹T的深度{if(!T)return0;〃空樹else(for(maxd=0,p=T->firstchild;p;p=p->nextsib)if((d=GetDepthCSTree(p))>maxd)maxd=d;〃子樹的最大深度returnmaxd+1;}}//GetDepth_CSTree6.63intGetDepth_CTree(CTreeA)〃求孩子鏈表表示的樹A的深度ireturnSubDepth(A.r);}//GetDepth_CTreeintSubDepth(intT)〃求子樹T的深度(if(!A.nodes[T].firstchild)return1;for(sd=l,p=A?nodes[T].firstchild;p;p=p->next)if((d=SubDepth(p->chi1d))>sd)sd=d;returnsd+1;}//SubDepth6.64intGetDepth_PTree(PTreeT)〃求雙親表表示的樹T的深度maxdep=0;for(i=0;i<T.n;i++)dep=0;for(j=i;j>=0;j=T.nodes[j].parent)dep++;〃求每一個(gè)結(jié)點(diǎn)的深度if(dep>maxdep)maxdep=dep;}returnmaxdep;}//GetDepthPTree6.65charPred,Ind;〃假設(shè)前序序列和中序序列已經(jīng)分別儲(chǔ)存在數(shù)組Pre和In中BitreeBuild_Sub(intPre_Start,intPre_End,intIn_Start,intIn_End)〃由子樹的前序和中序序前建立其二叉鋸表{sroot=(BTNode*)malloc(sizeof(BTNode));〃建根sroot->data=Pre[Pre_Start];for(i=In_Start;In[i]!=sroot->data;i++);〃在中序序列中查找子樹根leftlen=i-In_Start;rightlen=InEnd-i;〃計(jì)算左右子樹的大小if(leftlen){lroot=Build_Sub(Pre_Start+l,Pre_Start+leftlen,InStart,In_Start+leftlen-l);sroot->lchild=lroot;)〃建左子樹，注意參數(shù)表的計(jì)算if(rightlen)rroot=BuildSub(PreEnd-rightlen+1,Pre_End,In_End-rightlen+l,InEnd);sroot->rchild=rroot;}〃建右子樹，注意參數(shù)表的計(jì)算returnsroot;〃返回子樹根}//Build_Submain()(Build_Sub(l,n,1,n);〃初始調(diào)用參數(shù),n為樹結(jié)點(diǎn)總數(shù))分析:本算法利用了這樣一個(gè)性質(zhì),即一棵子樹在前序和中序序列中所占的位置總是連續(xù)的.因此,就可以用起始下標(biāo)和終止下標(biāo)來確定一棵子樹.Pre_Start,Pre_End,In_Start和In_End分別指示子樹在前序子序列里的起始下標(biāo)，終止下標(biāo),和在中序字序列里而起始和終定下標(biāo).6.66typedefstruct{CSNode*ptr;CSNode*lastchild;}NodeMsg;〃結(jié)點(diǎn)的指針和其最后一個(gè)孩子的指針StatusBulid_CSTree_PTree(PTreeT)〃由樹T的雙親表構(gòu)造其孩子兄弟鏈表{NodeMsgTreed;for(i=0;i<T.n;i++)Tree[i].ptr=(CSNode*)malloc(sizeof(CSNode));Tree[i].ptr->data=T.node[i].data;〃建結(jié)點(diǎn)if(T.nodes[i].parent>=0)〃不是樹根{j=T.nodes[i].parent;〃本算法要求雙親表必須是按層序存儲(chǔ)if(!(Tree[j].lastchild))〃雙親當(dāng)前還沒有孩子Tree[j].ptr->firstchild=Tree[i].ptr;〃成為雙親的第一個(gè)孩子else〃雙親已經(jīng)有了孩子TreeEj].lastchild->nextsib=Tree[i].ptr;〃成為雙親最后一個(gè)孩子的下一個(gè)兄弟Tree[j].lastchild=Tree[i].ptr;〃成為雙親的最后一個(gè)孩子}//if}//for}//Buiid_CSTree_PTree6.67typedefstruct{chardata;CSNode*ptr;CSNode*lastchild;}Nodeinfo;〃結(jié)點(diǎn)數(shù)據(jù)，結(jié)點(diǎn)指針和最后一個(gè)孩子的指針StatusCreateCSTreeDuplet(CSTree&T)〃輸入二元組建立樹的孩子兄弟鏈表{NodeinfoTreed;n=l;k=0;if(getchar()!=，f)returnERROR;〃未按格式輸入if((c=getchar())==")T=NULL;〃空樹Tree[0].ptr=(CSNode*)malloc(sizeof(CSNode));Tree[0].data=c;Tree[0].ptr->data=c;whi1e((p=getchar())!=,"，&&(c=getchar())!=,9)Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode));Tree[n].data=c;Tree[n].ptr->data=c;for(k=0;Tree[k].data!=p;k++);〃查找當(dāng)前邊的雙親結(jié)點(diǎn)if(Tree[k].data!=p)returnERROR;〃未找到:未按層序輸入r=Tree[k].ptr;if(!r->firstchild)r->firstchild=Tree[n].ptr;elseTree[k].lastchild->nextsib=Tree[n].ptr;Treefk].lastchild=Tree[n].ptr;〃這?段含義同上題n++;}//whilereturnOK;}//CreateCSTree_Duplet6.68StatusCreateCSTree_Degree(charnode[],intdegree[])〃由結(jié)點(diǎn)的層序序列和各結(jié)點(diǎn)的度構(gòu)造樹的孩子兄弟鏈表{CSNode*ptrd;〃樹結(jié)點(diǎn)指針的輔助存儲(chǔ)ptr[0]=(CSNode*)ma11oc(sizeof(CSNode));i=0;k=l;〃i為當(dāng)前結(jié)點(diǎn)序號(hào),k為當(dāng)前孩子的序號(hào)while(node[i])ptr[i]->dataz:node[i];d二degree[i];if(d)(ptr[k++]=(CSNode*)malloc(sizeof(CSNode));//k為當(dāng)前孩子的序號(hào)ptr[i]->firstchild=ptr[k];//建立i與第一個(gè)孩子k之間的聯(lián)系for(j=2;j<=d;j++)(ptr[k++]=(CSNode*)malloc(sizeof(CSNode));ptr[kT]->nextsib二ptr[k];〃當(dāng)結(jié)點(diǎn)的度大于1時(shí),為其孩子建立兄弟鏈表}//for}//ifi++；}//while}//CreateCSTree_Degree69voidPrint_BiTree(BiTreeT,inti)〃按樹狀打印輸出二叉樹的元素，i表示結(jié)點(diǎn)所在層次,初次調(diào)用時(shí)i=0iif(T->rchild)PrintBiTree(T->rchiId,i+1);for(j=l;j<=i;j++)printf("〃)；〃打印i個(gè)空格以表示出層次printf(，z%c\n，z,T->data);〃打印T元素，換行if(T->lchild)Print_BiTree(T->rchiId,i+1);}//Print_BiTree分析:該遞歸算法實(shí)際上是帶層次信息的中序遍歷，只不過按照題目要求，順序?yàn)橄扔液笞?6.70StatusCreateBiTreeGList(BiTree&T)〃由廣義表形式的輸入建立二叉鏈表{c=getchar();if(c==，)T=NULL;〃空子樹else(T=(CSNode*)malloc(sizeof(CSNode));T->data=c;if(getcharO!=，C)returnERROR;if([CreateBiTreeGList(pl))returnERROR;T->lchild=pl;if(getcharO!=，,*)returnERROR;if(!CreateBiTreeGList(pr))returnERROR;T->rchild=pr;if(getcharO!=，)J)returnERROR;〃這些語句是為了保證輸入符合A(B,C)的格式}returnOK;}//CreateBiTree_GList6.71voidPrint_CSTree(CSTreeT,inti)〃按凹入表形式打印輸出樹的元素，i表示結(jié)點(diǎn)所在層次，初次調(diào)用時(shí)i=0for(j=l;j<=i;j++)printff〃)；//留出i個(gè)空格以表現(xiàn)出層次printf("%c\n",T->data);//打印元素,換行for(p=T->firstchild;p;p=p->nextsib)Print_CSTree(p,i+1);〃打印子樹}//Print_CSTree6.72voidPrint_CTree(inte,inti)〃按凹入表形式打印輸出樹的元素，i表示結(jié)點(diǎn)所在層次(for(j=l;j<=i;j++)printf("〃)；〃留出i個(gè)空格以表現(xiàn)出層次printf(*%c\n*,T.nodes[e].data);〃打印元素,換行for(p=T.nodes[e].firstchiId;p;p=p->next)Print_CSTree(p->child,i+1);//打印子樹}//Print_CSTreemain(){Print_CTree(T.r,0);〃初次調(diào)用時(shí)i=0}//main6.73charc;〃全局變量,指示當(dāng)前字符StatusCreateCSTree_GList(CSTree&T)〃由廣義表形式的輸入建立孩子兄弟鏈表c=getchar();T=(CSNode*)malloc(sizeof(CSNode));T->data=c;if((c=getchar())==,C)〃非葉結(jié)點(diǎn)(if(!CreateCSTree_GList(fc))returnERROR;//建第一個(gè)孩子T->firstchild=fc;for(p=fc;c==，,>;p->nextsib=nc,p=nc)〃建兄弟鏈if(!CreateCSTreeGList(nc))returnERROR;p->nextsib=NULL;if((c=getchar())!=’)')returnERROR;〃括號(hào)不配對(duì)}elseT->firtchild=NULL;〃葉子結(jié)點(diǎn)returnOK;}//CreateBiTree_GList分析:書后給出了兩個(gè)間接遞歸的算法,事實(shí)上合成一個(gè)算法在形式上可能更好一些.本算法另一個(gè)改進(jìn)之處在于加入了廣義表格式是否合法的判斷.6.74voidPrintGlist_CSTree(CSTreeT)〃按廣義表形式輸出孩子兄弟鏈表表示的樹{printf(“枇"，T->data);if(T->firstchild)〃非葉結(jié)點(diǎn)(printf("(");for(p=T->firstchild;p;p=p->nextsib)PrintGlist_CSTree(p);if(p->nextsib)printf 最后?個(gè)孩子后面不需要加逗號(hào))printf(*)*)；}//if}//PrintGlist_CSTree6.75charc;intpos=0;〃pos是全局變量,指示已經(jīng)分配到了哪個(gè)結(jié)點(diǎn)StatusCreateCTree_GList(CTree&T,int&i)〃由廣義表形式的輸入建立孩子鏈表{c=getchar();T.nodes[pos].data=c;i=pos++;〃i是局部變量,指示當(dāng)前正在處理的子樹根if((c=getchar())==,(*)〃非葉結(jié)點(diǎn)(CreateCTree_GList();p=(CTBox*)maHoc(sizeof(CTBox));T.nodes[i].firstchild=p;p->child=pos;〃建立孩子鏈的頭for(;c=,*;p=p->next)〃建立孩子鏈iCreateCTree_GList(T,j);〃用j返回分配得到的子樹根位置p->child=j;p->next=(CTBox*)malloc(sizeof(CTBox));p->next=NULL;if((c二getchar())!=')')returnERROR;〃括號(hào)不配對(duì)}//ifelseT.nodes[i].firtchild=NULL;〃葉子結(jié)點(diǎn)returnOK;}//CreateBiTreeGList分析:該算法中,pos變量起著〃分配”結(jié)點(diǎn)在表中的位置的作用，是按先序序列從上向下分配,因此樹根T.r一定等于0,而最終的pos值就是結(jié)點(diǎn)數(shù)T.n.76voidPrintGList_CTree(CTreeT,inti)〃按廣義表形式輸出孩子鏈表表示的樹{printfT.nodes[i].data);if(T.nodes[i].firstchild)〃非葉結(jié)點(diǎn)(printf("(");for(p=T->firstchild;p;p=p->nextsib){PrintGlist_CSTree(T,p->child);if(p->nextsib)printf 〃最后一個(gè)孩子后面不需要加逗號(hào)}printf(")");}//if"/PrintGlistCTree第七章圖14StatusBuild_AdjList(ALGraph&G)〃輸入有向圖的頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)信息和邊的信息建立鄰接表InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;〃頂點(diǎn)數(shù)不能為負(fù)G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;〃邊數(shù)不能為負(fù)G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();〃輸入各頂點(diǎn)的符號(hào)for(m=1;m<=a;m++)(t=getchar();h=getchar();//t為弧尾,h為弧頭if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;〃頂點(diǎn)未找到p二(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices,[i].firstarc)G.vertices[i].firstarc=p;else(for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//BuildAdjList7.15〃本題中的圖G均為有向無權(quán)圖，其余情況容易由此寫出StatusInsert_Vex(MGraph&G,charv)〃在鄰接矩陣表示的圖G上插入頂點(diǎn)v{if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G?vexnum]=v;returnOK;}//Insert_VexStatusInsertArc(MGraph&G,charv,charw)〃在鄰接矩陣表示的圖G上插入邊(v,w)(if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(i==j)returnERROR;if(!G.arcs[i][j].adj)(G.arcs[i][j],adj=l;G.arcnum++;}returnOK;}//Insert_ArcStatusDelete_Vex(MGraph&G,charv)〃在鄰接矩陣表示的圖G上刪除頂點(diǎn)v{n=G.vexnum;if((m=LocateVex(G,v))<0)returnERROR;G.vexs[m]<->G.vexs[n];〃將待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)for(i=0;i<n;i++)(G.arcs[i][m]=G.arcs[i][n];G.arcs[m][i]=G.arcs[n][i];〃將邊的關(guān)系隨之交換}G.arcs[m][m].adj=0;G.vexnum--；returnOK;}//Delete_Vex分析:如果不把待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)的話,算法將會(huì)比較復(fù)雜,而伴隨著大量元素的移動(dòng)，時(shí)間復(fù)雜度也會(huì)大大增加.StatusDeleteArc(MGraph&G,charv,charw)〃在鄰接矩陣表示的圖G上刪除邊(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj)(G.arcs[i][j].adj=0;G.arcnum——；returnOK;}//Delete_Arc7.16〃為節(jié)省篇幅,本題只給出Insert_Arc算法.其余算法請(qǐng)自行寫出.StatusInsert_Arc(ALGraph&G,charv,charw)〃在鄰接表表示的圖G上插入邊(v,w)if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;elseifor(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)if(q->adjvex==j)returnERROR;〃邊已經(jīng)存在q->nextarc=p;}G.arcnum++;returnOK;}//Insert_Arc17〃為節(jié)省篇幅〈spanlang=ENTJSstyle='mso-bidi-font-size:10.Opt;font-family:"TimesNewRom第八章查找9.1(I)無序表：順序查找不成功時(shí)，查找長(zhǎng)度為n+1；成功時(shí)，平均查找長(zhǎng)度為1/(n+1)*(1+2+—+(n+1))=(n+2)/2；兩者不相同。(2)表中只有一個(gè)關(guān)鍵字等于給定值k的記錄，無序表、有序表：順序查找成功時(shí),平均查找長(zhǎng)度均為l/(n)*(l+2+…+n)=(n+D/2；兩者相同。(3)表中只有m個(gè)關(guān)鍵字等于給定值k的記錄，無序表：ASL=n+l；有序表：ASL=(n+1)/2+m；兩者不相同。9.35234ASL=1/1O(1+2*2+4*3+3*4)=2.99.1167899.14刪除50后刪除68后<2030^30502050302267413053461301ASL=(4*l+2*2+3+6)/8=17/89.25intSearch-Seq(SSTableST,KeyTypekey){〃在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素，ST按關(guān)鍵字自大至小有序,〃若找到，則函數(shù)值為該元素在表中的位置，否則為0ST.elem[ST.length+1].key=key;for(i=l;ST.elem[i].key>key;++i);if(ST.elem[i].key=key)&&(i<=ST.length)returnielsereturn0;}//Search-Seq9.31TelemTypeMaxv(BitreeT){〃返回二叉排序樹T中所有結(jié)點(diǎn)的最大值for(p=T;p->rchild;p=p->rchild);returnp->data;}//MaxvTelemTypeMinv(BitreeT){〃返回二叉排序樹T中所有結(jié)點(diǎn)的最小值for(p=T;p->lchild;p=p->lchild);returnp->data;}//MinvStatusIsBST(BitreeT){〃判別T是否為二叉排序樹if(!T)returnOK;elseif((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)<T->data)))&&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))returnOKelsereturnERROR;}//IsBST9.33StatusOutputGEx(BitreeT,TelemTypex){〃從大到小輸出給定二叉排序樹T中所有值不小于x的數(shù)據(jù)元素if(T){if(OutputGEx(T->rchiId,x))if(T->data>=x){print(T->data);if(OutputGEx(T->lchiId,x))returnOK;}elsereturnOK;}elsereturnOK;}//OutputGEx第九章查找9.25intSearch_Sq(SSTableST,intkey)〃在有序表上順序查找的算法，監(jiān)視哨設(shè)在高下標(biāo)端{(lán)ST.elem[ST.length+1].key=key;for(i=l;ST.elem[i].key>key;i++);if(i>ST.length||ST.elem[i].key<key)returnERROR;returni;}//Search_Sq分析:本算法查找成功情況下的平均查找長(zhǎng)度為ST.length/2,不成功情況下為ST.length.9.26intSearchBin_Digui(SSTableST,intkey,intlow,inthigh)〃折半查找的遞歸算法{if(low>high)return0;〃查找不到時(shí)返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Digui(ST,key,low,mid-1);elsereturnSearchBinDigui(ST,key,mid+1,high);)}//Search_Bin_Digui9.27intLocate_Bin(SSTableST,intkey)〃折半查找,返回小于或等于待查元素的最后一個(gè)結(jié)點(diǎn)號(hào){int*r;r=ST.elem;if(key<r.key)return0;elseif(key>=r[ST.length],key)returnST.length;low=l;high=ST.length;while(low<=high)mid=(low+high)/2;if(key>=r[mid].key&&key<r[mid+1].key)〃查找結(jié)束的條件returnmid;elseif(key<r[mid].key)high=mid;elselow=mid;)〃本算法不存在查找失敗的情況,不需要return0;}//Locate_Bin9.28typedefstruct{intmaxkey;intfirstloc;}Index;typedefstruct{int*elem;intlength;Indexidx[MAXBLOCK];〃每塊起始位置和最大元素，其中idx[0]不利用，其內(nèi)容初始化為{0,0}以利于折半查找intblknum;〃塊的數(shù)目}IdxSqList;〃索引順序表類型intSearchIdxSeq(IdxSqListL,intkey)〃分塊查找，用折半查找法確定記錄所在塊,塊內(nèi)采用順序去找法{if(key>L.idx[L.blknum].maxkey)returnERROR;//超過最大元素low=l;high=L.blknum;found=0;while(low<=high&&!found)〃折半查找記錄所在塊號(hào)mid{mid=(low+high)/2;if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1],maxkey)found=l;elseif(key>L.idx[mid],maxkey)low=mid+l;elsehigh=mid-1;}i=L.idx[mid],firstloc;〃塊的下界j=i+blksize-l;〃塊的上界temp=L.elem[i-l];〃保存相鄰元素L.elem[i-l]=key;//設(shè)置監(jiān)視哨for(k=j;L.elem[k]!=key;k--);〃順序查找L.elem[i-l]=temp;〃恢復(fù)元素if(k<i)returnERROR;〃未找到returnk;}//Search_IdxSeq分析:在塊內(nèi)進(jìn)行順序查找時(shí),如果需要設(shè)置監(jiān)視哨，則必須先保存相鄰塊的相鄰元素，以免數(shù)據(jù)丟失.9.29typedefstruct{LNode*h;//h指向最小元素LNode*t;〃t指向上次查找的結(jié)點(diǎn)}CSList;LNode*Search_CSList(CSList&L,intkey)〃在有序單循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)上的查找算法,假定每次查找都成功{if(L.t->data==key)returnL.t;elseif(L.t->data>key)for(p=L.h,i=l;p->data!=key;p=p->next,i++);elsefor(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);L.t=p;//更新t指針returnp;}//Search_CSList分析：由于題目中假定每次查找都是成功的，所以本算法中沒有關(guān)于查找失敗的處理,由微積分可得,在等概率情況下,平均查找長(zhǎng)度約為n/3.9.30typedefstruct{DLNode*pre;intdata;DLNode*next;}DLNode;typedefstruct{DLNode*sp;intlength;}DSList;〃供查找的雙向循環(huán)鏈表類型DLNode*Search_DSList(DSList&L,intkey)〃在有序雙向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)上的查找算法,假定每次查莪都成功p=L.spif(p->data>key)(while(p->data>key)p=p->pre;L?sp=p;}elseif(p->data<key)(while(p->data<key)p=p->next;L.sp=p;}returnp;}//SearchDSList分析:本題的平均查找長(zhǎng)度與上一題相同,也是n/3.9.31intlast=O,flag=l;intIs_BSTree(BitreeT)〃判斷二叉樹T是否二叉排序樹，是則返回1,否則返回0{if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data<last)flag=O;〃與其中序前驅(qū)相比較last=T->data;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree9.32intlast=O;voidMaxLT_MinGT(BiTreeT,intx)〃找到二叉排序樹T中小于x的最大元素和大于x的最小元素{if(T->lchild)MaxLT_MinGT(T->lchild,x);〃本算法仍是借助中序遍歷來實(shí)現(xiàn)if(last<x&&T->data>=x)〃找到了小于x的最大元素printf(*a=%d\nz/,last);if(last<=x&&T->data>x)〃找到了大于x的最小元素printf("b=%d\n”,T->data);last=T->data;if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)〃從大到小輸出二叉排序樹T中所有不小于x的元素{if(T->rchild)Print_NLT(T->rchiId,x);if(T->data<x)exit();〃當(dāng)遇到小于x的元素時(shí)立即結(jié)束運(yùn)行printf("刎\n”,T->data);if(T->lchild)Print_NLT(T->lchild,x);〃先右后左的中序遍歷}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)〃刪除二叉排序樹T中所有不小于x元素結(jié)點(diǎn)，并釋放空間if(T->rchild)Delete_NLT(T->rchild,x);if(T->data<x)exit();〃當(dāng)遇到小于x的元素時(shí)立即結(jié)束運(yùn)行q=T;T=T->lchild;free(q);〃如果樹根不小于x,則刪除樹根,并以左子樹的根作為新的樹根if(T)Delete_NLT(T,x);〃繼續(xù)在左子樹中執(zhí)行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)〃打印輸出后繼線索二叉排序樹T中所有大于a且小于b的元素IP=T;while(!p->ltag)p=p->lchild;//找到最小元素while(p&&p->data<b){if(p->data>a)printf(^dXn*,p->data);〃輸出符合條件的元素if(p->rtag)p=p->rtag;else(p=p->rchild;while(!p->ltag)p=p->lchiId;)〃轉(zhuǎn)到中序后繼}//while}//Print_Between9.36voidBSTreeInsert_Key(BiThrTree&T,intx)〃在后繼線索二叉排序樹T中插入元素Iif(T->data<x)〃插入到右側(cè){if(T->rtag)〃T沒有右子樹時(shí)，作為右孩子插入{p=T->rchild;q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->rchild=q;T->rtag=0;q->rtag=l;q->rchild=p;〃修改原線索}elseBSTree_Insert_Key(T->rchiId,x);//T有右子樹時(shí),插入右子樹中}//ifelseif(T->data>x)〃插入到左子樹中(if(!T->lchild)〃T沒有左子樹時(shí)，作為左孩子插入(q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->lchild=q;q->rtagz:l;q->rchild=T;〃修改自身的線索elseBSTree_Insert_Key(T->lchild,x);//T有左子樹時(shí),插入左子樹中}//if}//BSTree_Insert_Key9.37StatusBSTree_Deletekey(BiThrTree&T,intx)〃在后繼線索二叉排序樹T中刪除元素x(BTNode*pre,*ptr,*suc;//ptr為x所在結(jié)點(diǎn),pre和sue分別指向ptr的前驅(qū)和后繼p=T;last=NULL;//last始終指向當(dāng)前結(jié)點(diǎn)p的前一個(gè)(前驅(qū))while(!p->ltag)p=p->lchild;〃找到中序起始元素while(p){if(p->data==x)〃找到了元素x結(jié)點(diǎn){pre=last;ptr=p;}elseif(last&&last->data=x)suc=p;//找到了x的后繼if(p->rtag)p=p->rtag;elseip=p->rchild;while(!p->ltag)p=p->lchild;)〃轉(zhuǎn)到中序后繼last=p;}//while〃借助中序遍歷找到元素x及其前驅(qū)和后繼結(jié)點(diǎn)if(!ptr)returnERROR;〃未找到待刪結(jié)點(diǎn)Delete_BSTree(ptr);〃刪除x結(jié)點(diǎn)if(pre&&pre->rtag)pre->rchild=suc;〃修改線索returnOK;J//BSTreeDelete_keyvoidDelete_BSTree(BiThrTree&T)〃課本上給出的刪除二叉排序樹的子樹T的算法,按照線索二叉留的結(jié)構(gòu)作了一些改動(dòng){q=T;if(!T->1tag&&T->rtag)〃結(jié)點(diǎn)無右子樹,此時(shí)只需重接其左子樹T=T->lchild;elseif(T->1tag&&!T->rtag)〃結(jié)點(diǎn)無左子樹，此時(shí)只需重接其右子樹T=T->rchild;elseif(!T->1tag&&!T->rtag)〃結(jié)點(diǎn)既有左子樹又有右子樹(p=T;r=T->lchild;while(!r->rtag)(s=r;r=r->rchild;//找到結(jié)點(diǎn)的前驅(qū)r和r的雙親sT->data=r->data;〃用r代替T結(jié)點(diǎn)if(s!=T)s->rchild=r->lchild;elses->lchild=r->lchild;〃重接r的左子樹到其雙親結(jié)點(diǎn)上q=r;}//elsefree(q);〃刪除結(jié)點(diǎn)}//Delete_BSTree分析:本算法采用了先求出x結(jié)點(diǎn)的前驅(qū)和后繼,再刪除x結(jié)點(diǎn)的辦法,這樣修改線索時(shí)會(huì)比較簡(jiǎn)單,直接讓前驅(qū)的線索指向后繼就行了.如果試圖在刪除X結(jié)點(diǎn)的同時(shí)修改線索,則問題反而復(fù)雜化了.9.38voidBSTreeMerge(BiTree&T,BiTree&S)〃把二叉排序樹S合并到T中{if(S->lchild)BSTree_Merge(T,S->lchild);if(S->rchild)BSTree_Merge(T,S->rchild);〃合并子樹Insert_Key(T,S);〃插入元素}//BSTree_MergevoidInsert_Key(Bitree&T,BTNode*S)〃把樹結(jié)點(diǎn)S插入到T的合適位置上{if(S->data>T->data)(if(!T->rchild)T->rchild=S;elseInsert_Key(T->rchild,S);}elseif(S->data<T->data)if(!T->lchild)T->lchild=S;elseInsert_Key(T->lchild,S);}S-"child=NULL;〃插入的新結(jié)點(diǎn)必須和原來的左右子樹斷絕關(guān)系S->rchild=NULL;〃否則會(huì)導(dǎo)致樹結(jié)構(gòu)的混亂}//Insert_Key分析:這是個(gè)與課本上不同的插入算法.在合并過程中,并不釋放或新建任何結(jié)點(diǎn),而是采取修改指針的方式來完成合并.這樣,就必須按照后序序列把一棵樹中的元素逐個(gè)連接到另一棵樹上,否則將會(huì)導(dǎo)致樹的結(jié)構(gòu)的混亂.9.39voidBSTreeSplit(BiTree&T,BiTree&A,BiTree&B,intx)〃把二叉排序樹T分裂為兩棵二叉排序樹A和B,其中A的元素全部小于等于x,B的元素全部大于xIif(T->lchild)BSTree_Split(T->lchild,A,B,x);if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子樹if(T->data<=x)Insert_Key(A,T);elseInsert_Key(B,T);〃將元素結(jié)點(diǎn)插入合適的樹中}//BSTree_SplitvoidInsertKey(Bitree&T,BTNode*S)〃把樹結(jié)點(diǎn)S插入到T的合適位置上(if(!T)T=S;〃考慮到剛開始分裂時(shí)樹A和樹B為空的情況elseif(S->data>T->data)〃其余部分與上一題同if(!T->rchild)T->rchild=S;elseInsert_Key(T->rchild,S);}elseif(S->data