数据结构实验报告二叉树的实现与遍历_二叉树的遍历实验报告
数据结构实验报告二叉树的实现与遍历由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树的遍历实验报告”。
《数据结构》 第六次实验报告
学生姓名 学生班级 学生学号 指导老师
重庆邮电大学计算机学院 计算机专业实验中心
一、实验内容
1)采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。2)输出树的深度，最大元，最小元。
二、需求分析
遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法： 首先介绍先序遍历：
先序遍历的顺序是根 左 右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：
中序遍历的顺序是左 根 右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历：
后序遍历的顺序是左 右 根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。
三、详细设计
源代码：
#include #define MAX 100 //表示栈的最大容量 #define FULL 99//表示栈满 #define EMPTY-1//表示栈空
typedef struct Tnode //定义结点 {
char data;//存储结点数据
struct Tnode *left;//定义结点左子指针 struct Tnode *right;//定义右子指针
}Tnode,*Pnode;//声明Tnode类型的变量和指针 typedef struct Stack//定义栈 { Pnode pnode[MAX];//存放数据 int p;//栈顶指针
}Stack,*Pstack;//定义Stack类型的变量和指针 void Push(Pstack pstack,Pnode pnode)//入栈 {
} Pnode Pop(Pstack pstack)//出栈 { } Pnode Top(Pstack pstack)//看栈顶元素 { } int Isempty(Pstack pstack)//栈判空 {
} int Isfull(Pstack pstack)//栈满 {
} void Initstack(Pstack pstack)//初始化栈 if(pstack->p==FULL)else return 0;return 1;if(pstack->p==EMPTY)else return 0;;return 1;return pstack->pnode[pstack->p];return pstack->pnode[pstack->p--];pstack->p ++;pstack->pnode[pstack->p] = pnode;//赋值
{ } void Inittnode(Pnode root,Pnode left,Pnode right,char data)//初始化结点 {
} void PreorderR(Pnode proot)//递归先序遍历算法 {
} void InorderR(Pnode proot)//递归中序遍历算法 {
} void PostorderR(Pnode proot)//递归后序遍历算法 {
} void PreorderI(Pnode proot,Pstack pstack)//非递归先序遍历算法 {
Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//如果栈空并且结点指针空，则结束循环 {
if(proot){ printf(“%2c”,proot->data);if(proot){
} PostorderR(proot->left);PostorderR(proot->right);printf(“%2c”,proot->data);if(proot){
}
InorderR(proot->left);printf(“%2c”,proot->data);InorderR(proot->right);if(proot){
} printf(“%2c”,proot->data);PreorderR(proot->left);PreorderR(proot->right);root->left=left;root->right = right;root->data = data;pstack->p=EMPTY;
}
}
} else {
} if(Isfull(pstack))//如果栈满不能执行入栈操作 {
} Push(pstack,proot);//入栈 proot=proot->left;//指针指向左子 printf(“栈满，不能执行入栈操作！”);return;if(Isempty(pstack))//栈空时不能出栈 {
} proot = Pop(pstack);//执行出栈操作 proot=proot->right;//指针指向右子 printf(“栈空，不能执行出栈操作！”);return;void InorderI(Pnode proot,Pstack pstack)//非递归中序遍历算法 {
Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//循环结束条件 {
if(proot){
} else {
if(Isempty(pstack)){
} proot = Pop(pstack);//出栈
printf(“%2c”,proot->data);//打印数据 printf(“栈空，不能执行出栈操作！”);return;if(Isfull(pstack)){
} Push(pstack,proot);//执行入栈操作 proot = proot->left;//指针指向左子 printf(“栈满，不能执行入栈操作！”);return;
}
} } proot=proot->right;//指针指向右子
void PostorderI(Pnode proot,Pstack pstack)//非递归后续遍历算法 {
} void main(){ int flags[MAX];//定义标志位栈 int p =-1;//初始化标志位栈 int flag;//存放标志位 Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//循环结束条件 {
} if(proot){
} else {
} proot = Pop(pstack);//指针出栈 flag = flags[p--];//相应标志位出栈
if(flag==0)//如果标志位为0表示右子还未访问过 {
} else {
} printf(“%2c”,proot->data);//打印数据 proot = NULL;//将结点指针置空 flag =1;//将标志位置1，右子已访问 flags[++p] = flag;//标志位入栈 Push(pstack,proot);//结点入栈 if(Isfull(pstack)){
} flags[++p] = 0;//标志位置0，并入栈 Push(pstack,proot);//结点入栈 proot=proot->left;//指针指向左子 printf(“栈满，不能执行入栈操作！”);return;
proot = proot->right;//指针指向右子
Tnode A,B,C,D,E,F,G;//声明结点变量 Stack stack;//声明栈
Inittnode(&A,&B,&C,'A');//初始化结点 Inittnode(&B,NULL,&D,'B');Inittnode(&C,&E,&F,'C');Inittnode(&D,NULL,NULL,'D');Inittnode(&E,NULL,NULL,'E');Inittnode(&F,&G,NULL,'F');Inittnode(&G,NULL,NULL,'G');printf(“你定义的树的结构是：n”);printf(“A(B(D)C(E F(G)))n”);printf(“=====================下面是遍历结果====================n”);printf(“=====================递归先序遍历：====================n”);PreorderR(&A);printf(“n”);printf(“=====================非递归先序遍历：==================n”);PreorderI(&A,&stack);printf(“n”);printf(“=====================递归中序遍历：====================n”);InorderR(&A);printf(“n”);printf(“=====================非递归中序遍历：==================n”);InorderI(&A,&stack);printf(“n”);PostorderR(&A);printf(“n”);PostorderI(&A,&stack);
printf(“n”);
/*一下是调用相应的函数输出遍历结果*/
}
printf(“=====================递归后序遍历：====================n”);
printf(“=====================非递归后序遍历：==================n”);
五、遇到的问题及解决办法
这部分我主要遇到如下两个问题，其内容和解决方法如下所列：
执行程序时程序停止运行，其效果如图：
解决方法：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不合理，因此对调用的自定义函数进行相应的改动，将参数由具体类型改为指针类型后，程序正常运行。
程序不停的输出同一个结点的数据，其效果入图：
解决方法：分析运行结果可知，第一不停的输出证明遇到了死循环，第二输出的是同一个结点的数据，表示指针没有按预期进行指向，首先对程序进行调试，发现程序没有添加循环结束条件，添加循环结束条件后，只能输出树的部分结点的数据，对标志位进行修改后，程序运行正常，也能正确输出遍历结果。
六、心得体会
通过这次作业真的受益匪浅，感触良多：
首先，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，更不能眼高手低。眼高手低，懒得动手，这就犯了编程人员的大忌。大一我们开始接触C语言，这是我们接触到的第一种编程语言，但是当时徒有对编程的兴趣，却没有付诸行动，动手少，结果考试险过，通过这次作业，我再次看了C语言课本，边看边写代码，理解快，印象深刻，思维也活跃许多，状态也好，真正的意识到，编程能力需要靠实践来提升。当自己写出意想的程序后，真的有些成就感。再者，在吴老师的指导和要求下，我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很多，认真完成好每一项任务，这样无形中提高了对自己的要求，同时也增强了我们的动手能力和编程能力。
七、附录 运行结果截图。
