成都信息工程學院計算機系課程實驗報告實驗課程：數(shù)據(jù)結(jié)構(gòu)實驗項目：數(shù)據(jù)結(jié)構(gòu)綜合設(shè)計之二叉樹遍歷算法指導教師李莉麗學生姓名:梅鉦琪學生學號：2012051114班級：應(yīng)用122實驗地點：6308實驗時間：實驗成績：評閱老師：一【上機實驗目的】1.掌握二叉樹的概念，包括二叉樹、滿二叉樹和完全二叉樹的定義。

2.掌握二叉樹的性質(zhì)。

重點掌握二叉樹的存儲結(jié)構(gòu)，包括二叉樹順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。重點掌握二叉樹的基本運算和各種遍歷算法的實現(xiàn)。二【實驗環(huán)境】PC機1臺,，VC++6.0，easyX圖形庫三【上機實驗內(nèi)容】數(shù)據(jù)結(jié)構(gòu)綜合設(shè)計之二叉樹遍歷算法四【上機調(diào)試程序流程圖】（用傳統(tǒng)流程圖的形式表示）打印相加后的多項式兩個多項式相加打印多項式打印相加后的多項式兩個多項式相加打印多項式

五【上機調(diào)試中出現(xiàn)的錯誤信息、錯誤原因及解決辦法】非遞歸后序遍歷時出現(xiàn)了問題，不能遍歷非完全二叉樹，后來用到，右孩子不存在或者已經(jīng)訪問過，root出棧并訪問，否則，不出棧，繼續(xù)訪問右孩子層次遍歷是開始想的是用棧來實現(xiàn)，但是很麻煩，還有問題，后來用隊列，解決了問題六【上機調(diào)試后的源程序及還存在的問題】#include<stdio.h>#defineMAXN100#include<windows.h>#include<graphics.h>structBTNode{chartag;BTNode*left;BTNode*right;};//二叉樹結(jié)點intX[10]={300,125,55,195,125,265,475,405,545,475};intY[10]={20,120,220,220,320,320,120,220,220,320};//動畫演示的坐標charB[21]={'A','B','C','#','#','D','E','#','#','F','#','#','G','H','#','#','I','J','#','#','#'};//固定動畫演示的charC[10]={'A','B','C','D','E','F','G','H','I','J'};intxx[10]={145,165,185,205,225,245,265,285,305,325};//輸出結(jié)果的橫坐標intflag=0;//標記是否進行動畫演示，0代表“不”，1代表“要”voidcreatree(BTNode**root)//動畫演示先序構(gòu)造二叉樹{ staticii=0; if(B[ii]=='#') { *root=NULL; ii++; } else { *root=newBTNode; (*root)->tag=B[ii]; ii++; creatree(&(*root)->left);creatree(&(*root)->right); }}/*先序方式創(chuàng)建二叉樹*/voidBuildBTree(BTNode**root){ charc; c=getchar(); if(c=='#') *root=NULL; else { *root=newBTNode; (*root)->tag=c; BuildBTree(&(*root)->left);BuildBTree(&(*root)->right); }}voidPreVisit(BTNode*root)//遞歸前序遍歷{ staticii=0; if(root!=NULL){ if(flag==0)//不動畫演示 { printf("%c",root->tag); } else//動畫演示 { for(inti=0;i<10;i++) { if(C[i]==root->tag) { setcolor(GREEN); fillcircle(X[i],Y[i],15); setcolor(GREEN); setbkmode(TRANSPARENT); setfont(20,20,"宋體"); outtextxy(X[i]-10,Y[i]-7,C[i]); setbkmode(OPAQUE); outtextxy(xx[ii],400,C[i]); ii++; break; } } Sleep(1500); } PreVisit(root->left); PreVisit(root->right); }}voidInVisit(BTNode*root)//遞歸中序遍歷{ staticii=0; if(root!=NULL) { InVisit(root->left); if(flag==0) { printf("%c",root->tag); } else { for(inti=0;i<10;i++) { if(C[i]==root->tag) { setcolor(500); fillcircle(X[i],Y[i],15); setcolor(500); setbkmode(TRANSPARENT); setfont(20,20,"宋體"); outtextxy(X[i]-10,Y[i]-7,C[i]); setbkmode(OPAQUE); outtextxy(xx[ii],400,C[i]); ii++; break; } } Sleep(1500); } InVisit(root->right); }}voidPostVisit(BTNode*root)//遞歸后序遍歷{ staticii=0; if(root!=NULL) { PostVisit(root->left); PostVisit(root->right); if(flag==0) { printf("%c",root->tag); } else { for(inti=0;i<10;i++) { if(C[i]==root->tag) { setcolor(GREEN); fillcircle(X[i],Y[i],15); setcolor(GREEN); setbkmode(TRANSPARENT); setfont(20,20,"宋體"); outtextxy(X[i]-10,Y[i]-7,C[i]); setbkmode(OPAQUE); outtextxy(xx[ii],400,C[i]); ii++; break; } } Sleep(1500); }}}voidNR_PreVisit(BTNode*root)//非遞歸前序遍歷{BTNode*s[MAXN]; //棧inttop=0; //頭指針 while(top!=0||root!=NULL) //如果結(jié)點不為空或棧不為空{(diào) while(root!=NULL) //如果結(jié)點不為空 {s[top]=root; //壓棧 printf("%c",s[top]->tag); //輸出結(jié)點 top++;root=root->left; //指向左孩子} if(top>0)//如果棧不為空{(diào) top--; //出棧root=s[top]; root=root->right;//指向右孩子 } }}voidNR_InVisit(BTNode*root)//非遞歸中序遍歷{ BTNode*s[MAXN]; //棧 inttop=0; //頭指針 while(top!=0||root!=NULL)//如果結(jié)點不為空或棧不為空 { while(root!=NULL)//如果結(jié)點不為空 { s[top++]=root;//壓棧 root=root->left; //指向左孩子 } if(top>0)//如果棧不為空 { root=s[--top]; printf("%c",root->tag); root=root->right; } }}voidNR_PostVisit(BTNode*root)//非遞歸后序遍歷{ BTNode*s[MAXN],*tmp=NULL; inttop=0; while(top!=0||root!=NULL) { while(root!=NULL) {s[top++]=root; root=root->left;} if(top>0){root=s[--top]; /*右孩子不存在或者已經(jīng)訪問過，root出棧并訪問*/ if((root->right==NULL)||(root->right==tmp)){ printf("%c",root->tag); tmp=root;//保存root指針root=NULL;//當前指針置空，防止再次入棧 } /*不出棧，繼續(xù)訪問右孩子*/else {top++;//與root=s[--top]保持平衡 root=root->right; } } }}voidCengci(BTNode*root)/*按層次遍歷*/{ staticii=0; BTNode*V[MAXN],*p; intfront=0,area=0;//隊列 if(root!=NULL) { area++; V[area]=root; while(front<area) { front++; p=V[front]; if(flag==0) { printf("%c",p->tag); } else { for(inti=0;i<10;i++) { if(C[i]==p->tag) { setcolor(500); fillcircle(X[i],Y[i],15); setcolor(500); setbkmode(TRANSPARENT); setfont(20,20,"宋體"); outtextxy(X[i]-10,Y[i]-7,C[i]); setbkmode(OPAQUE); outtextxy(xx[ii],400,C[i]); ii++; break; } } Sleep(1500); } if(p->left!=NULL) { area++;V[area]=p->left; } if(p->right!=NULL) { area++;V[area]=p->right; } } } return;}intmain(){ BTNode*root=NULL,*T=NULL; BuildBTree(&root);//頭指針的地址/*非動畫演示部分*/ printf("遞歸前序遍歷：");//遞歸遍歷 PreVisit(root); printf("\n"); printf("遞歸中序遍歷："); InVisit(root); printf("\n"); printf("遞歸后序遍歷："); PostVisit(root); printf("\n---------------------------------------------\n"); printf("非遞歸前序遍歷：");//非遞歸遍歷 NR_PreVisit(root); printf("\n"); printf("非遞歸中序遍歷："); NR_InVisit(root); printf("\n"); printf("非遞歸后序遍歷："); NR_PostVisit(root); printf("\n---------------------------------------------\n"); printf("層次遍歷：");//層次遍歷 Cengci(root); printf("\n---------------------------------------------\n"); printf("\n\n按任意鍵進行特例動畫演示。。。。。\n\n->"); system("pause"); /*動畫演示部分*/ flag=1; creatree(&T); initgraph(668,500); for(inti=0;i<10;i++) { setcolor(WHITE); fillcircle(X[i],Y[i],15); setcolor(500); setbkmode(TRANSPARENT); setfont(20,20,"宋體"); outtextxy(X[i]-10,Y[i]-7,C[i]); } setcolor(WHITE); setlinestyle(PS_SOLID,NULL,2); line(X[0]-15,Y[0]+15,X[1]+15,Y[1]-15);//畫線 line(X[1]-15,Y[1]+15,X[2]+15,Y[2]-15); line(X[1]+15,Y[1]+15,X[3]-15,Y[3]-15); line(X[3]-15,Y[3]+15,X[4]+15,Y[4]-15); line(X[3]+15,Y[3]+15,X[5]-15,Y[5]-15); line(X[0]+15,Y[0]+15,X[6]-15,Y[6]-15); line(X[6]-15,Y[6]+15,X[7]+15,Y[7]-15); line(X[6]+15,Y[6]+15,X[8]-15,Y[8]-15); line(X[8]-15,Y[8]+15,X[9]+15,Y[9]-15); setbkmode(OPAQUE); //動畫演示前序遍歷 setfont(16,16,"宋體"); setcolor(YELLOW); outtextxy(5,5,"前序遍歷:"); outtextxy(2,403,"遍歷結(jié)果:"); PreVisit(T); system("pause"); setbkmode(OPAQUE); //動畫演示中序遍歷 setfont(16,16,"宋體"); setcolor(YELLOW); outtextxy(5,5,"中序遍歷:"); InVisit(T); system("pause"); setbkmode(OPAQUE); //動畫演示后序遍歷 setfont(16,16,"宋體"); setcolor(YELLOW); outtextxy(5,5,"后序遍歷:"); PostVisit(T); system("pause"); setbkmode(OPAQUE); //動畫演示層次遍歷 setfont(16,16,"宋體"); setcolor(YELLOW); outtextxy(5,5,"層次遍歷:"); Cengci(T); system("pause"); closegraph(); return0;}七【上機實驗中的其他它問題及心得】上機實驗心得這次數(shù)據(jù)結(jié)構(gòu)綜合設(shè)計拿到的是，二叉樹遍歷算法。一開始還暗自竊喜，覺得，二叉樹遍歷嘛！遞歸嘛！非遞歸嘛！書上有的嘛！是的，是我高興的太早。第一個問題是，要求要動畫演示。動畫演示，還要變色。一開始想到，用easyX圖形庫，貼圖嘛，再一想，怎樣“動”？一想，怎樣動態(tài)畫圖形，一想，怎樣動態(tài)變色？啊。。。嗯，這是我第一次高興太早。沒事，先把遍歷實現(xiàn)了再說吧。我開始查閱教材書，上面有以先序方式建立的二叉樹，和遞歸前序遍歷和非遞歸中序遍歷的尾代碼。其他的都得自己寫。嗯，這是我第二次覺得高興的太早。第三，第四。。。也陸陸續(xù)續(xù)的來了。事已至此，何以為正？我只能老老實實的把它完成，否則我得掛科啊。不能掛，這個“強大的信念”，帶著我前進，知道完成。整個過程，遇到了很多很多問題。一開始，我全部用書上的代碼，從遞歸遍歷，完成了之后，我又從網(wǎng)上查閱了相關(guān)遞歸遍歷，然后我又把代碼做了一些簡化。像，不用visit()函數(shù)。這樣讓代碼看起來更簡單，易懂。然后又是非遞歸遍歷。開始，我也是用書上的尾代碼，將之完善。然后中序遍歷非遞歸通過。然后我又仿照中序遍歷寫前序和