成都信息工程学院计算机系
课程实验报告
一【上机实验目的】
1.掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。
2.掌握二叉树的性质。
3.重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。
4.重点掌握二叉树的基本运算和各种遍历算法的实现。
二【实验环境】
PC机1台,，VC++6.0，easyX图形库
三【上机实验内容】
数据结构综合设计之二叉树遍历算法
四【上机调试程序流程图】
（用传统流程图的形式表示）
五【上机调试中出现的错误信息、错误原因及解决办法】
非递归后序遍历时出现了问题，不能遍历非完全二叉树，后来用到，右孩子不存在或者已经访问过，root出栈并访问，否则，不出栈，继续访问右孩子
层次遍历是开始想的是用栈来实现，但是很麻烦，还有问题，后来用队列，解决了问题
六【上机调试后的源程序及还存在的问题】
#include<stdio.h>
#define MAXN 100
#include<windows.h>
#include<graphics.h>
struct BTNode
{
char tag;
BTNode *left;
BTNode *right;
};//二叉树结点
int X[10]={300,125,55,195,125,265,475,405,545,475};
int Y[10]={20,120,220,220,320,320,120,220,220,320};//动画演示的坐标
char B[21]={'A','B','C','#','#','D','E','#','#','F','#','#','G','H','#','#','I','J','#','#','#'};//固定动画演示的
char C[10]={'A','B','C','D','E','F','G','H','I','J'};
int xx[10]={145,165,185,205,225,245,265,285,305,325};//输出结果的横坐标
int flag=0;//标记是否进行动画演示，0 代表“不”，1 代表“要”
void creatree(BTNode **root)//动画演示先序构造二叉树
{
static ii=0;
if(B[ii] == '#')
{
*root=NULL;
ii++;
}
else
{
*root = new BTNode;
(*root)->tag = B[ii];
ii++;
creatree(&(*root)->left);
creatree(&(*root)->right);
}
}
/*先序方式创建二叉树*/
void BuildBTree(BTNode **root)
{
char c;
c = getchar();
if(c == '#')
*root=NULL;
else
{
*root = new BTNode;
(*root)->tag = c;
BuildBTree(&(*root)->left);
BuildBTree(&(*root)->right);
}
}
void PreVisit(BTNode *root)//递归前序遍历
{
static ii=0;
if(root!=NULL)
{
if (flag == 0)//不动画演示
{
printf("%c ", root->tag );
}
else//动画演示
{
for (int i=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);
}
}
void InVisit(BTNode *root)//递归中序遍历
{
static ii=0;
if(root!=NULL)
{
InVisit(root->left);
if (flag == 0)
{
printf("%c ", root->tag );
}
else
{
for (int i=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);
}
}
void PostVisit(BTNode *root)//递归后序遍历
{
static ii=0;
if(root!=NULL)
{
PostVisit(root->left);
PostVisit(root->right);
if (flag == 0)
{
printf("%c ", root->tag );
}
else
{
for (int i=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);
}
}
}
void NR_PreVisit(BTNode *root)//非递归前序遍历
{
BTNode *s[MAXN]; //栈
int top=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;//指向右孩子
}
}
}
void NR_InVisit(BTNode *root)//非递归中序遍历
{
BTNode *s[MAXN]; //栈
int top=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;
}
}
}
void NR_PostVisit(BTNode *root)//非递归后序遍历
{
BTNode *s[MAXN], *tmp=NULL;
int top=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;
}
}
}
}
void Cengci(BTNode *root) /* 按层次遍历 */
{
static ii=0;
BTNode *V[MAXN],*p;
int front=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 (int i=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;
}
int main()
{
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 (int i=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();
return 0;
}
七【上机实验中的其他它问题及心得】
上机实验心得
这次数据结构综合设计拿到的是，二叉树遍历算法。
一开始还暗自窃喜，觉得，二叉树遍历嘛！递归嘛！非递归嘛！书上有的嘛！是的，是我高兴的太早。
第一个问题是，要求要动画演示。动画演示，还要变色。一开始想到，用easyX图形库，
贴图嘛，再一想，怎样“动”？一想，怎样动态画图形，一想，怎样动态变色？啊。。。嗯，这是我第一次高兴太早。
没事，先把遍历实现了再说吧。我开始查阅教材书，上面有以先序方式建立的二叉树，和递归前序遍历和非递归中序遍历的尾代码。其他的都得自己写。嗯，这是我第二次觉得高兴的太早。第三，第四。。。也陆陆续续的来了。
事已至此，何以为正？我只能老老实实的把它完成，否则我得挂科啊。不能挂，这个“强大的信念”，带着我前进，知道完成。整个过程，遇到了很多很多问题。一开始，我全部用书上的代码，从递归遍历，完成了之后，我又从网上查阅了相关递归遍历，然后我又把代码做了一些简化。像，不用visit()函数。这样让代码看起来更简单，易懂。然后又是非递归遍历。开始，我也是用书上的尾代码，将之完善。然后中序遍历非递归通过。然后我又仿照中序遍历写前序和后序的时候，发现便不是像递归那样搬来就可以用了，出现了很多很多问题。
在栈的处理和逻辑上有很多的不一样，实现起来很是吃力。非递归让我费了很多时间和精力。我也在草稿纸上，反复花了栈的变化，还有在网上查询。皇天不负有心人，我终于搞懂了非递归栈的变化和处理。非递归的后序遍历是我最大的困扰。开始改了很久都不能遍历非完全二叉树，后来用到，右孩子不存在或者已经访问过，root出栈并访问，否则，不出栈，继续访问右孩子，终于也可以遍历非完全二叉树了，完成了非递归遍历后，我也从网上查了喝多相关的资料，然后也做了简化。比如，我书上的定义一个栈结构体，用initstack()初始化一个带头结点的空栈，push()压栈，pop()出栈，这些都简省了。我用BTNode *s[MAXN]这样的语句来模拟一个栈，用int定义一个top来压栈和出栈，s[top++]，s[top--]，来压栈，和出栈，这样一来，节省了很多代码，让程序看起来也很易懂。这也是我挺值得高兴的地方，让我知道，其实，栈，只是一个思想，一个先进后出的思想，怎样来灵活应用才是最重要的。这让我更加深刻地理解了栈。
实现了递归遍历和非递归遍历，我开始做动画演示。我开始一直在想怎样，想生成一个什么样的二叉树就生成一个什么样的二叉树，想了很久没摸着头脑。这时，从老师那里来了一个好消息，动画演示只是演示一个特定的例子。哈哈，所以我最大的困扰撇开了。凭着以前用过easyX图形库，所以画起二叉树来，也很快上手。当然，在做动画的过程中也遇到了各种各样的小问题，多想想，也迎刃而解了。
终于大功告成。这时，其他很多同学也还没做起。我开始想做一些加分的地方。我决定做层次遍历，层次遍历用到了队列的相关知识，处理起来也费时不少。
这次综合设计实验让我收获了很多，深刻了解了二叉树的相关概念，性质及存储。也深刻体会了栈的先进后出的特点，和队列先进先出的特点。同时体会到了，数据结构思想对程序设计的重要性。