（考研專升本資料）二叉樹算法

9二叉樹按二叉鏈表形式存儲，對于樹中每個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的

空間。

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

歷。

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

結(jié)點的父結(jié)點。

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

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

(

if(bt){

DeleteTree(bt->lchild);

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

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

)

)

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

voidSearch(BiTreebt,intx)

(

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

if(bt){

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

DeleteXTree(p->lchild);

exit(O);

)

InitQueue(Q);

EnQueue(Q,bt);

while(!lsEmpty(Q)){

DeQueue(Q,p);

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

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

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

}

else

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

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

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

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

)

else

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

)

}

第1頁共n頁

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

/*

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

的祖先，依次出棧打印即可。因為查找的過程就是后序遍歷的過程，因此使用的棧的深度不超過樹的深

度。

7

typedefstruct{

BiTreet;

inttag;//tag=0表示左子女已被訪問，tag=l表示右子女已被訪問

}stack;

voidSearch(BiTreebtjntx)

(

stacks口;〃棧容量足夠大

top=0;

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

{

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

(

s[++top].t=bt;

s[top].tag=0;

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

}

if(bt->data==x)

(

printf("所查結(jié)點的所有祖先結(jié)點的值為:\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頁共11頁

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

祖先結(jié)點ro

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

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

算法思想：采用后序非遞歸算法，棧中存放二又樹結(jié)點的指針，當訪問到某結(jié)點時，棧中所有元素均為

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

續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配(即相等)的元素就是

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

typedefstruct{

BiTreet;

inttag;//tag=O表示左子女已被訪問，tag=l表示右子女已被訪問

}stack;

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

BiTreeAncester(BiTreeROOTBiTNode*p,BiTNode*q){

top=0;

bt=ROOT;

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

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時，棧中元素均為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é)點

for(i=top;i>0;i-){〃將棧中元素的樹結(jié)點到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無公共祖先

第3頁共11頁

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

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

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

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

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

typedefstruct（

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

intlevel[MaxSize];〃保存data中相同下標結(jié)點的層次

intfront,rear;

}Qu;

intBTWidth(BiTreeb){

BiTreep;

intk,max,i,n;

Qu.front二Qu.rear=-1;〃隊列為空

Qu.rear++；

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

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

while(Qu.front<Qu.rear){

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

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

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

)

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

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

)

}//while

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

k=1;//k表示從第一層開始查找

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

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

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

n++;i++;

)

k=Qu.level[i];

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

)

returnmax;

第4頁共U頁

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

/*

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

先序遍歷解決問題。

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

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

傳遞。

算法步驟如下：

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

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

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

③最后返回計算出的wpl即可。

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

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

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

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

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

*/

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

typedefstructBiTNode{

intweight;

structBiTNode*lchild,*rchild;

JBiTNode,*BiTree;

intWPL(BiTreeroot){

returnwpl_PreOrder(root,0);

intwpl_Preorder(BiTreeroot,intdeep){

staticintwpl=0;〃定義一個static變量存儲wpl

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

wpl+=deep*root->weight;

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

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

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

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

returnwpl;

第5頁共U頁

18將給定的表達式（二叉樹）轉(zhuǎn)換為等價的中綴表達式（通過括號反映操作符的計算次序）并輸出。

/*

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

表達式樹的中序序列加上必要的括號即為等價的中綴表達式?？梢曰诙鏄涞闹行虮闅v策略得到所需

的表達式。

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

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

點）和操作數(shù)（對應(yīng)葉結(jié)點）不需要添加括號。

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

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

遍歷其左子樹之前加上左括號，遍歷完右子樹后加上右括號。

*/

voidBtreeToE（BTree*root）｛

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

voidBtreeToExp(BTree*root,intdeep)

(

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

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

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

else(

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

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

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

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

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

)

第6頁共n頁

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

/*

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

每個結(jié)點的度，逐個鏈接結(jié)點。

*/

//definemaxNodes15

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

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

〃參數(shù)n是樹結(jié)點個數(shù)

CSNode*pointer=newCSNode[maxNodes];〃判斷pointer[i]為空的語句未寫

inti,j,d,k=0;

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

pointer[i]=newcsNode;〃判斷pointer]]為空的語句未寫

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

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

}

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

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

if(d){

1<++;〃1<為子女結(jié)點序號

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

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

k++;

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

)

)

T=pointer[0];

delete[]pointer;

第7頁共11頁

24利用二叉樹遍歷的思想編寫一個判斷二叉樹是否平衡二叉樹的算法

/*

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

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

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

2)若bt僅有根結(jié)點，則高度為Lbalanced。

3)否則，對bt的左、右子樹執(zhí)行遞歸運算，返回左、右子樹的高度和平衡標記，bt的高度

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

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

*/

voidJudgeAVL(BiTreebt,int&balance,intsh){

〃本算法判斷一個給定的二叉樹是否為平衡二叉樹

intbl=O,br=O,hl=0,hr=O;〃左、右子樹的平衡標記和高度

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

h=0;

balance=l;

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

h=l;

balance=l;

)

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

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

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

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

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

else

balance=0;

第8頁共U頁

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

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

/*

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

vj,則說明存在由頂點vi到頂點j的路徑。

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

intvisited[MAXSIZE]={0};〃訪問標記數(shù)組

intExist_Path_DFS(ALGraphG,inti,intj){

intp;〃頂點序號

if(i==j)

return1;//i就是j

else{

visited[i]=l;〃置訪問標記

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)先遍歷算法的實現(xiàn)如下

intvisited[MAXSI2E]={0};〃訪問標記數(shù)組

intExist_Path_BFS(ALGraphGJntijntj){

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

InitQueue(Q);

EnQueue(QJ);〃頂點i入隊

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

DeQueue(Q,u);〃隊頭頂點出隊

visited[u]=l;〃置訪問標記

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

〃檢查所有鄰接點

k=p.adjvex;

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

return1;

if(!visited[k])〃否則，頂點k入隊

EnQueue(Q,k);

}//for

}//while

return0;

)

第9頁共n頁

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

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

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

/*

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

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

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