1、數據構造實驗報告二一二年數據構造實驗3實驗報告實驗項目3：二叉樹層次遍歷學號姓名課程號實驗地址指導教師時間考語：準時完成實驗；實驗內容和過程記錄完滿；回答以下問題完滿、正確；實驗報告的撰寫認真、格式吻合要求；無抄襲的行為。二叉樹從左至右，從上至基層次遍歷成績教師簽字1、預習要求：二叉樹構造定義和層次遍歷。2、實驗目的：1）認識二叉樹構造層次遍歷看法；2）理解二叉樹二種不同樣層次遍歷過程；3）掌握二叉樹層次遍歷算法程序。3、實驗內容及要求：（1）建立包含10個結點的二叉樹（樹構造和數據元素的值由自己設定）；（2）完成二叉樹從左至右，從上至基層次遍歷程序；（3）給出程序和遍歷程序的結果。4、實驗設

2、備（環境）及要求硬件：支持IntelPentium及其以上CPU，內存128MB以上、硬盤1GB以上容量的微機。軟件：配有Windows98/2000/XP操作系統，安裝VisualC+。5、實驗時間：10學時6、該文檔的文件名不要更正，存入命名的文件夾中7、該表中的數據只需填空，已有內容不要更正實驗結果（運行結果界面及源程序，運行結果界面放在前面）：數據構造實驗報告二一二年數據構造實驗報告二一二年數據構造實驗報告二一二年#include#include#include#include#defineSTUDENTETypestructSTUDENTcharcharcharintcharnumb

3、er8;name8;sex3;age;place20;structBinaryTreeNodeETypedata;BinaryTreeNode*LChild;BinaryTreeNode*RChild;structQTypeBinaryTreeNode*ptr;structQueueQType*element;intfront;intrear;intmaxsize;structNode_PtrBinaryTreeNode*ptr;voidCreatQueue(Queue&Q,intMaxQueueSize)/創辦行列Q.maxsize=MaxQueueSize;數據構造實驗報告二一二年Q.el

4、ement=newQTypeQ.maxsize+1;Q.front=0;Q.rear=0;boolIsEmpty(Queue&Q)/判斷行列可否為空if(Q.front=Q.rear)returntrue;returnfalse;boolIsFull(Queue&Q)/判斷行列可否為滿if(Q.front=(Q.rear+1)%(Q.maxsize+1)returntrue;returnfalse;boolGetFront(Queue&Q,QType&result)/取出隊頭元素if(IsEmpty(Q)returnfalse;result=Q.element(Q.front+1)%(Q.ma

5、xsize+1);returntrue;boolGetRear(Queue&Q,QType&result)/取出隊尾元素if(IsEmpty(Q)returnfalse;result=Q.elementQ.rear;returntrue;boolEnQueue(Queue&Q,QType&x)/元素進隊if(IsFull(Q)returnfalse;Q.rear=(Q.rear+1)%(Q.maxsize+1);Q.elementQ.rear=x;returntrue;boolDeQueue(Queue&Q,QType&result)/元素出隊if(IsEmpty(Q)returnfalse;

6、Q.front=(Q.front+1)%(Q.maxsize+1);result=Q.elementQ.front;數據構造實驗報告二一二年returntrue;BinaryTreeNode*MakeNode(EType&x)/構造節點BinaryTreeNode*ptr;ptr=newBinaryTreeNode;if(!ptr)returnNULL;ptr-data=x;ptr-LChild=NULL;ptr-RChild=NULL;returnptr;voidMakeBinaryTree(BinaryTreeNode*root,BinaryTreeNode*left,BinaryTree

7、Node*right)/構造二叉樹之間的關系root-LChild=left;root-RChild=right;voidOutputBinaryTreeNode(BinaryTreeNode*p)/輸出節點data.sexdata.agedata.placeendl;coutendl;voidLevelOrder_LtoR_UtoD(BinaryTreeNode*BT)/從左至右，從上至下按層次遍歷一棵二叉樹QueueQ;QTypetemp;BinaryTreeNode*p;intmaxqueuesize=50;CreatQueue(Q,max

8、queuesize);p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout學號姓名性別年齡地址endl;cout=LChild)temp.ptr=p-LChild;EnQueue(Q,temp);if(p-RChild)temp.ptr=p-RChild;EnQueue(Q,temp);voidLevelOrder_RtoL_UtoD(BinaryTreeNode*BT)/從右至左，從上至下按層次遍歷一棵二叉樹QueueQTypeBinaryTreeNodeQ;temp;*p;intmaxqueuesize=50;CreatQueue(Q,maxqueue

9、size);p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout學號姓名性別年齡地址endl;cout=RChild)temp.ptr=p-RChild;EnQueue(Q,temp);if(p-LChild)temp.ptr=p-LChild;數據構造實驗報告二一二年EnQueue(Q,temp);voidLevelOrder_LtoR_DtoU(BinaryTreeNode*BT)/從左至右，從下至上按層次遍歷一棵二叉樹QueueQ;QTypetemp;BinaryTreeNode*p;intmaxqueuesize=50;CreatQueue(Q,m

10、axqueuesize);intfrontkeep=Q.front;p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout學號姓名性別年齡地址endl;cout=RChild)temp.ptr=p-RChild;EnQueue(Q,temp);if(p-LChild)temp.ptr=p-LChild;EnQueue(Q,temp);for(inti=Q.rear;ifrontkeep;i-)OutputBinaryTreeNode(Q.elementi.ptr);voidLevelOrder_RtoL_DtoU(BinaryTreeNode*BT)/從右至

11、左，從下至上按層次遍歷一棵二叉樹QueueQ;QTypetemp;BinaryTreeNode*p;intmaxqueuesize=50;數據構造實驗報告二一二年CreatQueue(Q,maxqueuesize);intfrontkeep=Q.front;p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout學號姓名性別年齡地址endl;cout=LChild)temp.ptr=p-LChild;EnQueue(Q,temp);if(p-RChild)temp.ptr=p-RChild;EnQueue(Q,temp);for(inti=Q.rear;ifr

12、ontkeep;i-)OutputBinaryTreeNode(Q.elementi.ptr);intBinaryHeight(BinaryTreeNode*BT)/返回二叉樹的高度if(!BT)return0;intHighL=BinaryHeight(BT-LChild);intHighR=BinaryHeight(BT-RChild);if(HighLHighR)return+HighL;elsereturn+HighR;voidBinaryDelete(BinaryTreeNode*BT)/二叉樹刪除算法if(BT)BinaryDelete(BT-LChild);數據構造實驗報告二一二

13、年BinaryDelete(BT-RChild);deleteBT;intBinaryNodeSum(BinaryTreeNode*BT)/計算二叉樹中的節點數if(!BT)return0;QueueQ;QTypetemp;BinaryTreeNode*p;intmaxqueuesize=50;intindex=0;CreatQueue(Q,maxqueuesize);p=BT;temp.ptr=p;EnQueue(Q,temp);while(p)if(!DeQueue(Q,temp)break;p=temp.ptr;/出隊成功index+;if(p-LChild)temp.ptr=p-LCh

14、ild;EnQueue(Q,temp);if(p-RChild)temp.ptr=p-RChild;EnQueue(Q,temp);returnindex;voidDigitalToString(charstr,intn)chartemp;chark=1;inti=0;while(n&i80)k=n%10+48;數據構造實驗報告二一二年n=n/10;stri=k;i+;stri=0;intlen=strlen(str);for(i=0;ilen/2;i+)temp=stri;stri=strlen-i-1;strlen-i-1=temp;char*GetOuputInformationStri

15、ng(intWidthOfData,char*OutputInformation,char*outputstring)/將一個元素的字符串OutputInformation變換為寬度為WidthOfData的等長字符串outputstring/比方，姓名是由四個字符組成，而WidthOfData為8，則在姓名字符串的兩邊分別連接兩個字符，形成8個長度的字符串intleft_space,right_space;inti;charleft_space_string16=;charright_space_string16=;intadd_space;intlen_OutputInformation=

16、strlen(OutputInformation);/計算OutputInformation的字符個數add_space=WidthOfData-len_OutputInformation;/計算需要補充的字符個數left_space=add_space/2;/計算OutputInformation左邊需要補充的字符個數right_space=add_space-left_space;/計算OutputInformation右邊需要補充的字符個數for(i=1;i=left_space;i+)/形成OutputInformation左邊需要補充的空格字符串strcat(left_space_s

17、tring,);數據構造實驗報告二一二年for(i=1;);break;case2:strcat(outputInformation,elementk.ptr-data.number);break;case3:strcat(outputInformation,elementk.ptr-data.place);break;case4:strcat(outputInformation,elementk.ptr-data.sex);break;case5:DigitalToString(outputInformation,elementk.ptr-data.age);break;

18、default:break;數據構造實驗報告二一二年returnoutputInformation;/輸出二叉樹voidOutputBinaryTree(BinaryTreeNode*BT)Node_Ptrtemp,*element;BinaryTreeNode*p;intMaxSize;intBinaryTreeHigh;inti,j,k;BinaryTreeHigh=BinaryHeight(BT);MaxSize=(int)pow(2,BinaryTreeHigh);element=newNode_PtrMaxSize+1;/定義一個用于存放二叉樹結點指針的數組for(i=1;i=Max

19、Size;i+)/對指針數組初始化，初值設為NULLelementi.ptr=NULL;p=BT;temp.ptr=p;if(p)element1=temp;for(i=1;iLChild)/&!p-Lflag/線索樹特有的辦理與一般二叉樹不同樣之處temp.ptr=p-LChild;element2*i=temp;if(p-RChild)/&!p-Rflag/線索樹特有的辦理與一般二叉樹不同樣之處temp.ptr=p-RChild;element2*i+1=temp;數據構造實驗報告二一二年intWidthOfData=5;intIntervalOfData=3;coutWidthOfDat

20、a=WidthOfDataendl;coutIntervalOfData=IntervalOfDataendl;coutBinaryTreeHigh=BinaryTreeHighendl;intposition_of_central617;/存放每一元素輸出地址中心（距離屏幕左界線的字符數）introw,col;for(i=0;i=BinaryTreeHigh;i+)/二維數組的行列下標變量/存放每一元素輸出地址中心（距離屏幕左界線的字符數），初值為0for(j=0;j=pow(2,BinaryTreeHigh-1);j+)position_of_centralij=0;for(i=1;i=p

21、ow(2,BinaryTreeHigh)-1;i+)/對深度為BinaryTreeHigh的滿二叉樹的所有結點計算每個結點輸出的中心點地址k=i*2;while(k=pow(2,BinaryTreeHigh)-1)/k/k指向i的左子樹根結點不斷推進到i編號的結點左子樹中最右后輩結點k=2*k+1;k=k/2;/k的值就是i編號的結點左子樹中最右后輩結點的編號j=(int)(k-(pow(2,(BinaryTreeHigh-1)-1);/由k編號的結點換算出該結點是基層中從左至右第j個結點右上方/即編號為k的結點中心點垂直線左邊最基層上有j個結點row=(int)(log10(i)/log10

22、(2)+1);/計算中心點值存放在position_of_centralrowcol中的rowcol=(int)(i-(pow(2,(row-1)-1);position_of_centralrowcol中的col/計算中心點值存放在if(row=BinaryTreeHigh)計算基層i結點距離左界線的字符數，左邊無縫隙position_of_centralrowcol=(j-1)*WidthOfData+(j-1)*IntervalOfData+(WidthOfData/2+1);else計算非基層i結點距離左界線的字符數，position_of_centralrowcol=j*WidthO

23、fData+(j-1)*IntervalOfData+(IntervalOfData/2+1);數據構造實驗報告二一二年charprespace100;intm;intkk;intkkk;intitem_max=5;coutendl;for(i=1;i=BinaryTreeHigh;i+)kkk=(int)pow(2,i-1);/kkk是滿二叉樹中每一層第1個結點的編號for(intitem=1;item=item_max;item+)/輸出每個數據元素多個item成員的值inthalf_len_pre_value=0;/同一行前一個輸出的元素值長度的一半,同一行第一個輸出的元素值前沒有值輸出

24、，初值為0inthalf_len_now_value=WidthOfData/2;/同一行當前輸出的元素值長度的一半，其值向來為WidthOfData的一半kk=kkk;/kk是滿二叉樹中每一層結點的編號變化，從某層的最左邊第一個結點編號kkk開始for(j=1;j=pow(2,i-1);j+)/輸出滿二叉樹中同一層次上的每個數據元素的同一個成員的值charoutputInformation20=;char*OutputInformation;if(elementkk.ptr)/獲取每個數據元素的一個成員的值OutputInformation，如姓名、年齡等OutputInformation=

25、GetOuputInformation(item,kk,outputInformation,element);if(position_of_centralij)/輸出數據中點值存在時，position_of_centralij非0charoutputstring80=;char*OutputString;名、年齡等，變換為等長/下面語句將每個數據元素的一個成員的值WidthOfData的字符串OutputStringOutputInformation，如姓數據構造實驗報告二一二年OutputString=GetOuputInformationString(WidthOfData,OutputI

26、nformation,outputstring);/生成兩個孩子從前的空格串prespace/組成：=-strcpy(prespace,);m=(position_of_centralij-position_of_centralij-1-1-half_len_pre_value-half_len_now_value);for(k=1;k=m;k+)strcat(prespace,);coutprespace;coutOutputString;half_len_pre_value=WidthOfData/2;/調整同一行前一個輸出的元素值長度為WidthOfData的一半kk+;/if(posi

27、tion_of_centralij)/for(j=1;j=pow(2,i-1);j+)coutendl;/for(intitem=1;item=5;item+)charline3=;charOutputLine80;charmidspace80;intnodenumber;if(i=1)/對深度為BinaryTreeHigh號，計算第i層上初步結點的編號nodenumber的滿二叉樹從上至下，從左至右的編nodenumber=1;else點編號nodenumber=(int)(pow(2,i)-1)-(pow(2,i-1)-1);nodenumber/第i(i!=1)層上的第1個結for(j=

28、1;j=pow(2,i-1);j+)/輸出同一層次上的線條if(i=BinaryTreeHigh)break;/最基層下面沒有線條，所以break/生成兩個數據元素從前的前導空格串prespacestrcpy(prespace,);m=(position_of_centrali+1j-position_of_centrali+1j-1-1);數據構造實驗報告二一二年for(k=1;k=m;k+)strcat(prespace,);/計算左右兩個孩子之間一半的連線OutLine，由若干個line組成/注意line是漢字字符，一個占兩個字符位，m是左右兩個孩子之間的line數，所以m要除4strc

29、py(OutputLine,);m=(position_of_centrali+1j+1-position_of_centrali+1j-1)/4;for(k=1;k=m;k+)strcat(OutputLine,line);/計算左右兩個孩子之間一半的空格字符的個數m,，所以要除2。由m形成左右兩個孩子之間的空格串midspacestrcpy(midspace,);m=(position_of_centrali+1j+1-position_of_centrali+1j-1)/2;for(k=1;k=m;k+)strcat(midspace,);if(element2*nodenumber.p

30、tr)&(element2*nodenumber+1.ptr)/左右子樹都存在時，左右兩個孩子上的連接線coutprespaceOutputLineOutputLine;if(element2*nodenumber.ptr)&(!element2*nodenumber+1.ptr)/左子樹存在，右子樹不存在時，左右兩個孩子上的連接線coutprespaceOutputLinemidspace;if(!element2*nodenumber.ptr)&(element2*nodenumber+1.ptr)/左子樹不存在，右子樹存在時左右兩個孩子上的連接線coutprespacemidspaceO

31、utputLine;if(!element2*nodenumber.ptr)&(!element2*nodenumber+1.ptr)/左子樹不存在，右子樹不存在時，沒有連接線，是空格串coutprespacemidspacemidspace;nodenumber=nodenumber+1;/結點編號加1coutendl;/for(i=1;i=BinaryTreeHigh;i+)數據構造實驗報告二一二年deleteelement;/釋下班作空間intmain()BinaryTreeNode*BT,*P11;ETypex;intchoice;charnumber8=,001,002,003,00

32、4,005,006,007,008,009,010;charname8=,百里,東郭,太史,聞人,公孫,赫連,鐘離,鮮魚,軒轅,南門;charsex3=,女,男,女,男,女,女,男,男,女,男;charplace20=,重慶,長安,東莞,安慶,承德,四平,安穩,香港,金門,龍門;for(inti=1;i=10;i+)strcpy(x.number,numberi);strcpy(,namei);strcpy(x.sex,sexi);x.age=20+i;strcpy(x.place,placei);Pi=MakeNode(x);MakeBinaryTree(P1,P2,P3);MakeBinaryTree(P2,P4,P5);MakeBinaryTree(P3,NULL,P6);MakeBinaryTree(P4,P7,NULL);MakeBinaryTree(P5,NULL,P8);MakeBinaryTree(P6,P9,P10);MakeBinaryTree(P7,NULL,NULL);MakeBinaryTree(P8,NULL,NULL);MakeBinaryTree(P9,NULL,NULL);MakeBinaryTree(P10,NULL,NULL);BT=P1;while(true)couten