北航計(jì)軟實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二

實(shí)驗(yàn)報(bào)告二叉樹(shù)二叉樹(shù)實(shí)驗(yàn)名稱(chēng)班學(xué)姓成班學(xué)姓成級(jí) 號(hào) 名 績(jī)實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康募耙蟆空莆斩鏄?shù)的存儲(chǔ)結(jié)構(gòu)【實(shí)驗(yàn)原理】(1)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的每一個(gè)結(jié)點(diǎn)i有三個(gè)域：值域V(i),左鏈域L(i),右鏈域R(i)o分別用三個(gè)一維數(shù)組表示它們，并用頭指針HBT指向二叉樹(shù)的根結(jié)點(diǎn)。(2)按層次輸出所有結(jié)點(diǎn)設(shè)置一個(gè)容量足夠大的循環(huán)隊(duì)列(可以用一個(gè)首尾相接的一維數(shù)組模擬)。初始時(shí)，將根結(jié)點(diǎn)序號(hào)入隊(duì)。然后每次從隊(duì)列中退出一個(gè)結(jié)點(diǎn)序號(hào)，將此結(jié)點(diǎn)的值及左右鏈指針輸出，且依次將此結(jié)點(diǎn)的左右鏈指針入隊(duì)。這個(gè)過(guò)程一直進(jìn)行到隊(duì)列空為止。設(shè)循環(huán)隊(duì)列數(shù)組為cq(1：m),其頭尾指針?lè)謩e為front與rear,則按層次輸出所有結(jié)點(diǎn)的算法如下：IFHBT=0THENRETURN“THISTREEISEMPTY”Frontrear<-mADD(cq,HBT,front,rear)WHILEfront豐rearDO(DEL(cq,i,front,rear)OUTPUT(L⑴，V⑴,R(i))IFL(i)，0THENADD(cq,L(i),front,rear)IFR(i)W0THENADD(cq,R(i),front,rear))RETURN在這個(gè)算法中的ADD和DEL分別為入隊(duì)和退隊(duì)運(yùn)算的兩個(gè)過(guò)程，其算法(不考慮溢出情況)如下：ADD(cq,i,front,rear)rear-rear+1IFrear=m+1THENrear_1cq(rear)-iRETURNDEL(cq,i,front,rear)frontJfront+1IFfront=m+1THENfont_1iJcq(front)RETURN(3)輸出所有葉子結(jié)點(diǎn)設(shè)置一個(gè)容量足夠大的棧S(可以用一個(gè)一維數(shù)組模擬它，棧底在數(shù)組的第一個(gè)元素處)。具體過(guò)程是：從根結(jié)點(diǎn)開(kāi)始掃描二叉樹(shù)，如果掃描的當(dāng)前結(jié)點(diǎn)的左右均為零，則輸出次葉子結(jié)點(diǎn)；否則將非零的右指針和左指針值推入堆棧。然后從棧中退出一個(gè)結(jié)點(diǎn)序號(hào)重新進(jìn)行這個(gè)過(guò)程，直至棧空為止。其算法如下：IFHBT=OTHENRETURN“THISTREEISEMTPY”top.0PUSH(S,HBT,top)WHILEtopW。DO(POP(S,i,top)IF(L(i)=0)and(R(i)=0)THENOUTPUTV(i)ELSE(IFR(i)=0THENPUSH(S,R(i),top)IFL(i)00THENPUSH(S,L(i),top)RETURN(4)將所有左右子樹(shù)值交換這個(gè)問(wèn)題的處理和輸出所有葉子結(jié)點(diǎn)的問(wèn)題很類(lèi)彳以，只要將非葉子結(jié)點(diǎn)的左右指針交換即可，其算法如下：IFHBT=0THENRETURNUTHISTREEISEMPTY”top.0PUSH(S,HBT,top)WHILEtop*0DO(POP(S,i,top)IF(L(i)WO)or(R(i)*0)THEN(L(i)—R(i)IFL(i)W0THENPUSH(S,L(i),top)IFR(i)=0THENPUSH(S,R(i),top)))RETURN【實(shí)驗(yàn)環(huán)境】(使用的軟硬件)硬件：PC軟件：VC++6.0實(shí)驗(yàn)內(nèi)容:【實(shí)驗(yàn)方案設(shè)計(jì)】.對(duì)給定二叉樹(shù)用鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)；利用隊(duì)列與棧對(duì)二叉樹(shù)進(jìn)行運(yùn)算。.按層次輸出所有結(jié)點(diǎn)。.輸出所有葉子結(jié)點(diǎn)。.將所有左右子樹(shù)值交換?！緦?shí)驗(yàn)過(guò)程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）（-）實(shí)驗(yàn)步驟.分別編制實(shí)驗(yàn)內(nèi)容中題2、3、4的三個(gè)子程序。.以上圖所示的二叉樹(shù)為例編制主程序，實(shí)現(xiàn)下述功能，并運(yùn)行這個(gè)程序。（1）輸入二叉樹(shù)用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；（2）調(diào)用題2的子程序，并輸出結(jié)果；（3）調(diào)用題3的子程序，并輸出結(jié)果；（4）調(diào)用題4的子程序，并輸出結(jié)果；.自行設(shè)計(jì)一棵二叉樹(shù)，重復(fù)步驟2。.整理程序清單與所有結(jié)果，并寫(xiě)出實(shí)驗(yàn)報(bào)告。（二）程序清單#include<stdio.h>#include<stdlib.h>structtree（intnum;structtree"left;structtreebright;}；inta[50]={0};structtree*build(inti)(structtree*n;n=(structtree^)malloc(sizeof(structtree));n->num=a[i];if(a[2*i]!=0)n->left=build(2*i);elsen->left=NULL;if(a[2*i+l]!=0)n->right=build(2*i+1);elsen->right=NULL;retum(n);)structtree*head;intbuild_binary_tree()(FILE*fi;inti=l;charfile_name[20];printf(”請(qǐng)輸入存放滿二叉樹(shù)數(shù)據(jù)的文件名稱(chēng):“)；scanf(H%sH,file_name);fi=fopen(file_name,nrn);if(fi=NULL)(printf("文件讀取失敗，名為“%s”的文件不存在！\n\file_name);return(O);}else(while(!feof(fi))(fscanf(fij%dt&a[i]);i=i+l;)fclose(fi);head=build(l);printf("文件讀取成功，已用鏈?zhǔn)酱鎯?chǔ)方式構(gòu)建二叉樹(shù)。)return(l);#definem100voidadd(structtree**cq,structtree*n,intupfront,int*prear)(*prear=*prear+l;if(*prear==m+l)*prear=l;cq[*prear]=n;)voiddel(structtree**cq,structtree**ptemp,intupfront,int*prear)(*pfront=*pfront+1;if(*pfront==m+l)*pfront=l;*ptemp=cq[Upfront];)voidfunc_2(structtree*head)(if(head==0)printf("此二叉樹(shù)為空!\nn);else(structtree*cq[m],*temp,**ptemp二&temp;intfront=m,rear=m,^pfront=&front,*prear=&rear;printfC⑵按層次輸出所有節(jié)點(diǎn):\nn);add(cq,head,pfront,prear);while(front!=rear)(del(cq,ptemp,pfront,prear);printf(n%d',,temp->num);if(temp->left!=NULL)(printf("左節(jié)點(diǎn):％d",temp->left->num);add(cq,temp->left,pfront,prear);)elseprintf("無(wú)左節(jié)點(diǎn))if(temp->right!=NULL)(printf("右節(jié)’點(diǎn):％d”,temp->right->num);add(cq,temp->right,pfront,prear);)elseprintf("無(wú)右節(jié)點(diǎn))printfC**”)；printf(n\nn);}printf(n\nH);))voidpush(structtree**S,structtree*n,int*ptop)(*ptop=*ptop+l;S[*ptop]=n;)voidpop(structtree**S,structtree**ptemp,int*ptop)(*ptemp二S[*ptop];*ptop=*ptop-l;)voidfunc_3(structtree*head)(if(head==0)printf("此二叉樹(shù)為空!\rT);else(inti=l;structtree*S[m],*temp,**ptemp=&temp;inttop=0,*ptop=⊤printf(”(3)此二叉樹(shù)的所有葉子結(jié)點(diǎn)為:\n”)；push(S,head,ptop);while(top!=0)(pop(S,ptemp,ptop);if((temp->left==NULL)&&(temp->right==NULL))printf(n%dn,temp->num);else(if(temp->right!=NULL)push(S,temp->right,ptop);if(temp->left!=NULL)push(S,temp->left,ptop);))printf(n\n\nn);))voidfunc_4(structtree*head)(if(head==0)printf("此二叉樹(shù)為空!\nn);else(inti=l;structtree*S[m],*temp,**ptemp二&temp,"exchange;inttop=0,*ptop=⊤printf("⑷執(zhí)行所有左右子樹(shù)值交換操作。\n操作過(guò)程顯示如下：\n)push(S,head,ptop);while(top!=0)(pop(S,ptemp,ptop);if((temp->left!=NULL)11(temp->right!=NULL))(exchange=temp->left;temp->left=temp->right;temp->right=exchange;printf("交換結(jié)點(diǎn)“%d”的左子樹(shù)與右子樹(shù)】emp->num);if(temp->left!=NULL)push(S,temp->left,ptop);if(temp->right!=NULL)push(S,temp->right,ptop);)}printf(n\nn);)func_2(head);)main()(intjudge;while(l)(judge=buildbinarytree();if(judge=l)(system(npause");func_2(head);func_3(head);func_4(head);break;(三)運(yùn)行結(jié)果，青輸入存放滿二叉樹(shù)數(shù)據(jù)的文件名稱(chēng):tree.txt文件讀取成功，已用鏈?zhǔn)酱鎯?chǔ)方式構(gòu)建二叉樹(shù)。，\\psf\Home\Doc5ients\不啊啊'大二上'計(jì)\\psf\Home\Documents\不啊啊\大二上'計(jì)軟，青輸入存放滿二叉樹(shù)數(shù)據(jù)的文件名稱(chēng):tree.txt文件讀取成功，已用鏈?zhǔn)酱鎯?chǔ)方式構(gòu)建二叉樹(shù)。，\\psf\Home\Doc5ients\不啊啊'大二上'計(jì)軟'上機(jī)實(shí)驗(yàn)\shiyan2'用作為當(dāng)前目錄閡以上路徑啟動(dòng)了CMD.EXE.UNC路徑木受支持。默認(rèn)值設(shè)為Windows目錄。請(qǐng)按任意鍵繼續(xù).?.(2)按層次輸出所有節(jié)點(diǎn)：15左結(jié)點(diǎn)：98右結(jié)點(diǎn)：698左結(jié)點(diǎn)：2。右結(jié)點(diǎn)：1。6左結(jié)點(diǎn)：45無(wú)右結(jié)點(diǎn)2。左結(jié)點(diǎn)：3。右結(jié)點(diǎn)：4。1。無(wú)左結(jié)點(diǎn)無(wú)右結(jié)點(diǎn)45無(wú)左結(jié)點(diǎn)右結(jié)￡：603。無(wú)左結(jié)點(diǎn)無(wú)右結(jié)點(diǎn)帆無(wú)左結(jié)點(diǎn)無(wú)右結(jié)點(diǎn)60左結(jié)點(diǎn)：70無(wú)右結(jié)點(diǎn)再無(wú)左結(jié)點(diǎn)無(wú)右結(jié)點(diǎn)(3)此二叉樹(shù)的所有葉子結(jié)點(diǎn)為:30401070(4)執(zhí)行所有左右子樹(shù)值交換操作。操作過(guò)程顯示如下：交換結(jié)點(diǎn)“15”的左子樹(shù)與右子樹(shù)(4)執(zhí)行所有左右子樹(shù)值交換操作。操作過(guò)程顯示如下：交換結(jié)點(diǎn)“15”的左子樹(shù)與右子樹(shù)交換結(jié)點(diǎn)交換結(jié)點(diǎn)交換結(jié)點(diǎn)交換結(jié)點(diǎn)交換結(jié)點(diǎn)“98”的左子樹(shù)與右子樹(shù)“20”的左子樹(shù)與右子樹(shù)“6”的左子樹(shù)與右子樹(shù)“45”的左子樹(shù)與右子樹(shù)“60”的左子樹(shù)與右子樹(shù)(2)