《数据结构》上机实验报告(模版)

成都信息工程学院计算机系课程实验报告实验课程：数据结构实验项目：数据结构综合设计之二叉树遍历算法指导教师李莉丽学生姓名:梅钲琪学生学号：2012051114班级：应用122实验地点：6308实验时间：实验成绩：评阅老师：一【上机实验目的】1.掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。

2.掌握二叉树的性质。

重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。重点掌握二叉树的基本运算和各种遍历算法的实现。二【实验环境】PC机1台,，VC++6.0，easyX图形库三【上机实验内容】数据结构综合设计之二叉树遍历算法四【上机调试程序流程图】（用传统流程图的形式表示）打印相加后的多项式两个多项式相加打印多项式打印相加后的多项式两个多项式相加打印多项式

五【上机调试中出现的错误信息、错误原因及解决办法】非递归后序遍历时出现了问题，不能遍历非完全二叉树，后来用到，右孩子不存在或者已经访问过，root出栈并访问，否则，不出栈，继续访问右孩子层次遍历是开始想的是用栈来实现，但是很麻烦，还有问题，后来用队列，解决了问题六【上机调试后的源程序及还存在的问题】#include<stdio.h>#defineMAXN100#include<windows.h>#include<graphics.h>structBTNode{chartag;BTNode*left;BTNode*right;};//二叉树结点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};//输出结果的横坐标intflag=0;//标记是否进行动画演示，0代表“不”，1代表“要”voidcreatree(BTNode**root)//动画演示先序构造二叉树{ staticii=0; if(B[ii]=='#') { *root=NULL; ii++; } else { *root=newBTNode; (*root)->tag=B[ii]; ii++; creatree(&(*root)->left);creatree(&(*root)->right); }}/*先序方式创建二叉树*/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) //如果结点不为空或栈不为空{ while(root!=NULL) //如果结点不为空 {s[top]=root; //压栈 printf("%c",s[top]->tag); //输出结点 top++;root=root->left; //指向左孩子} if(top>0)//如果栈不为空{ top--; //出栈root=s[top]; root=root->right;//指向右孩子 } }}voidNR_InVisit(BTNode*root)//非递归中序遍历{ BTNode*s[MAXN]; //栈 inttop=0; //头指针 while(top!=0||root!=NULL)//如果结点不为空或栈不为空 { while(root!=NULL)//如果结点不为空 { 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]; /*右孩子不存在或者已经访问过，root出栈并访问*/ if((root->right==NULL)||(root->right==tmp)){ printf("%c",root->tag); tmp=root;//保存root指针root=NULL;//当前指针置空，防止再次入栈 } /*不出栈，继续访问右孩子*/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,"遍历结果:"); 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;}七【上机实验中的其他它问题及心得】上机实验心得这次数据结构综合设计拿到的是，二叉树遍历算法。一开始还暗自窃喜，觉得，二叉树遍历嘛！递归嘛！非递归嘛！书上有的嘛！是的，是我高兴的太早。第一个问题是，要求要动画演示。动画演示，还要变色。一开始想到，用easyX图形库，贴图嘛，再一想，怎样“动”？一想，怎样动态画图形，一想，怎样动态变色？啊。。。嗯，这是我第一次高兴太早。没事，先把遍历实现了再说吧。我开始查阅教材书，上面有以先序方式建立的二叉树，和递归前序遍历和非递归中序遍历的尾代码。其他的都得自己写。嗯，这是我第二次觉得高兴的太早。第三，第四。。。也陆陆续续的来了。事已至此，何以为正？我只能老老实实的把它完成，否则我得挂科啊。不能挂，这个“强大的信念”，带着我前进，知道完成。整个过程，遇到了很多很多问题。一开始，我全部用书上的代码，从递归遍历，完成了之后，我又从网上查阅了相关递归遍历，然后我又把代码做了一些简化。像，不用visit()函数。这样让代码看起来更简单，易懂。然后又是非递归遍历。开始，我也是用书上的尾代码，将之完善。然后中序遍历非递归通过。然后我又仿照中序遍历写前序和