二叉樹(shù)算法匯總集合

樹(shù)與二叉樹(shù)算法匯總1．以二叉樹(shù)表示算術(shù)表達(dá)式，根結(jié)點(diǎn)用于存儲(chǔ)運(yùn)算符。若能先分別求出左子樹(shù)和右子樹(shù)表示的子表達(dá)式的值，最后就可以根據(jù)根結(jié)點(diǎn)的運(yùn)算符的要求，計(jì)算出表達(dá)式的最后結(jié)果。typedefstructnode{ElemTypedata;floatval;charoptr;//只取‘+'，‘-'，‘*'，‘/'structnode*lchild，*rchild}BiNode,*BiTree;floatPostEval(BiTreebt)//以后序遍歷算法求以二叉樹(shù)表示的算術(shù)表達(dá)式的值{floatlv,rv;if(bt!=null){lv=PostEval(bt->lchild);//求左子樹(shù)表示的子表達(dá)式的值rv=PostEval(bt->rchild);//求右子樹(shù)表示的子表達(dá)式的值switch(bt->optr){case‘+':value=lv+rv;break;case‘-':value=lv-rv;break;case‘*':value=lv*rv;break;case‘/':value=lv/rv;}}return(value);}32.二叉樹(shù)采取順序結(jié)構(gòu)存儲(chǔ)，是按完全二叉樹(shù)格式存儲(chǔ)的。對(duì)非完全二叉樹(shù)要補(bǔ)上“虛結(jié)點(diǎn)”。由于不是完全二叉樹(shù)，在順序結(jié)構(gòu)存儲(chǔ)中對(duì)葉子結(jié)點(diǎn)的判定是根據(jù)其左右子女為0。葉子和雙親結(jié)點(diǎn)下標(biāo)間的關(guān)系滿足完全二叉樹(shù)的性質(zhì)。intLeaves(inth)//求深度為h以順序結(jié)構(gòu)存儲(chǔ)的二叉樹(shù)的葉子結(jié)點(diǎn)數(shù){intBT[];intlen=2hT,count=0;//BT是二叉樹(shù)結(jié)點(diǎn)值一維數(shù)組，容量為2hfor(i=1;i<=len;i++)//數(shù)組元素從下標(biāo)1開(kāi)始存放if(BT[i]!=0)//假定二叉樹(shù)結(jié)點(diǎn)值是整數(shù)，“虛結(jié)點(diǎn)”用0填充if(i*2)〉len)count++;//第i個(gè)結(jié)點(diǎn)沒(méi)子女，肯定是葉子elseif(BT[2*i]==0&&2*i+1<=len&&BT[2*i+1]==0)count++;//無(wú)左右子女的結(jié)點(diǎn)是葉子return(count)}//結(jié)束Leaves★★建立二叉樹(shù)算法★★6．二叉樹(shù)是遞歸定義的，以遞歸方式建立最簡(jiǎn)單。判定是否是完全二叉樹(shù)，可以使用隊(duì)列，在遍歷中利用完全二叉樹(shù)“若某結(jié)點(diǎn)無(wú)左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。BiTreeCreat()//建立二叉樹(shù)的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu){ElemTypex；BiTreebt;scanf(“%d”,&x);//本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x==0)bt=null;elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode));bt->data=x;bt->lchild=creat();bt->rchild=creat();}elseerror(“輸入錯(cuò)誤")；return(bt);}//結(jié)束B(niǎo)iTreeintJudgeComplete(BiTreebt)//判斷二叉樹(shù)是否是完全二叉樹(shù),如是，返回1，否則，返回0{inttag=0;BiTreep=bt,Q[];//Q是隊(duì)列，元素是二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大if(p==null)return(1);QueueInit(Q);QueueIn(Q,p);//初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while(!QueueEmpty(Q)){p=QueueOut(Q);//出隊(duì)if(p->lchild&&!tag)QueueIn(Q,p->lchild);//tag==0結(jié)點(diǎn)不空，左子入隊(duì)else{if(p->lchild)return0;//tag==1前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空elsetag=1;}//p->lchild==null首次出現(xiàn)結(jié)點(diǎn)為空if(p->rchild&&!tag)QueueIn(Q,p->rchild);//tag=0結(jié)點(diǎn)不空，右子女入隊(duì)else{if(p->rchild)return0;elsetag=1;}}//whilereturn1;//是完全二叉樹(shù)}//JudgeComplete2[算法討論]完全二叉樹(shù)證明還有其它方法。判斷時(shí)易犯的錯(cuò)誤是證明其左子樹(shù)和右子數(shù)都是完全二叉樹(shù)，由此推出整棵二叉樹(shù)必是完全二叉樹(shù)的錯(cuò)誤結(jié)論。7．BiTreeCreat(ElemTypeA[],inti)//n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存于一維數(shù)組A中，本算法據(jù)此遞歸建立以二叉鏈表表示的完全二叉樹(shù){BiTreetree;if(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[算法討論]初始調(diào)用時(shí)，i=l。9.二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)(一維數(shù)組)是按完全二叉樹(shù)的形狀存儲(chǔ)的，不是完全二叉樹(shù)的二叉樹(shù)順序存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。數(shù)組中的第一個(gè)元素是根結(jié)點(diǎn)。本題中采用隊(duì)列結(jié)構(gòu)。typedefstruct{BiTreebt;//二叉樹(shù)結(jié)點(diǎn)指針intnum;}tnode//num是結(jié)點(diǎn)在一維數(shù)組中的編號(hào)tnodeQ[maxsize];//循環(huán)隊(duì)列，容量足夠大voidcreat(BiTreeT，ElemTypeBT[])//深度h的二叉樹(shù)存于一維數(shù)組BT[l:2hT]中，本算法生成該二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu){tnodetq;//tq是隊(duì)列元素intlen=2h-1;//數(shù)組長(zhǎng)度T=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)T->data=BT[1];//根結(jié)點(diǎn)數(shù)據(jù)tq.bt=T;tq.num=1;Q[1]=tq;//根入隊(duì)列front=0;rear=1;//循環(huán)隊(duì)列頭、尾指針while(front!=rear)//當(dāng)隊(duì)列不空時(shí)循環(huán){front=(front+1)%maxsize;tq=Q[front];p=tq.bt;i=tq.num;//出隊(duì)，取出結(jié)點(diǎn)及編號(hào)if(BT[2*i]==‘#'||2*i>len)p->lchild=null;//左子樹(shù)為空，‘#'表示虛結(jié)點(diǎn)else//建立左子女結(jié)點(diǎn)并入隊(duì)列{p->lchild=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)空間p->lchilddata=BT[2*i];//左子女?dāng)?shù)據(jù)tq.bt=p->lchild;tq.num=2*i;rear=(rear+1)%maxsize;//計(jì)算隊(duì)尾位置Q[rear]=tq;//左子女結(jié)點(diǎn)及其編號(hào)入隊(duì)}if(BT[2*i+1]==‘#'||2*i+1>len)p->rchild=null;//右子樹(shù)為空else//建立右子女結(jié)點(diǎn)并入隊(duì)列{p->rchild=(BiTree)malloc(sizeof(BiNode);//申請(qǐng)結(jié)點(diǎn)空間p->rchild->data=BT[2*i+1];tq.bt=p->rchild;tq.num=2*i+1;rear=(rear+1)%maxsize;Q[rear]=tq;//計(jì)算隊(duì)尾位置,右子女及其編號(hào)入隊(duì)}}//while}//結(jié)束creat[算法討論]本題中的虛結(jié)點(diǎn)用‘#'表示。應(yīng)根據(jù)二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)的類型而定。10．本題靜態(tài)鏈表中結(jié)點(diǎn)是按動(dòng)態(tài)二叉鏈表的前序遍歷順序存放的。首先對(duì)動(dòng)態(tài)二叉鏈表的二叉樹(shù)進(jìn)行前序遍歷，填寫(xiě)靜態(tài)鏈表的“下標(biāo)”和data域，再對(duì)動(dòng)態(tài)二叉鏈表的二叉樹(shù)進(jìn)行層次遍歷，設(shè)隊(duì)列Q,填寫(xiě)靜態(tài)鏈表的lchild域和rchild域。typedefstructnode//靜態(tài)鏈表結(jié)點(diǎn)結(jié)構(gòu){ElemTypedata;//結(jié)點(diǎn)數(shù)據(jù)introw,lchild,rchild;//下標(biāo)，左右子女}component；componentst[];//st容量足夠大structnode{BiTreet;intidx;}qbt;staticintnum=0;voidPreOrder(BiTreebt);//前序遍歷二叉樹(shù)，填寫(xiě)靜態(tài)鏈表的"下標(biāo)”和data域{if(bt){st[++num].data=bt->data;st[num].row=num;PreOrder(bt->lchild);PreOrder(bt->rchild);3}}intLocate(ElemTypex)//在靜態(tài)鏈表中查二叉樹(shù)結(jié)點(diǎn)的下標(biāo){for(i=1;i<=num;i++)if(st[i].data==x)return(i);}voidDynaToST(BiTreebt)//將二叉樹(shù)的動(dòng)態(tài)二叉鏈表結(jié)構(gòu)轉(zhuǎn)為靜態(tài)鏈表結(jié)構(gòu){inti=0;//i為靜態(tài)鏈表st的下標(biāo)if(bt!=null){Queuelnit(Q);//Q是隊(duì)列，容量足夠大，隊(duì)列元素是qbtqbt.t=bt;qbt.idx=1;QueueIn(Q,qbt);st[1].data=bt->data;while(!QueueEmpty(Q)){qbt=QueueOut(Q);//出隊(duì)列p=qbt.t;i=qbt.idx;//二叉樹(shù)結(jié)點(diǎn)及在靜態(tài)鏈表中的下標(biāo)if(p-〉lchild!=null)//若左子存在,查其在靜態(tài)鏈表中的下標(biāo)，填lchild域值{lch=Locate(p->lchild->data)；st[i].lchild=lch;//下標(biāo)填入“靜態(tài)鏈表”qbt.t=p->lchild;qbt.idx=lch;QueueIn(Q,qbt);}elsest[i].lchild=0;//無(wú)左子，其lchild域填0if(p-〉rchild!=null)//若右子存在，查其在靜態(tài)鏈表中的下標(biāo)，填rchild域值{rch=Locate(p->->rchild->data)；st[i].rchild=rch;qbt.t=p->rchild;qbt.idx=rch;QueueIn(Q,qbt);}elsest[i].rchild=0;//無(wú)右子，其lchild域填0}//while}//結(jié)束DynaToST49.二叉樹(shù)按完全二叉樹(shù)格式輸入，對(duì)非完全二叉樹(shù)，要補(bǔ)上“虛結(jié)點(diǎn)”。按完全二叉樹(shù)雙親和子女存儲(chǔ)下標(biāo)間的關(guān)系，完成雙親和子女間指針的鏈接。‘#'是輸入結(jié)束標(biāo)志，‘$'是虛結(jié)點(diǎn)標(biāo)志。BiTreecreat()//生成三叉鏈表的二叉樹(shù){BiTreep,Q[]，root;//Q是二叉樹(shù)結(jié)點(diǎn)指針的一維數(shù)組，容量足夠大charch;intrear=0;//一維數(shù)組最后元素的下標(biāo)scanf(&ch);while(ch!=‘#'){p=null;if(ch!=‘$'){p=(BiTree)malloc(sizeof(nodetp));p->data=ch;p->lchild=p->rchild=null;}Q[++rear]=p;//元素或虛結(jié)點(diǎn)if(p){if(rear==1){root=p;root->parent=null;}//根結(jié)點(diǎn)else{//雙親結(jié)點(diǎn)和子女結(jié)點(diǎn)用指針鏈上Q[rear]->parent=Q[rear/2];if(rear%2==0)Q[rear/2]->lchild=Q[rear];elseQ[rear/2]->rchild=Q[rear];}}scanf(“%c”,&ch);}//whilereturn(root);}//結(jié)束creat★★高度深度算法★★8.二叉樹(shù)高度可遞歸計(jì)算如下：若二叉樹(shù)為空，則高度為零，否則，二叉樹(shù)的高度等于左右子樹(shù)高度的大者加1。這里二叉樹(shù)為空的標(biāo)記不是null而是0。設(shè)根結(jié)點(diǎn)層號(hào)為1,則每個(gè)結(jié)點(diǎn)的層號(hào)等于其雙親層號(hào)加1?，F(xiàn)將二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)定義如下:typedefstructnode{intL[];//編號(hào)為i的結(jié)點(diǎn)的左兒子intR[];//編號(hào)為i的結(jié)點(diǎn)的右兒子intD[];//編號(hào)為i的結(jié)點(diǎn)的層號(hào)inti;//存儲(chǔ)結(jié)點(diǎn)的順序號(hào)(下標(biāo))}tnode;intHeight(tnodet,inti)//求二叉樹(shù)高度，調(diào)用時(shí)i=1{intlh,rh;if(i==0)return(0);else{lh=Height(t,t.L[i]);4rh=Height(t,t.R[i]);if(lh>rh)return(lh+1);elsereturn(rh+1);}}//結(jié)束HeightintLevel(tnodet)//求二叉樹(shù)各結(jié)點(diǎn)的層號(hào)，已知編號(hào)為1的結(jié)點(diǎn)是根，且層號(hào)為1{t.D[1]=1;for(i=1;i<=n;i++){depth=t.D[i]；//取出根結(jié)點(diǎn)層號(hào)if(t.L[i]!=0)t.D[t.L[i]]=depth+1;//i結(jié)點(diǎn)左兒子層號(hào)if(t.R[i]!=0)t.D[t.R[i]]=depth+1;}//i結(jié)點(diǎn)右兒子層號(hào)}結(jié)束levelintHeight(btrebt)//遞歸求二叉鏈表二叉樹(shù)bt的深度{inthl,hr;if(bt==null)return(0);else{hl=Height(bt->lch);hr=Height(bt->rch);if(hl>hr)return(hl+1);elsereturn(hr+1);}}14．由孩子兄弟鏈表表示的樹(shù)，求高度的遞歸模型是：若樹(shù)為空，高度為零；若第一子女為空，高度為1和兄弟子樹(shù)的高度的大者；否則，高度為第一子女樹(shù)高度加1和兄弟子樹(shù)高度的大者。其非遞歸算法使用隊(duì)列，逐層遍歷樹(shù)，取得樹(shù)的高度。?intHeight(CSTreebt)//遞歸求以孩子兄弟鏈表表示的樹(shù)的深度{inthc,hs;if(bt==null)return(0);elseif(!bt->firstchild)return(1+height(bt->nextsibling));//子女空，查兄弟的深度else//結(jié)點(diǎn)既有第一子女又有兄弟，高度取子女高度+1和兄弟子樹(shù)高度的大者{hc=height(bt->firstchild)；//第一子女樹(shù)高h(yuǎn)s=height(bt-〉nextsibling)；//兄弟樹(shù)高if(hc+1>hs)return(hc+1);elsereturn(hs);}}//結(jié)束height?intheight(CSTreet)//非遞歸遍歷求以孩子兄弟鏈表表示的樹(shù)的深度{if(t==null)return(0);else{intfront=1,rear=1;//front,rear是隊(duì)頭隊(duì)尾元素的指針intlast=l,h=O;//last指向樹(shù)中同層結(jié)點(diǎn)中最后一個(gè)結(jié)點(diǎn)，h是樹(shù)的高度Q[rear]=t;//Q是以樹(shù)中結(jié)點(diǎn)為元素的隊(duì)列while(front<=last){t=Q[front++];//隊(duì)頭出列while(t!=null)//層次遍歷{if(t->firstchild)Q[++rear]=t->firstchild;//第一子女入隊(duì)t=t->nextsibling;//同層兄弟指針后移}if(front>last)//本層結(jié)束，深度加1(初始深度為0){h++;last=rear;}//last再移到指向當(dāng)前層最右一個(gè)結(jié)點(diǎn)}//while(front<=last)}//else}//Height11.由于以雙親表示法作樹(shù)的存儲(chǔ)結(jié)構(gòu)，找結(jié)點(diǎn)的雙親容易。因此我們可求出每一結(jié)點(diǎn)的層次，取其最大層次就是樹(shù)有深度。對(duì)每一結(jié)點(diǎn)，找其雙親，雙親的雙親，直至(根)結(jié)點(diǎn)雙親為0為止。intDepth(Ptreet)//求以雙親表示法為存儲(chǔ)結(jié)構(gòu)的樹(shù)的深度{intmaxdepth=0;for(i=1;i<=t.n;i++)//n為葉子結(jié)點(diǎn)個(gè)數(shù){temp=0;f=i;while(f>0){temp++;f=t.nodes[f].parent;}//深度加1,并取新的雙親if(temp>maxdepth)maxdepth=temp;//最大深度更新}return(maxdepth);//返回樹(shù)的深度}//結(jié)束Depth13．求最大寬度可采用層次遍歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。5intWidth(BiTreebt)//求二叉樹(shù)bt的最大寬度{if(bt==null)return(0);//空二叉樹(shù)寬度為0else{BiTreeQ[];//Q是隊(duì)列，元素為二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大front=l;rear=1;last=1;//front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置temp=0;maxw=0;//temp記局部寬度,maxw記最大寬度Q[rear]=bt;//根結(jié)點(diǎn)入隊(duì)列while(front<=last){p=Q[front++];temp++;//同層元素?cái)?shù)加1if(p->lchild!=null)Q[++rear]=p->lchild;//左子女入隊(duì)if(p->rchild!=null)Q[++rear]=p->rchild;//右子女入隊(duì)if(front>last)//一層結(jié)束，{last=rear;if(temp>maxw)maxw=temp;//last指向下層最右元素,更新當(dāng)前最大寬度temp=0;}//if}//whilereturn(maxw);}//結(jié)束width★★后序遍歷算法★★36.二叉樹(shù)結(jié)點(diǎn)p所對(duì)應(yīng)子樹(shù)的第一個(gè)后序遍歷結(jié)點(diǎn)q的求法如下：若p有左子樹(shù)，貝Uq是p的左子樹(shù)上最左下的葉子結(jié)點(diǎn)；若P無(wú)左子樹(shù)，僅有右子樹(shù)，則q是P的右子樹(shù)上最左下的葉子結(jié)點(diǎn)。BiTreePostFirst(p){BiTreeq=p;if(!q)return(null);elsewhile(q->lchild||q->rchild);//找最左下的葉子結(jié)點(diǎn)if(q->lchild)q=q->lchild;//優(yōu)先沿左分枝向下去查“最左下”的葉子結(jié)點(diǎn)elseq=q->rchild;//沿右分枝去查“最左下”的葉子結(jié)點(diǎn)return(q);}[算法討論]題目“求p所對(duì)應(yīng)子樹(shù)的第一個(gè)后序遍歷結(jié)點(diǎn)”，蘊(yùn)涵p是子樹(shù)的根。若p是葉子結(jié)點(diǎn)，求其后繼要通過(guò)雙親。18?后序遍歷最后訪問(wèn)根結(jié)點(diǎn)，當(dāng)訪問(wèn)到值為x的結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。voidSearch(BiTreebt,ElemTypex)//在二叉樹(shù)bt中，查找值為x的結(jié)點(diǎn)，并打印其所有祖先{typedefstruct{BiTreet;inttag;}stack;//tag=0表示左子女被訪問(wèn)，tag=1表示右子女被訪問(wèn)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”)；//找到xfor(i=1;i<=top;i++)printf(s[i].t->data);return;}//輸出祖先值后結(jié)束?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)}結(jié)束search因?yàn)椴檎业倪^(guò)程就是后序遍歷的過(guò)程，使用的棧的深度不超過(guò)樹(shù)的深度，算法復(fù)雜度為O(logn)。15.后序遍歷最后訪問(wèn)根結(jié)點(diǎn)，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹(shù)結(jié)點(diǎn)的指針，當(dāng)訪問(wèn)到某結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。本題要找p和q的最近共同祖先結(jié)點(diǎn)r,不失一般性，設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點(diǎn)p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點(diǎn)1時(shí)，將棧中元素從棧頂開(kāi)始逐個(gè)到輔助棧中去匹配，第一個(gè)匹配(即相等)的元素就是結(jié)點(diǎn)P和q的最近公共祖先。typedefstruct{BiTreet;inttag;//tag=0表示結(jié)點(diǎn)的左子女已被訪問(wèn)，tag=1表示結(jié)點(diǎn)的右子女已被訪問(wèn)}stack;stacks[],sl[];//棧，容量夠大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹(shù)上結(jié)點(diǎn)p和q的最近的共同祖先結(jié)點(diǎn)r。{top=0;bt=ROOT;6while(bt!=null||top>0){while(bt!=null&&bt!=p&&bt!=q)//結(jié)點(diǎn)入棧{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下if(bt==p)//不失一般性，假定p在q的左側(cè)，遇結(jié)點(diǎn)p時(shí)，棧中元素均為p的祖先結(jié)點(diǎn){for(i=l;i〈=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉(zhuǎn)入輔助棧si保存if(bt==q)//找到q結(jié)點(diǎn)。for(i=top;i〉0;i—)//；將棧中元素的樹(shù)結(jié)點(diǎn)到si去匹配{pp=s[i].t;for(j=topi;j>0;j--)if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}}while(top!=0&&s[top].tag==i)top--;//退棧if(top!=0){s[top].tag=i;bt=s[top].t->rchild;}//沿右分枝向下遍歷}//結(jié)束while(bt!=null||top>0)return(null);//q、p無(wú)公共祖先}//結(jié)束Ancestor16.二叉樹(shù)順序存儲(chǔ)，是按完全二叉樹(shù)的格式存儲(chǔ)，利用完全二叉樹(shù)雙親結(jié)點(diǎn)與子女結(jié)點(diǎn)編號(hào)間的關(guān)系，求下標(biāo)為i和j的兩結(jié)點(diǎn)的雙親，雙親的雙親，等等，直至找到最近的公共祖先。voidAncestor(ElemTypeA[],intn,i,j)//二叉樹(shù)順序存儲(chǔ)在數(shù)組A[1..n]中，本算法求下標(biāo)分別為i和j的結(jié)點(diǎn)的最近公共祖先結(jié)點(diǎn)的值。{while(i!=j)if(i>j)i=i/2;//下標(biāo)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)elsej=j/2;//下標(biāo)為j的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)printf(“所查結(jié)點(diǎn)的最近公共祖先的下標(biāo)是%4，值是%d",i,A[i]);//設(shè)元素類型整型。}//Ancestor48.刪除以元素值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ù){DeleteXTree(bt->lchild);DeleteXTree(bt->rchild);//刪除bt的左子樹(shù)、右子樹(shù)free(bt);}//DeleteXTree//釋放被刪結(jié)點(diǎn)所占的存儲(chǔ)空間?voidSearch(B:Treebt,ElemTypex)//在二叉樹(shù)上查找所有以x為元素值的結(jié)點(diǎn)，并刪除以其為根的子樹(shù){BiTreeQ[];//Q是存放二叉樹(shù)結(jié)點(diǎn)指針的隊(duì)列，容量足夠大if(bt){if(bt-〉data==x){DeleteXTree(bt);exit(O);}//若根結(jié)點(diǎn)的值為x,則刪除整棵樹(shù){QueueInit(Q);QueueIn(Q,bt);while(!QueueEmpty(Q)){p=QueueOut(Q);if(p->lchild)//若左子女非空if(p-〉lchild-〉data==x)//左子女結(jié)點(diǎn)值為x,應(yīng)刪除當(dāng)前結(jié)點(diǎn)的左子樹(shù){DeleteXTree(p->lchild);p->lchild=null;}//父結(jié)點(diǎn)的左子女置空elseEnqueue(Q,p->lchild);//左子女入隊(duì)列if(p->rchild)//若右子女非空if(p-〉rchild-〉data==x)//右子女結(jié)點(diǎn)值為x,應(yīng)刪除當(dāng)前結(jié)點(diǎn)的右子樹(shù){DeleteXTree(p->rchild);p->rchild=null;}//父結(jié)點(diǎn)的右子女置空elseEnqueue(Q,p->rchild);//右子女入隊(duì)列}//while}//if(bt)}//search55.每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，結(jié)點(diǎn)左孩子的編號(hào)小于右孩子的編號(hào)。由此看出，從小到大按“左右根”順序，這正是后序遍序的順序，故對(duì)二叉樹(shù)進(jìn)行后序遍歷，在遍歷中對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，現(xiàn)將二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedefstructnode{ElemTypedata;intnum;structnode*lchild,*rchild;}Bnode,*Btree；voidPostOrder(Btreet)//對(duì)二叉樹(shù)從1開(kāi)始編號(hào)，結(jié)點(diǎn)編號(hào)大于其左右子女結(jié)點(diǎn)編號(hào)，結(jié)點(diǎn)的左子女編號(hào)小于其右子女編號(hào){typedefstruct{Btreet;inttag;}node;7Btreep=t;nodesn,s[];//s為棧，容量足夠大intk=0,top=0;//k為結(jié)點(diǎn)編號(hào)，top為棧頂指針while(p!=null||top>0){while(p){sn.t=p;sn.tag=0;s[++top]=sn;p=p->lchild;}//沿左分枝向下while(top〉0&&s[top].tag==l){sn=s[top—];sn.t-〉num=++k;}//左右孩子已遍歷，結(jié)點(diǎn)賦編號(hào)if(top>0){s[top].tag=1;p=s[top].t->rchild;}}//while(p!=null||top>0)}結(jié)束PostOrder采用后序非遞歸遍歷二叉樹(shù)，棧中保留從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。voidPrintPath(BiTreebt,p)//打印從根結(jié)點(diǎn)bt到結(jié)點(diǎn)p之間路徑上的所有結(jié)點(diǎn){BiTreeq=bt,s[];//s是元素為二叉樹(shù)結(jié)點(diǎn)指針的棧，容量足夠大inttop=0;tag[];//tag是數(shù)組，元素值為0或1,訪問(wèn)左、右子樹(shù)的標(biāo)志，tag和s同步if(q==p){printf(q->data);return;}//根結(jié)點(diǎn)就是所找結(jié)點(diǎn)while(q!=null||top>0){★while(q!=null)//左子入棧，并置標(biāo)記if(q==P)//找到結(jié)點(diǎn)P，棧中元素均為結(jié)點(diǎn)P的祖先{printf(“從根結(jié)點(diǎn)到p結(jié)點(diǎn)的路徑為\n”);for(i=1;i<=toP;i++)Printf(s[i]->data);printf(q->data);return;}else{s[++top]=q;tag[top]=0;q=q->lchild;}//沿左分支向下★while(top>0&&tag[top]==1))top--；//本題不要求輸出遍歷序列，這里只退?！飅f(top>0){q=s[top];q=q->rchild;tag[top]=1;}//沿右分支向下}//while(q!=null||top>0)}//結(jié)束算法PrintPath打印由根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的所有路徑。只要在58基礎(chǔ)上把q是否等于p的判斷改為q是否是葉子結(jié)點(diǎn)即可。其語(yǔ)句段如下：if(q->lchild==null&&q->rchild==null)//q為葉子結(jié)點(diǎn){printf(“從根結(jié)點(diǎn)到p結(jié)點(diǎn)的路徑為\n”);for(i=l;i〈=top;i++)printf(s[i]-〉data);//輸出從根到葉子路徑上，葉子q的所有祖先printf(q->data);}因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)，則將該棧倒入輔助棧中，輔助棧始終保存最長(zhǎng)路徑長(zhǎng)度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。voidLongestPath(BiTreebt)//求二叉樹(shù)中的第一條最長(zhǎng)路徑長(zhǎng)度{BiTreep=bt,l[],s[];//l,s是棧，元素是二叉樹(shù)結(jié)點(diǎn)指針，l中保留當(dāng)前最長(zhǎng)路徑中的結(jié)點(diǎn)inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//當(dāng)前結(jié)點(diǎn)的右分枝已遍歷{if(!s[top]->Lc&&!s[top]->Rc)//只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長(zhǎng)度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;}//保留當(dāng)前最長(zhǎng)路徑到l棧，記住最高棧頂指針，退棧}elseif(top>0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while(p!=null||top>0)}//結(jié)束LongestPath★★先序遍歷算法★★二叉樹(shù)的順序存儲(chǔ)是按完全二叉樹(shù)的順序存儲(chǔ)格式，雙親與子女結(jié)點(diǎn)下標(biāo)間有確定關(guān)系。對(duì)順序存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)進(jìn)行遍歷，與二叉鏈表類似。在順序存儲(chǔ)結(jié)構(gòu)下，判二叉樹(shù)為空時(shí)，用結(jié)點(diǎn)下標(biāo)大于n(完全二叉樹(shù))或0(對(duì)一般二叉樹(shù)的“虛結(jié)點(diǎn)”)voidPreOrder(ElemTypebt,intn)//對(duì)以順序結(jié)構(gòu)存儲(chǔ)的完全二叉樹(shù)bt進(jìn)行先序遍歷{inttop=0,s[];//top是棧s的棧頂指針，棧容量足夠大while(i<=n||top>0){while(i<=n){printf(bt[i]);//訪問(wèn)根結(jié)點(diǎn)；if(2*i+1<=n)s[++top]=2*i+1;//右子女的下標(biāo)位置進(jìn)棧i=2*i;}//沿左子女向下if(top>0)i=s[top--];}//取出棧頂元素}//結(jié)束PreOrder19.先序遍歷二叉樹(shù)的非遞歸算法，要求進(jìn)棧元素少，意味著空指針不進(jìn)棧。8voidPreOrder(Bitreebt)//對(duì)二叉數(shù)bt進(jìn)行非遞歸先序遍歷{inttop=0;Bitrees[];//top是棧s的棧頂指針，棧中元素是樹(shù)結(jié)點(diǎn)指針，棧容量足夠大while(bt!=null||top>0){while(bt!=null){printf(bt->data);//訪問(wèn)根結(jié)點(diǎn)if(bt->rchlid)s[++top]=bt->rchild;//若有右子女，則右子女進(jìn)棧bt=bt->lchild;}if(top>0)bt=s[top--];}}//本題中的二叉樹(shù)中需進(jìn)棧的元素有C,H,K,F。本題使用的存儲(chǔ)結(jié)構(gòu)是一種雙親表示法，對(duì)每個(gè)結(jié)點(diǎn)，直接給出其雙親(的下標(biāo))，而且用正或負(fù)表示該結(jié)點(diǎn)是雙親的右子女或左子女。該類結(jié)構(gòu)不適于直接進(jìn)行前序遍歷(即若直接前序遍歷，算法要很復(fù)雜)，較好的辦法是將這類結(jié)構(gòu)轉(zhuǎn)為結(jié)點(diǎn)及其左右子女的順序存儲(chǔ)結(jié)構(gòu)，即Tree2=ARRAY[1..max]OFRECORDdata:char;//結(jié)點(diǎn)數(shù)據(jù)lc,rc:integer;END;//結(jié)點(diǎn)的左右子女在數(shù)組中的下標(biāo)?voidChange(Treet,Tree2bt,int*root)//先將t轉(zhuǎn)為如上定義類型的變量bt;{for(i=1;i<=max;i++){bt[i].lc=bt[i].rc=0;}//先將結(jié)點(diǎn)的左右子女初始化為0for(i=1;i<=max;i++)//填入結(jié)點(diǎn)數(shù)據(jù)，和結(jié)點(diǎn)左右子女的信息{bt[i].data=t[i].data;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記住根結(jié)點(diǎn)}}//change?voidPreOrder(Tree2bt)//對(duì)二叉樹(shù)進(jìn)行前序非遞歸遍歷{int*root,top=0;ints[];//s是棧change(t,bt,root);inti=*root;while(i!=0||top>0){while(i!=0){printf(bt[i].data)；if(bt[i].rc!=0)s[++top]=bt[i].rc;//右子進(jìn)棧i=bt[i].lc;}if(top>0)i=s[top--];}}//結(jié)束preorder[算法討論]本題的前序遞歸算法如下?voidPreOrder(introot)//root是二叉樹(shù)根結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)，本算法前序遍歷二叉樹(shù)bt{if(root!=0){printf(bt[root].data);//訪問(wèn)根結(jié)點(diǎn)PreOrder(bt[root].lc);//前序遍歷左子樹(shù)PreOrder(bt[root].rc);//前序遍歷右子樹(shù)}}//結(jié)束preorder，初始調(diào)用時(shí)，root是根結(jié)點(diǎn)的下標(biāo)當(dāng)給定數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)不合適時(shí)，可由已給結(jié)構(gòu)來(lái)構(gòu)造好的數(shù)據(jù)結(jié)構(gòu)，以便于運(yùn)算。22．二叉樹(shù)先序序列的最后一個(gè)結(jié)點(diǎn)，若二叉樹(shù)有右子樹(shù)，則是右子樹(shù)中最右下的葉子結(jié)點(diǎn)；若無(wú)右子樹(shù)僅有左子樹(shù)，則是左子樹(shù)最右下的葉子結(jié)點(diǎn)；若二叉樹(shù)無(wú)左右子樹(shù)，則返回根結(jié)點(diǎn)。BiTreeLastNode(BiTreebt)//返回二叉樹(shù)bt先序序列的最后一個(gè)結(jié)點(diǎn)的指針{BiTreep=bt;if(bt==null)return(null);elsewhile(p){if(p->rchild)p=p->rchild;//若右子樹(shù)不空，沿右子樹(shù)向下elseif(p->lchild)p=p->lchild;//右子樹(shù)空，左子樹(shù)不空，沿左子樹(shù)向下elsereturn(p);//無(wú)左右子樹(shù)，p即為所求}}//結(jié)束lastnode高度為K的二叉樹(shù)，按順序方式存儲(chǔ)，要占用2k-1個(gè)存儲(chǔ)單元，與實(shí)際結(jié)點(diǎn)個(gè)數(shù)n關(guān)系不大，對(duì)不是完全二叉樹(shù)的二叉樹(shù)，9要增加“虛結(jié)點(diǎn)”，使其在形態(tài)上成為完全二叉樹(shù)。intm=2K-1;//全局變量voidPreOrder(ElemTypebt[],i)//遞歸先序遍歷以順序方式存儲(chǔ)的二叉樹(shù)bt，i是根結(jié)點(diǎn)下標(biāo)(初始調(diào)用時(shí)為1)。{if(i<=m)//設(shè)虛結(jié)點(diǎn)以0表示{printf(bt[i])；//訪問(wèn)根結(jié)點(diǎn)if(2*i<=m&&bt[2*i]!=0)PreOrder(bt,2*i);//先序遍歷左子樹(shù)if(2*i+1<=m&&bt[2*i+1]!=0)PreOrder(bt,2*i+1);//先序遍歷右子樹(shù)}}//結(jié)束PreOrder二叉樹(shù)中最大序號(hào)的葉子結(jié)點(diǎn),是在順序存儲(chǔ)方式下編號(hào)最大的結(jié)點(diǎn)voidAncesstor(ElemTypebt[])//打印最大序號(hào)葉子結(jié)點(diǎn)的全部祖先{c=m;while(bt[c]==0)c--;//找最大序號(hào)葉子結(jié)點(diǎn),該結(jié)點(diǎn)存儲(chǔ)時(shí)在最后f=c/2;//c的雙親結(jié)點(diǎn)fwhile(f!=0)//從結(jié)點(diǎn)c的雙親結(jié)點(diǎn)直到根結(jié)點(diǎn)，路徑上所有結(jié)點(diǎn)均為祖先結(jié)點(diǎn){printf(bt[f]);f=f/2;}//逆序輸出，最老的祖先最后輸出}//結(jié)束voidexchange(BiTreebt)//將二叉樹(shù)bt所有結(jié)點(diǎn)的左右子樹(shù)交換，先序遍歷遞歸{if(bt){BiTrees；s=bt->lchild;bt->lchild=bt->rchild;bt->rchild=s;//左右子女交換exchange(bt->lchild);//交換左子樹(shù)上所有結(jié)點(diǎn)的左右子樹(shù)exchange(bt->rchild);//交換右子樹(shù)上所有結(jié)點(diǎn)的左右子樹(shù)}}[算法討論]將上述算法中兩個(gè)遞歸調(diào)用語(yǔ)句放在前面，將交換語(yǔ)句放在最后，則是以后序遍歷方式交換所有結(jié)點(diǎn)的左右子樹(shù)。中序遍歷不適合本題。下面是非遞歸算法(1)voidexchange(BiTreet)//交換二叉樹(shù)中各結(jié)點(diǎn)的左右孩子的非遞歸算法{inttop=0;BiTrees[],p;//s是二叉樹(shù)的結(jié)點(diǎn)指針的棧，容量足夠大if(bt){s[++top]=t;while(top>0){t=s[top--];if(t->lchild||t->rchild){p=t->lchild;t->lchild=t->rchild;t->rchild=p;}//交換if(t->lchild)s[++top]=t->lchild;//左子女入棧if(t->rchild)s[++top]=t->rchild;//右子女入棧}//while(top>0)}//if(bt)}//結(jié)束exchange★★中序遍歷算法★★voidInOrder(BiTreebt)//中序遍歷非遞歸{BiTrees[],p=bt;//s是元素為二叉樹(shù)結(jié)點(diǎn)指針的棧，容量足夠大inttop=0;while(p||top>0){while(p){s[++top]=p;bt=p->lchild;}//中序遍歷左子樹(shù)if(top>0){p=s[top--];printf(p->data);p=p->rchild;}//退棧，訪問(wèn)，轉(zhuǎn)右子樹(shù)}}二叉樹(shù)用順序方式存儲(chǔ)，其遍歷方法與用二叉鏈表方式存儲(chǔ)類似。判空時(shí)，在二叉鏈表方式下用結(jié)點(diǎn)指針是否等于null，在順序存儲(chǔ)方式下，一是下標(biāo)是否是“虛結(jié)點(diǎn)”，二是下標(biāo)值是否超過(guò)最大值(高為H的二叉樹(shù)要有2宙1個(gè)存儲(chǔ)單元，與實(shí)際結(jié)點(diǎn)個(gè)數(shù)關(guān)系不大)。順序存儲(chǔ)方式下，要告訴根結(jié)點(diǎn)的下標(biāo)。voidInOrder(inti)//對(duì)順序存儲(chǔ)的二叉樹(shù)進(jìn)行中序遞歸遍歷，i是根結(jié)點(diǎn)的下標(biāo){if(i!=0){InOrder(ar[i].Lc);//中序遍歷左子樹(shù)printf(ar[i].data);//訪問(wèn)根結(jié)點(diǎn)InOrder(ar[i].Rc);//中序遍歷右子樹(shù)}}//結(jié)束InOrder35.BiTreecreat()//生成并中序輸出二叉排序樹(shù){scanf(“%c”,&ch);//ch是二叉排序樹(shù)結(jié)點(diǎn)值的類型變量，假定是字符變量BiTreebst=null,f=null;while(ch!=‘#')//‘#'是輸入結(jié)束標(biāo)記10{s=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)s->data=ch;s->lchild=s->rchild=null;if(bst==null)bst=s;//根結(jié)點(diǎn)else//查找插入結(jié)點(diǎn){p=bst;while(p)if(ch〉p-〉data){f=p;p=p-〉rchild;}//沿右分枝查,f是雙親else{f=p;p=p->lchild;}//沿左分枝查if(f->data<ch)f->rchild=s;elsef->lchild=s;//將s結(jié)點(diǎn)插入樹(shù)中}scanf(“%c”,&ch);//讀入下一數(shù)據(jù)}//while(ch!=‘#')return(bst);}//結(jié)束creatvoidInOrder(BiTreebst)//bst是二叉排序樹(shù)，中序遍歷輸出二叉排序樹(shù){if(bst){InOrder(bst->lchild);printf(bst->data);InOrder(bst->rchild);}}//結(jié)束InOrder41?葉子結(jié)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre,初始為空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkedListhead,pre=null;//全局變量LinkedListInOrder(BiTreebt)//中序遍歷二叉樹(shù)bt，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head{if(bt){InOrder(bt->lchild);//中序遍歷左子樹(shù)if(bt->lchild==null&&bt->rchild==null)//葉子結(jié)點(diǎn)if(pre==null){head=bt;pre=bt;}//處理第一個(gè)葉子結(jié)點(diǎn)else{pre->rchild=bt;pre=bt;}//將葉子結(jié)點(diǎn)鏈入鏈表InOrder(bt->rchild);//中序遍歷右子樹(shù)pre->rchild=null;//設(shè)置鏈表尾}return(head);}//InOrder時(shí)間復(fù)雜度為O(n)，輔助變量使用head和pre,?？臻g復(fù)雜度O(n)★★層次遍歷算法★★voidInvertLevel(biTreebt)//對(duì)二叉樹(shù)按自下至上，自右至左的進(jìn)行層次遍歷{if(bt!=null){StackInit(s);//棧初始化，棧中存放二叉樹(shù)結(jié)點(diǎn)的指針QueueInit(Q);//隊(duì)列初始化。隊(duì)列中存放二叉樹(shù)結(jié)點(diǎn)的指針QueueIn(Q,bt);while(!QueueEmpty(Q))//從上而下層次遍歷{p=QueueOut(Q);push(s,p);//出隊(duì),入棧if(p->lchild)QueueIn(Q,p->lchild);//若左子不空，則入隊(duì)列if(p->rchild)QueueIn(Q,p->rchild);//若右子不空，則入隊(duì)列}while(!StackEmpty(s)){p=pop(s);printf(p->data);}//自下而上,從右到左的層次遍歷}//if(bt!=null)}//結(jié)束InvertLevel借助隊(duì)列和棧，最后彈出棧中元素實(shí)現(xiàn)對(duì)二叉樹(shù)按自下至上，自右至左的層次遍歷33.計(jì)算每層中結(jié)點(diǎn)值大于50的結(jié)點(diǎn)個(gè)數(shù)，應(yīng)按層次遍歷。設(shè)一隊(duì)列Q,用front和rear分別指向隊(duì)頭和隊(duì)尾元素，last指向各層最右結(jié)點(diǎn)的位置。存放值大于50的結(jié)點(diǎn)結(jié)構(gòu)為typedefstruct{intlevel,value,idx;}node;//元素所在層號(hào)、值和本層中的序號(hào)nodea[],s;voidValueGT50(BiTreebt)//查各層中結(jié)點(diǎn)值大于50的結(jié)點(diǎn)個(gè)數(shù)，輸出其值及序號(hào){if(bt!=null){intfront=0,last=1,rear=1,level=1,i=0,num=0;//num記>50的結(jié)點(diǎn)個(gè)數(shù)BiTreeQ[];Q[1]=bt;//根結(jié)點(diǎn)入隊(duì)while(front<=last){bt=Q[++front];if(bt->data>50){s.level=level;s.idx=++i;s.value=bt->data;a[++num]=s;}if(bt->lchild!=null)Q[++rear]=bt->lchild;//左子女入隊(duì)列if(bt->rchild!=null)Q[++rear]=bt->rchild;//右子女入隊(duì)列11if(front==last){last=rear;level++;i=0;}//本層最后一個(gè)結(jié)點(diǎn)已處理完}//初始化下層：last指向下層最右結(jié)點(diǎn)，層號(hào)加1,下層>50的序號(hào)初始為0for(i=l;i〈=num;i++)//輸出data域數(shù)值大于50的結(jié)點(diǎn)的層號(hào)、data域的數(shù)值和序號(hào)printf(“層號(hào)=%3d，本層序號(hào)=%3d，值=%3d"，a[i].level,a[i].idx,a[i].value);}}//算法ValueGT50結(jié)束54.對(duì)二叉樹(shù)的某層上的結(jié)點(diǎn)進(jìn)行運(yùn)算，采用隊(duì)列結(jié)構(gòu)按層次遍歷最適宜。intLeafKlevel(BiTreebt,intk)//求二叉樹(shù)bt的第k(k>1)層上葉子結(jié)點(diǎn)個(gè)數(shù){if(bt==null||k<1)return(0);BiTreep=bt,Q[];//Q是隊(duì)列，元素是二叉樹(shù)結(jié)點(diǎn)指針,容量足夠大intfront=0,rear=1,leaf=0;//front和rear是隊(duì)頭和隊(duì)尾指針，leaf是葉子結(jié)點(diǎn)數(shù)intlast=1,level=1;Q[1]=p;//last是二叉樹(shù)同層最右結(jié)點(diǎn)的指針，level是二叉樹(shù)的層數(shù)while(front<=rear){p=Q[++front];if(level==k&&!p->lchild&&!p->rchild)leaf++;//葉子結(jié)點(diǎn)if(p->lchild)Q[++rear]=p->lchild;//左子女入隊(duì)if(p->rchild)Q[++rear]=p->rchild;//右子女入隊(duì)if(front==last){level++;//二叉樹(shù)同層最右結(jié)點(diǎn)已處理,層數(shù)增1last=rear;}//last移到指向下層最右一元素if(level>k)return(leaf);//層數(shù)大于k后退出運(yùn)行}//while}//結(jié)束LeafKLevel45?本題應(yīng)采用層次遍歷方式。若樹(shù)不空，則二叉樹(shù)根結(jié)點(diǎn)入隊(duì)，然后當(dāng)隊(duì)列不空且隊(duì)列長(zhǎng)不超過(guò)n,重復(fù)如下操作：出隊(duì)，若出隊(duì)元素不為空，則記住其下標(biāo)，且將其左右子女入隊(duì)列；若出隊(duì)元素為空，當(dāng)作虛結(jié)點(diǎn)，也將其“虛子女”入隊(duì)列。為節(jié)省空間，就用樹(shù)T的順序存儲(chǔ)結(jié)構(gòu)A[l..n]作隊(duì)列，隊(duì)頭指針front,隊(duì)尾指針rear，元素最大下標(biāo)last.voidTraverse(BiTreebt,intn)//求二叉樹(shù)bt的順序存儲(chǔ)結(jié)構(gòu)A[l..n],下標(biāo)超過(guò)n報(bào)錯(cuò)，給出實(shí)際的最大下標(biāo){BiTreeA[],p;if(bt!=null){intfront=0,rear=1,last=1;A[1]=bt;while(front<=rear){p=A[++front];if(p)last=front;//出隊(duì);用last記住最后一個(gè)結(jié)點(diǎn)的下標(biāo)rear=2*front;//計(jì)算結(jié)點(diǎn)(包括虛結(jié)點(diǎn))“左子"下標(biāo)▲if(p)//二叉樹(shù)的實(shí)際結(jié)點(diǎn){if(rear>n)printf(“%c結(jié)點(diǎn)無(wú)左子”);elseA[rear]=p->lchild;if(rear+1>n)printf(“%c結(jié)點(diǎn)無(wú)右子”);elseA[rear+1]=p->rchild;}▲else//p是虛結(jié)點(diǎn){if(rear<=n)A[rear]=null;if(rear+1<=n)A[rear+1]=null;}}//while(front<=rear)printf(“實(shí)際的最大下標(biāo)是%d",last);}//if(bt!=null)}//TraverseintLevel(BiTreebt)//層次遍歷二叉樹(shù)，并統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù){intnum=0;//num統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù)if(bt){QueueInit(Q);QueueIn(Q,bt)；//Q是以二叉樹(shù)結(jié)點(diǎn)指針為元素的隊(duì)列while(!QueueEmpty(Q)){p=QueueOut(Q);printf(p->data);//出隊(duì),訪問(wèn)結(jié)點(diǎn)if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度為1的結(jié)點(diǎn)if(p->lchild)QueueIn(Q,p->lchild);//非空左子入隊(duì)if(p->rchild)QueueIn(Q,p->rchild);//非空右子入隊(duì)}}//if(bt)return(num);}//返回度為1的結(jié)點(diǎn)的個(gè)數(shù)★★先序轉(zhuǎn)為后序算法**對(duì)一般二叉樹(shù)，僅根據(jù)一個(gè)先序、中序、后序遍歷，不能確定另一個(gè)遍歷序列。但對(duì)于滿二叉樹(shù)，任一結(jié)點(diǎn)的左右子樹(shù)均含12有數(shù)量相等的結(jié)點(diǎn)，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列(即任一遍歷序列均可確定一棵二叉樹(shù))。voidPreToPost(ElemTypepre[],post[],intl1,h1,l2,h2)//將滿二叉樹(shù)的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點(diǎn)的下標(biāo)。{if(h1>=l1){post[h2]=pre[l1];//根結(jié)點(diǎn)half=(h1-l1)/2;//左或右子樹(shù)的結(jié)點(diǎn)數(shù)PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)//將左子樹(shù)先序序列轉(zhuǎn)為后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)//將右子樹(shù)先序序列轉(zhuǎn)為后序序列}}//PreToPost★★中序后序算法★★BiTreeIntoPost(ElemTypein[],post[],intl1,h1,l2,h2)//in和post是二叉樹(shù)的中序序列和后序序列遞歸，ll,hl,l2,h2分別是兩序列第一和最后結(jié)點(diǎn)的下標(biāo){BiTreebt=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)bt->data=post[h2];//后序遍歷序列最后一個(gè)元素是根結(jié)點(diǎn)數(shù)據(jù)for(i=l1;i<=h1;i++)if(in[i]==post[h2])break;//在中序序列中查找根結(jié)點(diǎn)if(i==l1)bt->lchild=null;//處理左子樹(shù)elsebt->lchild=IntoPost(in,post,i1,i-1,l2,l2+i-l1-1)；if(i==h1)bt->rchild=null;//處理右子樹(shù)elsebt->rchild=IntoPost(in,post,i+1,h1,l2+i-l1,h2-1);return(bt);}38.知二叉樹(shù)中序序列與后序序列，第30題以遞歸算法建立了二叉樹(shù)，本題是非遞歸算法。voidInPostCreat(ElemTypeIN[],POST[],intl1,h1,l2,h2)//由二叉樹(shù)的中序序列IN[]和后序序列P0ST[]非遞歸建立二叉樹(shù)，初始調(diào)用時(shí)，ll=l2=l,hl=h2=n。{typedefstruct{intl1,h1,l2,h2;BiTreet;}node;nodes[],p;//s為棧，容量足夠大BiTreebt=(BiTree)malloc(sizeof(BiNode));inttop=0,i;p.l1=l1;p.h1=h1;p.l2=l2;p.h2=h2;p.t=bt;s[++top]=p;//初始化while(top>0){p=s[top--];bt=p.t;l1=p.l1;h1=p.h1;l2=p.l2;h2=p.h2;//取出棧頂數(shù)據(jù)for(i=ll;i〈=hl;i++)if(IN[i]==P0ST[h2])break;//在中序序列中查等于POST[h2]的結(jié)點(diǎn)bt->data=POST[h2];//根結(jié)點(diǎn)的值if(i==l1)bt->lchild=null;//bt無(wú)左子樹(shù)else//將建立左子樹(shù)的數(shù)據(jù)入棧{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->rchild=null;//bt無(wú)右子樹(shù)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;}//右子樹(shù)數(shù)據(jù)入棧}//while(top>0)}結(jié)束InPostCreat★★先序中序算法★★37.voidPreInCreat(ElemTypeA[],B[]，intl1,h1,l2,h2)//由二叉樹(shù)前序序列A[l..n]和中序序列B[1..n]建立二叉樹(shù),ll,hl,和l2,h2分別為先序序列和//中序序列第一和最后結(jié)點(diǎn)的下標(biāo).初始調(diào)用時(shí)ll=l2=l,hl=h2=n。非遞歸{typedefstruct{intl1,h1,l2,h2;BiTreet;}node;BiTreebt;inttop=0,i;nodes[],p;//s為棧,容量足夠大bt=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)空間p.l1=l1;p.h1=h1;p.l2=l2;p.h2=h2;p.t=bt;s[++top]=p;//初始化while(top>0){p=s[top--];bt=p.t;l1=p.l1;h1=p.h1;l2=p.l2;h2=p.h2;//取出棧頂數(shù)據(jù)for(i=l2;i<=h2;i++)if(B[i]==A[l1])break;//到中序序列中查根結(jié)點(diǎn)的值bt-〉data=A[ll];//A[ll]為根結(jié)點(diǎn)的值if(i==l2)bt->lchild=null;//bt無(wú)左子樹(shù)13else//將建立左子樹(shù)的數(shù)據(jù)入棧{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;//bt無(wú)右子樹(shù)else{bt->rchild=(BiTree)malloc(sizeof(BiNode));p.t=bt->rchild;p.l1=l1+i-l2+1;p.h1=h1;p.l2=i+1;p.h2=h2;s[++top]=p;}//右子樹(shù)數(shù)據(jù)入棧}//while}結(jié)束當(dāng)二叉樹(shù)為單支樹(shù)時(shí)，棧深n；當(dāng)二叉樹(shù)左右子樹(shù)高相等時(shí)，棧深logn。時(shí)間復(fù)雜度0(n)。56.voidPreInCreat(BiTreeroot,ElemTypepre[],in[],intl1,h1,l2,h2)遞歸//根據(jù)二叉樹(shù)前序序列pre和中序序列in建立二叉樹(shù)。ll,hl,l2,h2是序列第一和最后元素下標(biāo)。{root=(BiTree)malloc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)root-〉data=pre[ll];//pre[ll]是根for(i=l2;i<=h2;i++)if(in[i]==pre[l1])break;//在中序序列中，根結(jié)點(diǎn)將樹(shù)分成左右子樹(shù)if(i==l2)root->lchild=null;//無(wú)左子樹(shù)elsePreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)； //遞歸建立左子樹(shù)if(i==h2)root->rchild=null;//無(wú)右子樹(shù)elsePreInCreat(root->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2)//遞歸建立右子樹(shù)}//結(jié)束PrelnCreat★★層次中序算法★★80．二叉樹(shù)的層次遍歷序列的第一個(gè)結(jié)點(diǎn)是二叉樹(shù)的根。實(shí)際上，層次遍歷序列中的每個(gè)結(jié)點(diǎn)都是“局部根”。確定根后，到二叉樹(shù)的中序序列中，查到該結(jié)點(diǎn)，該結(jié)點(diǎn)將二叉樹(shù)分為“左根右”三部分。若左、右子樹(shù)均有，則層次序列根結(jié)點(diǎn)的后面應(yīng)是左右子樹(shù)的根；若中序序列中只有左子樹(shù)或只有右子樹(shù)，則在層次序列的根結(jié)點(diǎn)后也只有左子樹(shù)的根或右子樹(shù)的根。這樣，定義一個(gè)全局變量指針R，指向?qū)哟涡蛄写幚碓亍Ｋ惴ㄖ邢忍幚砀Y(jié)點(diǎn)，將根結(jié)點(diǎn)和左右子女的信息入隊(duì)列。然后，在隊(duì)列不空的條件下，循環(huán)處理二叉樹(shù)的結(jié)點(diǎn)。隊(duì)列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstruct{intlvl;//層次序列指針，總是指向當(dāng)前“根結(jié)點(diǎn)”在層次序列中的位置intl,h;//中序序列的下上界intf;//層次序列中當(dāng)前“根結(jié)點(diǎn)”的雙親結(jié)點(diǎn)的指針intlr;//1—雙親的左子樹(shù)2—雙親的右子樹(shù)}qnode;BiTreeCreat(datatypein[],level[],intn)//由二叉樹(shù)的層次序列l(wèi)evel[n]和中序序列in[n]生成二叉樹(shù)。n是二叉樹(shù)的結(jié)點(diǎn)數(shù){if(n〈l){printf(“參數(shù)錯(cuò)誤\n");exit(O);}qnodes,Q[];//Q是元素為qnode類型的隊(duì)列，容量足夠大init(Q);intR=0;//R是層次序列指針，指向當(dāng)前待處理的結(jié)點(diǎn)BiTreep=(BiTree)malloc(sizeof(BiNode));//生成根結(jié)點(diǎn)p->data=level[0];p->lchild=null;p->rchild=null;//填寫(xiě)該結(jié)點(diǎn)數(shù)據(jù)for(i=0;i<n;i++)//在中序序列中查找根結(jié)點(diǎn)，然后，左右子信息入隊(duì)列if(in[i]==level[0])break;if(i==0)//根結(jié)點(diǎn)無(wú)左子樹(shù)，遍歷序列的1—n-1是右子樹(shù){p->lchild=null;s.lvl=++R;s.l=i+1;s.h=n-1;s.f=p;s.lr=2;enqueue(Q,s);}elseif(i==n-1)//根結(jié)點(diǎn)無(wú)右子樹(shù)，遍歷序列的1—n-1是左子樹(shù){p->rchild=null;s.lvl=++R;s.l=1;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);}else//根結(jié)點(diǎn)有左子樹(shù)和右子樹(shù){s.lvl=++R;s.l=0;s.h=iT;s.f=p;s.lr=1;enqueue(Q,s);//左子樹(shù)有關(guān)信息入隊(duì)列s.lvl=++R;s.l=i+1;s.h=n-1;s.f=p;s.lr=2;enqueue(Q,s);//右子樹(shù)有關(guān)信息入隊(duì)列}while(!empty(Q))//當(dāng)隊(duì)列不空，進(jìn)行循環(huán)，構(gòu)造二叉樹(shù)的左右子樹(shù){s=delqueue(Q);father=s.f;for(i=s.l;i<=s.h;i++)if(in[i]==level[s.lvl])break;p=(bitreptr)malloc(sizeof(binode));//申請(qǐng)結(jié)點(diǎn)空間p->data=level[s.lvl];p->lchild=null;p->rchild=null;//填寫(xiě)該結(jié)點(diǎn)數(shù)據(jù)14if(s.lr==1)father->lchild=p;elsefather->rchild=p；//讓雙親的子女指針指向該結(jié)點(diǎn)if(i==s.l){p->lchild=null;//處理無(wú)左子s.lvl=++R;s.l=i+1;s.f=p;s.lr=2;enqueue(Q,s);}elseif(i==s.h){p->rchild=null;//處理無(wú)右子s.lvl=++R;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);}else{s.lvl=++R;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);//左子樹(shù)有關(guān)信息入隊(duì)列s.lvl=++R;s.l=i+1;s.f=p;s.lr=2;enqueue(Q,s);//右子樹(shù)有關(guān)信息入隊(duì)列}}//結(jié)束while(!empty(Q))return(p);}//算法結(jié)束★★森林算法★★40.森林在先根次序遍歷時(shí)，首先遍歷第一棵子樹(shù)的根，接著是第一棵子樹(shù)的結(jié)點(diǎn)；之后是第二棵樹(shù)，??，最后一棵樹(shù)。本題中E[i]是H[i]所指結(jié)點(diǎn)的次數(shù)，次數(shù)就是結(jié)點(diǎn)的分支個(gè)數(shù)B,而分支數(shù)B與樹(shù)的結(jié)點(diǎn)數(shù)N的關(guān)系是N=B+1(除根結(jié)點(diǎn)外，任何一個(gè)結(jié)點(diǎn)都有一個(gè)分支所指)。所以，從E[i]的第一個(gè)單元開(kāi)始，將值累加，當(dāng)累加到第i個(gè)單元，其值正好等于i-1時(shí)，就是第一棵樹(shù)。接著，用相同方法，將其它樹(shù)分開(kāi)，進(jìn)行到第n個(gè)單元，將所有樹(shù)分開(kāi)。voidForest(ElemTypeH[],intE[],int,n)//H[i]是森林F在先根次序下結(jié)點(diǎn)的地址排列，E[i]是H[i]所指結(jié)點(diǎn)的次數(shù)，本算法計(jì)算森林F的樹(shù)形個(gè)數(shù)，并計(jì)算森林F的最后一個(gè)樹(shù)形的根結(jié)點(diǎn)地址{inti=1,sum=0,j=0,m=0;//sum記一棵樹(shù)的分支數(shù)，j記樹(shù)的棵數(shù)，m記一棵樹(shù)的結(jié)點(diǎn)數(shù)inttree[];//tree記每棵樹(shù)先序遍歷最后一個(gè)結(jié)點(diǎn)在H[i]中的地址?while(i<=n)//n是森林中結(jié)點(diǎn)個(gè)數(shù)，題目已給出{sum+=E[i];m++;if(sum+1==m&&i<=n)//記樹(shù)先序最后結(jié)點(diǎn)的地址，為下步初始化{sum=0;m=0;tree[++j]=i;}i++;}//while?if(j==1)return(1);//只有一棵樹(shù)時(shí)，第一個(gè)結(jié)點(diǎn)是根elsereturn(tree[j-1]+1)}//forest47.根據(jù)樹(shù)的雙親表示法創(chuàng)建樹(shù)的孩子兄弟鏈表表示法,首先給出根結(jié)點(diǎn)在雙親表示法中的下標(biāo)，但找根結(jié)點(diǎn)的子女要遍歷雙親表示法的整個(gè)靜態(tài)鏈表，根結(jié)點(diǎn)的第一個(gè)子女是孩子兄弟表示法中的孩子，其它子女結(jié)點(diǎn)作兄弟。對(duì)雙親表示法中的任一結(jié)點(diǎn)，均遞歸建立其孩子兄弟鏈表子樹(shù)。CSTreePtreeToCstree(PTreept,introot)//本算法將雙親表示法的樹(shù)pt轉(zhuǎn)為孩子兄弟鏈表表示的樹(shù)，root是根結(jié)點(diǎn)在雙親表示法中的下標(biāo)。{CSTreechild,sibling;intfirstchild;CSTreecst=(CSTree)malloc(sizeof(CSNode));//申請(qǐng)結(jié)點(diǎn)空間cst->data=pt.nodes[root].data;cst->firstchild=null;cst->nextsibling=null;//根結(jié)點(diǎn)firstchild=1;▼for(i=l;i<=pt.n;i++)//查找root的孩子if(pt.nodes[i].parent==root){child=PtreetoCstree(pt,i);if(firstchild){cst->firstchild=child;firstchild=0;sibling=cst->firstchild;}else//child不是root的第一個(gè)孩子，作兄弟處理{sibling->nextsibling=child;sibling=sibling->nextsibling;}}//if}//endforreturncst;}//結(jié)束PtreetoCstree★★二叉樹(shù)相似算法★★46.兩棵空二叉樹(shù)或僅有根結(jié)點(diǎn)的二叉樹(shù)相似；對(duì)非空二叉樹(shù)，可判左右子樹(shù)是否相似，采用遞歸算法intSimi