數(shù)據(jù)結(jié)構(gòu)實驗3 二叉樹層次遍歷

1、數(shù)據(jù)結(jié)構(gòu)實驗報告 二一二年數(shù)據(jù)結(jié)構(gòu)實驗3實驗報告實驗項目3：二叉樹層次遍歷學號姓名課程號實驗地點指導(dǎo)教師時間評語： 按時完成實驗；實驗內(nèi)容和過程記錄完整；回答問題完整、正確；實驗報告的撰寫認真、格式符合要求；無抄襲的行為。成績教師簽字二叉樹從左至右，從上至下層次遍歷1、預(yù)習要求：二叉樹結(jié)構(gòu)定義和層次遍歷。2、實驗?zāi)康模?（1）了解二叉樹結(jié)構(gòu)層次遍歷概念；（2）理解二叉樹二種不同層次遍歷過程；（3）掌握二叉樹層次遍歷算法程序。3、實驗內(nèi)容及要求：（1）建立包含10個結(jié)點的二叉樹（樹結(jié)構(gòu)和數(shù)據(jù)元素的值由自己設(shè)定）；（2）完成二叉樹從左至右，從上至下層次遍歷程序；（3）給出程序和遍歷程序的結(jié)果。4、

2、實驗設(shè)備（環(huán)境）及要求硬件：支持 intel pentium 及其以上 cpu ，內(nèi)存 128mb 以上、硬盤 1gb 以上容量的微機。軟件：配有 windows98/2000/xp 操作系統(tǒng)，安裝 visual c+ 。5、實驗時間：10學時6、該文檔的文件名不要修改，存入 命名的文件夾中7、該表中的數(shù)據(jù)只需填空，已有內(nèi)容不要修改實驗結(jié)果（運行結(jié)果界面及源程序，運行結(jié)果界面放在前面）：#include #include #include #include #define student etypestruct studentcharnumber8;charname8;charsex3;int

3、 age;charplace20;struct binarytreenodeetype data;binarytreenode *lchild;binarytreenode *rchild;struct qtypebinarytreenode *ptr;struct queueqtype *element;int front;int rear;int maxsize;struct node_ptrbinarytreenode*ptr; ;void creatqueue(queue &q,int maxqueuesize)/創(chuàng)建隊列q.maxsize=maxqueuesize;q.element

4、=new qtypeq.maxsize+1;q.front=0;q.rear=0;bool isempty(queue &q)/判斷隊列是否為空if(q.front=q.rear) return true;return false;bool isfull(queue &q)/判斷隊列是否為滿if(q.front=(q.rear+1)%(q.maxsize+1) return true;return false;bool getfront(queue &q,qtype &result)/取出隊頭元素if(isempty(q) return false;result=q.element(q.fro

5、nt+1)%(q.maxsize+1);return true;bool getrear(queue &q,qtype &result)/取出隊尾元素if(isempty(q) return false;result=q.elementq.rear;return true;bool enqueue(queue &q,qtype &x)/元素進隊if(isfull(q) return false;q.rear=(q.rear+1)%(q.maxsize+1);q.elementq.rear=x;return true;bool dequeue(queue &q,qtype &result)/元素

6、出隊if(isempty(q) return false;q.front=(q.front+1)%(q.maxsize+1);result=q.elementq.front;return true;binarytreenode *makenode(etype &x)/構(gòu)造節(jié)點binarytreenode *ptr;ptr=new binarytreenode;if(!ptr) return null;ptr-data=x;ptr-lchild=null;ptr-rchild=null;return ptr;void makebinarytree(binarytreenode *root, bi

7、narytreenode *left,binarytreenode *right)/構(gòu)造二叉樹之間的關(guān)系root-lchild=left;root-rchild=right;void outputbinarytreenode(binarytreenode *p)/輸出節(jié)點cout data.number data.sex data.age data.placeendl;coutendl;void levelorder_ltor_utod(binarytreenode *bt)/從左至右，從上至下按層次遍歷一棵二叉樹queue q;qtype temp;binarytreen

8、ode *p;int maxqueuesize=50;creatqueue(q,maxqueuesize);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);void levelorder_rtol_utod(binarytreenode *bt)/從右至左，從上至下按層次遍歷一棵二叉樹queue q;qtype temp;bin

9、arytreenode *p;int maxqueuesize=50;creatqueue(q,maxqueuesize);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);void levelorder_ltor_dtou(binarytreenode *bt)/從左至右，從下至上按層次遍歷一棵二叉樹queue q;qtype

10、temp;binarytreenode *p;int maxqueuesize=50;creatqueue(q,maxqueuesize);int frontkeep=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(int i=q.rear;ifrontkeep;i-)outputbinarytreeno

11、de(q.elementi.ptr);void levelorder_rtol_dtou(binarytreenode *bt)/從右至左，從下至上按層次遍歷一棵二叉樹queue q;qtype temp;binarytreenode *p;int maxqueuesize=50;creatqueue(q,maxqueuesize);int frontkeep=q.front;p=bt;temp.ptr=p;enqueue(q,temp);coutendl;cout 學號 姓名 性別 年齡 住址 endl;cout =lchild)temp.ptr=p-lchild;enqueue(q,tem

12、p);if(p-rchild)temp.ptr=p-rchild;enqueue(q,temp);for(int i=q.rear;ifrontkeep;i-)outputbinarytreenode(q.elementi.ptr);int binaryheight(binarytreenode *bt)/返回二叉樹的高度if(!bt) return 0;int highl=binaryheight(bt-lchild);int highr=binaryheight(bt-rchild);if(highlhighr)return +highl;elsereturn +highr;void bi

13、narydelete(binarytreenode *bt)/二叉樹刪除算法if(bt)binarydelete(bt-lchild);binarydelete(bt-rchild);delete bt;int binarynodesum(binarytreenode *bt)/計算二叉樹中的節(jié)點數(shù)if(!bt) return 0; queue q;qtype temp;binarytreenode *p;int maxqueuesize=50;int index=0;creatqueue(q,maxqueuesize);p=bt;temp.ptr=p;enqueue(q,temp);whil

14、e(p)if(!dequeue(q,temp) break;p=temp.ptr; /出隊成功index+;if(p-lchild)temp.ptr=p-lchild;enqueue(q,temp);if(p-rchild)temp.ptr=p-rchild;enqueue(q,temp);return index;void digitaltostring(char str,int n)chartemp;chark=1;inti=0;while (n & i80)k=n%10+48;n=n/10;stri=k;i+;stri=0;int len=strlen(str);for (i=0;ile

15、n/2;i+)temp=stri;stri=strlen-i-1;strlen-i-1=temp;char*getouputinformationstring(int widthofdata,char *outputinformation,char *outputstring)/將一個元素的字符串outputinformation轉(zhuǎn)換為寬度為widthofdata的等長字符串outputstring /例如，姓名是由四個字符組成，而widthofdata為8，則在姓名字符串的兩邊分別連接兩個字符，形成8個長度的字符串intleft_space,right_space;inti;charleft

16、_space_string16=;charright_space_string16=;intadd_space;intlen_outputinformation=strlen(outputinformation);/計算outputinformation的字符個數(shù)add_space=widthofdata - len_outputinformation;/計算需要補充的字符個數(shù)left_space=add_space/2;/計算outputinformation左邊需要補充的字符個數(shù)right_space=add_space-left_space;/計算outputinformation右邊需

17、要補充的字符個數(shù)for(i=1;i=left_space;i+)/形成outputinformation左邊需要補充的空格字符串strcat(left_space_string, );for(i=1;);break;case 2:strcat(outputinformation,elementk.ptr-data.number);break;case 3:strcat(outputinformation,elementk.ptr-data.place);break;case 4:strcat(outputinformation,elementk.ptr-data.sex);

18、break;case 5:digitaltostring(outputinformation,elementk.ptr-data.age);break;default:break;returnoutputinformation;/輸出二叉樹void outputbinarytree(binarytreenode *bt)node_ptrtemp,*element;binarytreenode *p;intmaxsize; intbinarytreehigh;inti,j,k;binarytreehigh=binaryheight(bt);maxsize=(int) pow(2,binarytr

19、eehigh);element = new node_ptr maxsize+1;/定義一個用于存放二叉樹結(jié)點指針的數(shù)組for (i=1;i=maxsize;i+)/對指針數(shù)組初始化，初值設(shè)為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-

20、rchild;element2*i+1=temp;intwidthofdata=5;intintervalofdata=3;/coutwidthofdata=widthofdataendl;/coutintervalofdata=intervalofdataendl;/coutbinarytreehigh=binarytreehighendl;intposition_of_central617;/存放每一元素輸出位置中心（距離屏幕左邊界的字符數(shù)）introw,col;/二維數(shù)組的行列下標變量for(i=0;i=binarytreehigh;i+)/存放每一元素輸出位置中心（距離屏幕左邊界的字符

21、數(shù)），初值為0for(j=0;j=pow(2,binarytreehigh-1);j+)position_of_centralij=0;for(i=1;i=pow(2,binarytreehigh)-1;i+)/對深度為binarytreehigh的滿二叉樹的所有結(jié)點計算每個結(jié)點輸出的中心點位置k=i*2;/k指向i的左子樹根結(jié)點while (k=pow(2,binarytreehigh)-1)/k不斷推進到i編號的結(jié)點左子樹中最右子孫結(jié)點k=2*k+1;k=k/2;/k的值就是i編號的結(jié)點左子樹中最右子孫結(jié)點的編號j=(int)(k-(pow(2,(binarytreehigh-1)-1);

22、/由k編號的結(jié)點換算出該結(jié)點是底層中從左至右第j個結(jié)點右上方/即編號為k的結(jié)點中心點垂直線左邊最底層上有j個結(jié)點row=(int)(log10(i)/log10(2)+1);/計算中心點值存放在position_of_centralrowcol中的rowcol=(int)(i-(pow(2,(row-1)-1);/計算中心點值存放在position_of_centralrowcol中的colif(row=binarytreehigh) /計算底層i結(jié)點距離左邊界的字符數(shù)，左邊無間隙position_of_centralrowcol= (j-1)*widthofdata + (j-1)*inte

23、rvalofdata + (widthofdata/2 +1);else/計算非底層i結(jié)點距離左邊界的字符數(shù)，position_of_centralrowcol=j*widthofdata + (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個結(jié)點的編號for(int item=1;item=item_max;ite

24、m+)/輸出每個數(shù)據(jù)元素多個item成員的值inthalf_len_pre_value=0;/同一行前一個輸出的元素值長度的一半,同一行第一個輸出的元素值前沒有值輸出，初值為0inthalf_len_now_value=widthofdata/2;/同一行當前輸出的元素值長度的一半，其值始終為widthofdata的一半kk=kkk;/kk是滿二叉樹中每一層結(jié)點的編號變化，從某層的最左邊第一個結(jié)點編號kkk開始for(j=1;j=pow(2,i-1);j+)/輸出滿二叉樹中同一層次上的每個數(shù)據(jù)元素的同一個成員的值charoutputinformation20=;char*outputinfor

25、mation;if (elementkk.ptr)/獲取每個數(shù)據(jù)元素的一個成員的值outputinformation，如姓名、年齡等outputinformation=getouputinformation(item,kk,outputinformation,element);if (position_of_centralij)/輸出數(shù)據(jù)中點值存在時，position_of_centralij非0charoutputstring80=;char*outputstring;/下面語句將每個數(shù)據(jù)元素的一個成員的值outputinformation，如姓名、年齡等，轉(zhuǎn)換為等長widthofdata的

26、字符串outputstringoutputstring=getouputinformationstring(widthofdata,outputinformation,outputstring);/生成兩個孩子之前的空格串prespace/構(gòu)成：= - - 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

27、;half_len_pre_value=widthofdata/2;/調(diào)整同一行前一個輸出的元素值長度為widthofdata的一半kk+;/if (position_of_centralij)/for(j=1;j=pow(2,i-1);j+)coutendl;/for(int item=1;item=5;item+)charline3=;charoutputline80;charmidspace80;intnodenumber;if(i=1)/對深度為binarytreehigh的滿二叉樹從上至下，從左至右的編號，計算第i層上起始結(jié)點的編號nodenumbernodenumber=1;els

28、enodenumber=(int)(pow(2,i)-1)-(pow(2,i-1)-1);/第i(i!=1)層上的第1個結(jié)點編號nodenumberfor(j=1;j=pow(2,i-1);j+)/輸出同一層次上的線條if(i=binarytreehigh)break;/最底層下面沒有線條，所以break/生成兩個數(shù)據(jù)元素之前的前導(dǎo)空格串prespacestrcpy(prespace,);m=(position_of_centrali+1j-position_of_centrali+1j-1-1);for(k=1;k=m;k+)strcat(prespace, );/計算左右兩個孩子之間一半的

29、連線outline，由若干個line構(gòu)成/注意line是漢字字符，一個占兩個字符位，m是左右兩個孩子之間的line數(shù)，所以m要除4strcpy(outputline,);m=(position_of_centrali+1j+1-position_of_centrali+1j-1)/4;for(k=1;k=m;k+)strcat(outputline,line);/計算左右兩個孩子之間一半的空格字符的個數(shù)m,，所以要除2。由m形成左右兩個孩子之間的空格串midspacestrcpy(midspace,);m=(position_of_centrali+1j+1-position_of_centr

30、ali+1j-1)/2;for(k=1;k=m;k+)strcat(midspace, );if (element2*nodenumber.ptr) & (element2*nodenumber+1.ptr)/左右子樹都存在時，左右兩個孩子上的連接線coutprespaceoutputlineoutputline;if (element2*nodenumber.ptr) & (!element2*nodenumber+1.ptr)/左子樹存在，右子樹不存在時，左右兩個孩子上的連接線coutprespaceoutputlinemidspace;if (!element2*nodenumber.p

31、tr) & (element2*nodenumber+1.ptr)/左子樹不存在，右子樹存在時左右兩個孩子上的連接線coutprespacemidspaceoutputline;if (!element2*nodenumber.ptr) & (!element2*nodenumber+1.ptr)/左子樹不存在，右子樹不存在時，沒有連接線，是空格串coutprespacemidspace midspace ;nodenumber=nodenumber+1;/結(jié)點編號加1coutendl;/for(i=1;i=binarytreehigh;i+)delete element;/釋放工作空間int

32、 main()binarytreenode*bt,*p11;etype x;int choice;char number8= ,001,002,003,004,005,006,007,008,009,010;char name8= ,百里,東郭,太史,聞人,公孫,赫連,鐘離,鮮魚,軒轅,南門;char sex3= ,女,男,女,男,女,女,男,男,女,男;char place20= ,重慶,長安,東莞,安慶,承德,四平,安穩(wěn),香港,金門,龍門;for(int i=1;i=10;i+)strcpy(x.number , numberi);strcpy( , namei);strcpy

33、(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)coutendl;cout*二叉樹的簡單運