9二叉樹(shù)按二叉鏈表形式存儲(chǔ)，對(duì)于樹(shù)中每個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的

空間。

刪除以元素值X為根的子樹(shù)，只要能刪除其左、右子樹(shù)，就可以釋放值為X的根結(jié)點(diǎn)，因此宜采用后序遍

歷。

算法思想：刪除值為X的結(jié)點(diǎn)，意味著應(yīng)將其父結(jié)點(diǎn)的左(右)子女指針置空，用層次遍歷易于找到某

結(jié)點(diǎn)的父結(jié)點(diǎn)。

本題要求刪除樹(shù)中每個(gè)元素值為X的結(jié)點(diǎn)的子樹(shù)，因此要遍歷完整棵二叉樹(shù)。

voidDeleteXTree(BiTreebt)〃刪除以bt為根的子樹(shù)

(

if(bt){

DeleteTree(bt->lchild);

DeleteTree(bt->rchild);〃刪除bt的左子樹(shù)、右子樹(shù)

free(bt);〃釋放被刪結(jié)點(diǎn)所占的存儲(chǔ)空間

)

)

〃在二叉樹(shù)上查找所有以x為元素值的結(jié)點(diǎn)，并刪除以其為根的子樹(shù)

voidSearch(BiTreebt,intx)

(

BiTreeQ口;〃Q是存放二叉樹(shù)結(jié)點(diǎn)指針的隊(duì)列，容量足夠大

if(bt){

if(bt->data==x){〃若根結(jié)點(diǎn)值為x,則刪除整棵樹(shù)

DeleteXTree(p->lchild);

exit(O);

)

InitQueue(Q);

EnQueue(Q,bt);

while(!lsEmpty(Q)){

DeQueue(Q,p);

if(p->lchild)〃若左子女非空

if(p->lchild->data==x){〃左子樹(shù)符合則刪除左子樹(shù)

DeleteXTree(p->lchild);p->lchild=NULL;〃父結(jié)點(diǎn)的左子女置空

}

else

EnQueue(Q,p->lchild);〃左子樹(shù)入隊(duì)列

if(p->rchild)〃若右子女非空

if(p->rchiid->data==x){〃右子女符合則刪除右子樹(shù)

DeleteXTree(p->rchild);p->rchild=NULL;〃父結(jié)點(diǎn)的右子女置空

)

else

EnQueue(Q,p->rchild);〃右子女入隊(duì)列

)

}

第1頁(yè)共n頁(yè)

10二叉樹(shù)中查找值為x的結(jié)點(diǎn)，打印值為x的結(jié)點(diǎn)的所有祖先，假設(shè)值為x的結(jié)點(diǎn)不多于一個(gè)。

/*

算法思想：采用非遞歸后序遍歷，最后訪問(wèn)根結(jié)點(diǎn)，訪問(wèn)到值為X的結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)

的祖先，依次出棧打印即可。因?yàn)椴檎业倪^(guò)程就是后序遍歷的過(guò)程，因此使用的棧的深度不超過(guò)樹(shù)的深

度。

7

typedefstruct{

BiTreet;

inttag;//tag=0表示左子女已被訪問(wèn)，tag=l表示右子女已被訪問(wèn)

}stack;

voidSearch(BiTreebtjntx)

(

stacks口;〃棧容量足夠大

top=0;

while(bt!=NULL||top>0)

{

while(bt!=NULL&&bt->data!=x)〃結(jié)點(diǎn)入棧

(

s[++top].t=bt;

s[top].tag=0;

bt=bt->lchild;〃沿左分支向下

}

if(bt->data==x)

(

printf("所查結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的值為:\n");〃找到x

for(i=l;i<=top;i++)

printf(”％d，s[i].t?>data);〃輸出祖先值后結(jié)束

exit(l);

)

while(top!=0&&s[top].tag==l)

top-;〃退棧(空遍歷)

if(top!=0)

(

s[top].tag=1;

bt=s[top].t->rchild;〃沿右分支向下遍歷

}

}//while

第2頁(yè)共11頁(yè)

11二叉樹(shù)中p和q分別為指向該二叉樹(shù)中任意兩個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法找到p和q的最近公共

祖先結(jié)點(diǎn)ro

后序遍歷最后訪問(wèn)根結(jié)點(diǎn)，即在遞歸算法中，根是壓在棧底的。

本題要找P和q的最近公共祖先結(jié)點(diǎn)r,不失一般性，設(shè)p在q的左邊。

算法思想：采用后序非遞歸算法，棧中存放二又樹(shù)結(jié)點(diǎn)的指針，當(dāng)訪問(wèn)到某結(jié)點(diǎn)時(shí)，棧中所有元素均為

該結(jié)點(diǎn)的祖先。后序遍歷必然先遍歷到結(jié)點(diǎn)P，棧中元素均為p的祖先。先將棧復(fù)制到另一輔助棧中。繼

續(xù)遍歷到結(jié)點(diǎn)q時(shí)，將棧中元素從棧頂開(kāi)始逐個(gè)到輔助棧中去匹配，第一個(gè)匹配(即相等)的元素就是

結(jié)點(diǎn)P和q的最近公共祖先。

typedefstruct{

BiTreet;

inttag;//tag=O表示左子女已被訪問(wèn)，tag=l表示右子女已被訪問(wèn)

}stack;

stacks[Lsl[];〃棧，容量足夠大

BiTreeAncester(BiTreeROOTBiTNode*p,BiTNode*q){

top=0;

bt=ROOT;

while(bt!=NULL&&bt!=p&&bt!=q){〃結(jié)點(diǎn)入棧

while(bt!=NULL){

S[++top].t=bt;

s[topj.tag=0;

bt=bt->lchild;

"/沿左分支向下

while(top!=0&&s[top].tag==1){

〃假定p在q的左側(cè)，遇到p時(shí)，棧中元素均為p的祖先

if(s[top].t==p){

for(i=l;i<=top;i++){

sl[i]=s[i];

topi=top;

}〃將棧s的元素轉(zhuǎn)入輔助棧si保存

if(s[top].t==q)〃找到q結(jié)點(diǎn)

for(i=top;i>0;i-){〃將棧中元素的樹(shù)結(jié)點(diǎn)到si中去匹配

for(j=topl;j>0;j-)

if(sl[j].t==s[i].t)

returns[i].t;//p和q的最近公共祖先已找到

)

top-;〃退棧

}//while

if(top!=0){

s[top].tag=1;

bt=s[top].t->rchild;

)〃沿右分支向下遍歷

}//while

returnNULL;//p和q無(wú)公共祖先

第3頁(yè)共11頁(yè)

12二叉樹(shù)按二叉鏈表形式存儲(chǔ)，試求非空二叉樹(shù)b的寬度（即具有結(jié)點(diǎn)數(shù)最多的那一層的結(jié)點(diǎn)個(gè)數(shù)）。

采用層次遍歷的方法求出所有結(jié)點(diǎn)的層次，并將所有結(jié)點(diǎn)和對(duì)應(yīng)的層次放在一個(gè)隊(duì)列中。然后通過(guò)掃描

隊(duì)列求出各層的結(jié)點(diǎn)總數(shù)，最大的層結(jié)點(diǎn)總數(shù)即為二又樹(shù)的寬度。

注意:本題隊(duì)列中的結(jié)點(diǎn)，在出隊(duì)后仍需要保留在隊(duì)列中，以便求二又樹(shù)的寬度，所以設(shè)置的隊(duì)列采用非

環(huán)形隊(duì)列，否則在出隊(duì)后可能被其他結(jié)點(diǎn)覆蓋，無(wú)法再求二又樹(shù)的寬度。

typedefstruct（

BiTreedata[MaxSize];//i保存隊(duì)列中的結(jié)點(diǎn)指針

intlevel[MaxSize];〃保存data中相同下標(biāo)結(jié)點(diǎn)的層次

intfront,rear;

}Qu;

intBTWidth(BiTreeb){

BiTreep;

intk,max,i,n;

Qu.front二Qu.rear=-1;〃隊(duì)列為空

Qu.rear++；

Qu.data[Qu.rear]二b;〃根結(jié)點(diǎn)指針入隊(duì)

Qu.level[Qu.rear]=l;〃根結(jié)點(diǎn)層次為1

while(Qu.front<Qu.rear){

Qu.front++；p=Qu.data[Qu.front];k=Qu.level[Qu.front];

if(p->lchild!=NULL){〃左孩子進(jìn)隊(duì)列

Qu.rear++;Qu.data[Qu.rear]=p->lchild;Qu.level[Qu.rear]=k+l；

)

if(p->rchild1=NULL){〃右孩子進(jìn)隊(duì)列

Qu.rear++;Qu.data[Qu.rear]=p->rchild;Qu.level[Qu.rear]=k+l;

)

}//while

max=0;i=0;//max保存同一層最多的結(jié)點(diǎn)個(gè)數(shù)

k=1;//k表示從第一層開(kāi)始查找

while(i<=Qu.rear){〃i掃描隊(duì)中所有元素

n=0;〃n統(tǒng)計(jì)第k層的結(jié)點(diǎn)個(gè)數(shù)

while(i<=Qu.rear&6Qu.level[i]==k){

n++;i++;

)

k=Qu.level[i];

if(n>max)max=n;〃保存最大的n

)

returnmax;

第4頁(yè)共U頁(yè)

17二叉樹(shù)按二叉鏈表形式存儲(chǔ)，設(shè)計(jì)求二叉樹(shù)T的WPL的算法

/*

考查二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，二叉樹(shù)的帶權(quán)路徑長(zhǎng)度為每個(gè)葉結(jié)點(diǎn)的深度與權(quán)值之積的總和，可以使用

先序遍歷解決問(wèn)題。

1)算法的基本設(shè)計(jì)思想。

基于先序遞歸遍歷的算法思想是用一個(gè)static變量記錄wpl,把每個(gè)結(jié)點(diǎn)的深度作為遞歸函數(shù)的一個(gè)參數(shù)

傳遞。

算法步驟如下：

①若該結(jié)點(diǎn)是葉結(jié)點(diǎn)，則變量wpl加上該結(jié)點(diǎn)的深度與權(quán)值之積。

②若該結(jié)點(diǎn)是非葉結(jié)點(diǎn)，則左子樹(shù)不為空時(shí)，對(duì)左子樹(shù)調(diào)用遞歸算法，右子樹(shù)不為空，對(duì)右子樹(shù)調(diào)用遞

歸算法，深度參數(shù)均為本結(jié)點(diǎn)的深度參數(shù)加1。

③最后返回計(jì)算出的wpl即可。

PS:當(dāng)static關(guān)鍵字用于代碼塊內(nèi)部的變量的聲明時(shí);用于修改變量的存儲(chǔ)類型，即從自動(dòng)變量修改為靜態(tài)

變量，但變量的鏈接屬性和作用域不受影響。用這種方式聲明的變量在程序執(zhí)行之前創(chuàng)建，并在程序的

整個(gè)執(zhí)行期間一直存在，而不是每次在代碼塊開(kāi)始執(zhí)行時(shí)創(chuàng)建，在代碼塊執(zhí)行完畢后銷毀。也就是說(shuō)，

它保持局部變量?jī)?nèi)容的持久。靜態(tài)局部變量的生存期雖然為整個(gè)源程序，但其作用域仍與局部變量相同，

即只能在定義該變量的函數(shù)內(nèi)使用該變量。退出該函數(shù)后，盡管該變量還繼續(xù)存在，但不能使用它。

*/

//二叉樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：

typedefstructBiTNode{

intweight;

structBiTNode*lchild,*rchild;

JBiTNode,*BiTree;

intWPL(BiTreeroot){

returnwpl_PreOrder(root,0);

intwpl_Preorder(BiTreeroot,intdeep){

staticintwpl=0;〃定義一個(gè)static變量存儲(chǔ)wpl

if(root->lchild==NULL&&root->rchild==NULL)〃若為葉結(jié)點(diǎn)，累積wpl

wpl+=deep*root->weight;

if(root->lchild!=NULL)〃若左子樹(shù)不空，對(duì)左子樹(shù)遞歸遍歷

wpl_PreOrder(root->lchild,deep+l);

if(root->rchild!=NULL)〃若右子樹(shù)不空，對(duì)右子樹(shù)遞歸遍歷

wpl_PreOrder(root->rchild,deep+l);

returnwpl;

第5頁(yè)共U頁(yè)

18將給定的表達(dá)式（二叉樹(shù)）轉(zhuǎn)換為等價(jià)的中綴表達(dá)式（通過(guò)括號(hào)反映操作符的計(jì)算次序）并輸出。

/*

1）算法的基本設(shè)計(jì)思想：

表達(dá)式樹(shù)的中序序列加上必要的括號(hào)即為等價(jià)的中綴表達(dá)式。可以基于二叉樹(shù)的中序遍歷策略得到所需

的表達(dá)式。

表達(dá)式樹(shù)中分支結(jié)點(diǎn)所對(duì)應(yīng)的子表達(dá)式的計(jì)算次序，由該分支結(jié)點(diǎn)所處的位置決定。為得到正確的中綴

表達(dá)式，需要在生成遍歷序列的同時(shí)，在適當(dāng)位置增加必要的括號(hào)。顯然，表達(dá)式的最外層（對(duì)應(yīng)根結(jié)

點(diǎn)）和操作數(shù)（對(duì)應(yīng)葉結(jié)點(diǎn)）不需要添加括號(hào)。

2）算法實(shí)現(xiàn)：

將二又樹(shù)的中序遍歷遞歸算法稍加改造即可得本題的答案。除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，遍歷到其他結(jié)點(diǎn)時(shí)在

遍歷其左子樹(shù)之前加上左括號(hào)，遍歷完右子樹(shù)后加上右括號(hào)。

*/

voidBtreeToE（BTree*root）｛

BtreeToExp（root,1）;〃根的高度為1

voidBtreeToExp(BTree*root,intdeep)

(

if(root==NULL)return;〃空結(jié)點(diǎn)返回

elseiffroot->left==NULL&&root->right==NULL)〃若為葉結(jié)點(diǎn)

printf("%s",root->data);

else(

if(deep>l)printf("(")；〃輸出操作數(shù)，不加括號(hào)

BtreeToExp(root->left,deep+l);〃若有子表達(dá)式貝(I力口1層括號(hào)

printf("%s",root->data);〃輸出操作符

BtreeToExp(root->right,deep+l);

if(deep>l)printf(")")；〃若有子表達(dá)式則加1層括號(hào)

)

第6頁(yè)共n頁(yè)

21已知一棵樹(shù)的層次序列及每個(gè)結(jié)點(diǎn)的度，編寫(xiě)算法構(gòu)造此時(shí)的孩子-兄弟鏈接

/*

本題與樹(shù)的層次序列有關(guān)。可設(shè)立一個(gè)輔助數(shù)組pointer口存儲(chǔ)新建樹(shù)的各結(jié)點(diǎn)的地址，再根據(jù)層次序列與

每個(gè)結(jié)點(diǎn)的度，逐個(gè)鏈接結(jié)點(diǎn)。

*/

//definemaxNodes15

voidcreatecSTree_Degree(Csfree&T,inte[],intdegree[],intn){

〃根據(jù)樹(shù)結(jié)點(diǎn)的層次序列e口和各結(jié)點(diǎn)的度degree口構(gòu)造樹(shù)的孩子.兄弟鏈表

〃參數(shù)n是樹(shù)結(jié)點(diǎn)個(gè)數(shù)

CSNode*pointer=newCSNode[maxNodes];〃判斷pointer[i]為空的語(yǔ)句未寫(xiě)

inti,j,d,k=0;

for(i=0;i<n;i++){〃初始化

pointer[i]=newcsNode;〃判斷pointer]]為空的語(yǔ)句未寫(xiě)

pointer[i]->data=e[i];

pointer[i]->lchild=pointer[i]->rsibling=NULL;

}

for(i=0;i<n;i++){

d二degree]];〃結(jié)點(diǎn)i的度數(shù)

if(d){

1<++;〃1<為子女結(jié)點(diǎn)序號(hào)

pointe巾卜>lchild=pointer伙];〃建立i與子女k間的鏈接

for(j=2;j<=d;j++){

k++;

pointer[k-l]->rsibling=pointer[k];

)

)

T=pointer[0];

delete[]pointer;

第7頁(yè)共11頁(yè)

24利用二叉樹(shù)遍歷的思想編寫(xiě)一個(gè)判斷二叉樹(shù)是否平衡二叉樹(shù)的算法

/*

設(shè)置二叉樹(shù)的平衡標(biāo)記balance,標(biāo)記返回二又樹(shù)bt是否為平衡二叉樹(shù)，若為平衡二叉樹(shù)，

則返回1,否則返回0：h為二又樹(shù)bt的高度。采用后序遍歷的遞歸算法：

1)若bt為空,則高度為0,balance=lo

2)若bt僅有根結(jié)點(diǎn)，則高度為L(zhǎng)balanced。

3)否則，對(duì)bt的左、右子樹(shù)執(zhí)行遞歸運(yùn)算，返回左、右子樹(shù)的高度和平衡標(biāo)記，bt的高度

為最高子樹(shù)的高度加1。若左、右子樹(shù)的高度差大于1,則balanced;若左、右子樹(shù)的

高度差小于等于1,且左、右子樹(shù)都平衡時(shí)，balance=l,否則balance=0。

*/

voidJudgeAVL(BiTreebt,int&balance,intsh){

〃本算法判斷一個(gè)給定的二叉樹(shù)是否為平衡二叉樹(shù)

intbl=O,br=O,hl=0,hr=O;〃左、右子樹(shù)的平衡標(biāo)記和高度

if(bt==NULL){〃空樹(shù)，高度為0

h=0;

balance=l;

elseif(bt->lchild==NULL&6bt->xchild==NULL){〃僅有根結(jié)點(diǎn)，則高度為1

h=l;

balance=l;

)

Judge_AVL(bt->lchild,bl,hl);〃遞歸判斷左子樹(shù)

Judge_AVL(bts>rchild,br,hr);〃遞歸判斷右子樹(shù)

h=(hl>hr?hl:hr)+1;

if(abs(hl-hr)<2)〃若子樹(shù)高度差的絕對(duì)值<2,則看左、右子樹(shù)是否都平衡

balance=bl&&br;〃66為邏輯與，即左、右子樹(shù)都平衡時(shí)，二叉樹(shù)平衡

else

balance=0;

第8頁(yè)共U頁(yè)

4分別采用基于深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi

到頂點(diǎn)vj的路徑(用)o注意，算法中涉及的圖的基本操作必須在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。

/*

兩個(gè)不同的遍歷算法都采用從頂點(diǎn)V,出發(fā)，依次遍歷圖中每個(gè)頂點(diǎn)，直到搜索到頂點(diǎn)vj,若能夠搜索到

vj,則說(shuō)明存在由頂點(diǎn)vi到頂點(diǎn)j的路徑。

〃深度優(yōu)先遍歷算法的實(shí)現(xiàn)如下

intvisited[MAXSIZE]={0};〃訪問(wèn)標(biāo)記數(shù)組

intExist_Path_DFS(ALGraphG,inti,intj){

intp;〃頂點(diǎn)序號(hào)

if(i==j)

return1;//i就是j

else{

visited[i]=l;〃置訪問(wèn)標(biāo)記

for(p=FirstNeighbor(GJ);p>=0;p=NextNeighbor(G,i,p)){

k=p.adjvex;

if(!visited[p]&&Exist_Path_DFS(G,pj))

return1;

}//for

}//else

return0;

〃廣度優(yōu)先遍歷算法的實(shí)現(xiàn)如下

intvisited[MAXSI2E]={0};〃訪問(wèn)標(biāo)記數(shù)組

intExist_Path_BFS(ALGraphGJntijntj){

〃廣度優(yōu)先判斷有同圖G中頂點(diǎn)vi到頂點(diǎn)vj是否有路徑，是則返回1,否則返回0

InitQueue(Q);

EnQueue(QJ);〃頂點(diǎn)i入隊(duì)

while(!isEmpty(Q)){〃非空循環(huán)

DeQueue(Q,u);〃隊(duì)頭頂點(diǎn)出隊(duì)

visited[u]=l;〃置訪問(wèn)標(biāo)記

for(p=FirstNeighbor(G/i);p;p=NextNeighbor(GJ,p)){

〃檢查所有鄰接點(diǎn)

k=p.adjvex;

if(k==j)〃若k==j,則查找成功

return1;

if(!visited[k])〃否則，頂點(diǎn)k入隊(duì)

EnQueue(Q,k);

}//for

}//while

return0;

)

第9頁(yè)共n頁(yè)

312016統(tǒng)考真題】已知由n(n>2)個(gè)正整數(shù)構(gòu)成的集合A={akI0<=k<n},將其劃分為兩個(gè)不相交的子

集A1和A2,元素個(gè)數(shù)分別是nl和n2,Al和4中的元素之和分別為S1和立。設(shè)計(jì)一個(gè)盡可能高效的

劃分算法，滿足|nl-n2l最小且|S1-S2|最大

/*

1)算法的基本設(shè)計(jì)思想

由題意知，將最小的L[n/2]個(gè)元素放在A1中，其余的元素放在A2中，分組結(jié)果即可滿足題目要求。仿照

快速排序的思想，基于樞軸將n個(gè)整數(shù)劃分為兩個(gè)子集。根據(jù)劃分后樞軸所處的位置i