北航計軟實驗報告實驗二

實驗報告二叉樹二叉樹實驗名稱班學姓成班學姓成級 號 名 績實驗概述：【實驗目的及要求】掌握二叉樹的存儲結構【實驗原理】(1)二叉樹的鏈式存儲結構二叉樹的每一個結點i有三個域：值域V(i),左鏈域L(i),右鏈域R(i)o分別用三個一維數組表示它們，并用頭指針HBT指向二叉樹的根結點。(2)按層次輸出所有結點設置一個容量足夠大的循環(huán)隊列(可以用一個首尾相接的一維數組模擬)。初始時，將根結點序號入隊。然后每次從隊列中退出一個結點序號，將此結點的值及左右鏈指針輸出，且依次將此結點的左右鏈指針入隊。這個過程一直進行到隊列空為止。設循環(huán)隊列數組為cq(1：m),其頭尾指針分別為front與rear,則按層次輸出所有結點的算法如下：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在這個算法中的ADD和DEL分別為入隊和退隊運算的兩個過程，其算法(不考慮溢出情況)如下：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)輸出所有葉子結點設置一個容量足夠大的棧S(可以用一個一維數組模擬它，棧底在數組的第一個元素處)。具體過程是：從根結點開始掃描二叉樹，如果掃描的當前結點的左右均為零，則輸出次葉子結點；否則將非零的右指針和左指針值推入堆棧。然后從棧中退出一個結點序號重新進行這個過程，直至?？諡橹?。其算法如下：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)將所有左右子樹值交換這個問題的處理和輸出所有葉子結點的問題很類彳以，只要將非葉子結點的左右指針交換即可，其算法如下：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【實驗環(huán)境】(使用的軟硬件)硬件：PC軟件：VC++6.0實驗內容:【實驗方案設計】.對給定二叉樹用鏈式鏈式存儲結構；利用隊列與棧對二叉樹進行運算。.按層次輸出所有結點。.輸出所有葉子結點。.將所有左右子樹值交換。【實驗過程】（實驗步驟、記錄、數據、分析）（-）實驗步驟.分別編制實驗內容中題2、3、4的三個子程序。.以上圖所示的二叉樹為例編制主程序，實現下述功能，并運行這個程序。（1）輸入二叉樹用鏈式結構存儲；（2）調用題2的子程序，并輸出結果；（3）調用題3的子程序，并輸出結果；（4）調用題4的子程序，并輸出結果；.自行設計一棵二叉樹，重復步驟2。.整理程序清單與所有結果，并寫出實驗報告。（二）程序清單#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(”請輸入存放滿二叉樹數據的文件名稱:“)；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("文件讀取成功，已用鏈式存儲方式構建二叉樹。)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("此二叉樹為空!\nn);else(structtree*cq[m],*temp,**ptemp二&temp;intfront=m,rear=m,^pfront=&front,*prear=&rear;printfC⑵按層次輸出所有節(jié)點:\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é)點:％d",temp->left->num);add(cq,temp->left,pfront,prear);)elseprintf("無左節(jié)點)if(temp->right!=NULL)(printf("右節(jié)’點:％d”,temp->right->num);add(cq,temp->right,pfront,prear);)elseprintf("無右節(jié)點)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("此二叉樹為空!\rT);else(inti=l;structtree*S[m],*temp,**ptemp=&temp;inttop=0,*ptop=⊤printf(”(3)此二叉樹的所有葉子結點為:\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("此二叉樹為空!\nn);else(inti=l;structtree*S[m],*temp,**ptemp二&temp,"exchange;inttop=0,*ptop=⊤printf("⑷執(zhí)行所有左右子樹值交換操作。\n操作過程顯示如下：\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("交換結點“%d”的左子樹與右子樹】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;(三)運行結果，青輸入存放滿二叉樹數據的文件名稱:tree.txt文件讀取成功，已用鏈式存儲方式構建二叉樹。，\\psf\Home\Doc5ients\不啊啊'大二上'計\\psf\Home\Documents\不啊啊\大二上'計軟，青輸入存放滿二叉樹數據的文件名稱:tree.txt文件讀取成功，已用鏈式存儲方式構建二叉樹。，\\psf\Home\Doc5ients\不啊啊'大二上'計軟'上機實驗\shiyan2'用作為當前目錄閡以上路徑啟動了CMD.EXE.UNC路徑木受支持。默認值設為Windows目錄。請按任意鍵繼續(xù).?.(2)按層次輸出所有節(jié)點：15左結點：98右結點：698左結點：2。右結點：1。6左結點：45無右結點2。左結點：3。右結點：4。1。無左結點無右結點45無左結點右結￡：603。無左結點無右結點帆無左結點無右結點60左結點：70無右結點再無左結點無右結點(3)此二叉樹的所有葉子結點為:30401070(4)執(zhí)行所有左右子樹值交換操作。操作過程顯示如下：交換結點“15”的左子樹與右子樹(4)執(zhí)行所有左右子樹值交換操作。操作過程顯示如下：交換結點“15”的左子樹與右子樹交換結點交換結點交換結點交換結點交換結點“98”的左子樹與右子樹“20”的左子樹與右子樹“6”的左子樹與右子樹“45”的左子樹與右子樹“60”的左子樹與右子樹(2)