第1篇：二叉树遍历
目录
一 设计思想..........................................2 1递归遍历二叉树算法思想：.......................................2 2非递归遍历二叉树算法思想：.....................................2
二 算法流程图........................................4 三 源代码............................................4 四 运行结果.........................................16 五 遇到的问题及解决.................................16 1遇到的问题：..................................................16 2解决方法：....................................................16 六 心得体会.........................................17
一 设计思想
1递归遍历二叉树算法思想：
（1）先序遍历：首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。若二叉树非空，则依次进行如下操作：（1）访问跟结点；（2）前序遍历左子树；（3）前序遍历右子树。
（2）中序遍历：首先判断根结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。若二叉树非空，则依次进行如下操作：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
（3）后序遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。若二叉树非空，则依次进行如下操作：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
2非递归遍历二叉树算法思想：
（4）先序遍历：建立一个栈，当指针到达根结点时，打印根结点，并进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈判断前一元素是否有右结点一直到有右结点为止，有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左
2 右指向子结点的指针都为空结束循环即完成了先序遍历
（5）中序遍历：建立一个栈，当指针到达根结点时，结点进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈，每次弹栈都读取结点，然后判断前一元素是否有右结点一直到有右结点为止，有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了中序遍历
（6）后序遍历：建立一个栈，并建立一个数组，数组伴随进栈出栈更改对应的值，数组里的数值代表进栈次数，1代表进栈1次，2代表进栈两次。当指针到达根结点时，进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈判断前一元素是否有右结点若没有或已经进栈两次则读取结点的值并继续弹栈，一直到有右结点且只进过一次栈为止，然后将其第二次进栈，并将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了后序遍历。
3 二 算法流程图
开始T传入根结点T==Null？结点是否为空 No结束YesVisit（T）打印根结点的值T->child访问左子结点T->child访问右子结点
表1 递归先序流程图
开始T结束T==Null？ T->childVisit（T）
表2 递归中序遍历流程图
T->child5
开始T结束T==Null？ T->childT->child
表3 递归后序遍历流程图
Visit（T）
开始T，st传入树根指针，和栈指针a=T;b=T;aa！=Null有左子结点Yesvisit(a);IntoStack(st,a);a=a->lchild;NoOutStack(st,&b);Yes b=b->rchild;Yes St->top!=1栈不空No bvisit(b);IntoStack(st,b);a=b->lchild;b!=NULL有右子结点Yes No st->top!=1&&b==NULL栈不空且没有右子结点Yes OutStack(st,&b);b=b->rchild;st->top!=1&&(a!=NULL||b!=NULL)栈不空且有子节点No 结束No
表4 非递归先序遍历流程图
7 开始T，sta=T;b=T;aa！=NullNoOutStack(st,&b);visit(b);Yes b=b->rchild;YesIntoStack(st,a);a=a->lchild;St->top!=1Yes bb!=NULLYes No IntoStack(st,b);a=b->lchild;NoIntoStack(st,b);a=b->lchild;YesNob!=NULLst->top!=1&&b==NULLYes OutStack(st,&b);visit(b);b=b->rchild;No 结束表5 非递归后序遍历流程图
st->top!=1&&(a!=NULL||b!=NULL)No
8 开始T，sta=T;b=T;int i[max];int j=0;aa！=NullNoOutStack(st,&b);--j;a=b;b=b->rchild;YesIntoStack(st,a);i[j++]=1;a=a->lchild;Yes St->top!=1Yes bb!=NULLNoNo Yes IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;a=b->lchild;visit(a);IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;a=b->lchild;Yesvisit(a);a=NULL;b=NULL;Noi[j]!=2&&b!=NULLst->top!=1&&b==NULLYes OutStack(st,&b);--j;a=b;b=b->rchild;No 结束st->top!=1&&(a!=NULL||b!=NULL)No
表6 非递归后序遍历流程图
9 三 源代码
#include #include #define size sizeof(Bitreea)#define max 500 typedef struct Bitreea{ char data;struct Bitreea *lchild,*rchild;}Bitreea,*B;//树结点 typedef struct stack {int top;
B s[max];}stack;//创建栈
void IntoStack(stack *st,B in){
if(st->top==max-1){printf("wrong");}
st->s[(st->top)++]=in;}//进栈函数
void OutStack(stack *st,B *out){
if(st->top==0){printf("wrong");}
*out=st->s[--(st->top)];}//出栈函数 void visit(B T){ if(T->data!='#'){printf("%c ",T->data);} }//访问结点的值
10 int creatBitree(B &T){ char data;scanf("%c",&data);if(data=='#'){T=NULL;} else{
T=(Bitreea*)malloc(sizeof(Bitreea));
T->data=data;
creatBitree(T->lchild);creatBitree(T->rchild);}return(0);}//先序创建二叉树 //递归遍历二叉树 int pre(B T){ if(T!=NULL){visit(T);pre(T->lchild);pre(T->rchild);} }//先序遍历 int zhong(B T){ if(T!=NULL){
zhong(T->lchild);visit(T);zhong(T->rchild);} }//中序遍历 int hou(B T){ if(T!=NULL){ hou(T->lchild);
hou(T->rchild);
11 } visit(T);}//后序遍历
//非递归遍历
int fpre(B T, stack *st){B a,b;a=T;b=T;
do{
if(a!=NULL){visit(a);IntoStack(st,a);a=a->lchild;}
else
{if(st->top!=1)
{OutStack(st,&b);b=b->rchild;
if(b!=NULL)
{
visit(b);IntoStack(st,b);a=b->lchild;
}
else { while(st->top!=1&&b==NULL){OutStack(st,&b);b=b->rchild;
if(b!=NULL){ visit(b);IntoStack(st,b);a=b->lchild;
}
}
}
}
}
}while(st->top!=1&&(a!=NULL||b!=NULL));} //先序遍历 int fzhong(B T, stack *st){B a,b;a=T;b=T;
do{
if(a!=NULL){IntoStack(st,a);a=a->lchild;}
else
{if(st->top!=1)
{
OutStack(st,&b);visit(b);b=b->rchild;if(b!=NULL)
{
IntoStack(st,b);a=b->lchild;
}
else { while(st->top!=1&&b==NULL){OutStack(st,&b);visit(b);b=b->rchild;
if(b!=NULL){ IntoStack(st,b);a=b->lchild;
}
}
}
}
}
}while(st->top!=1&&(a!=NULL||b!=NULL));} //中序遍历 int fhou(B T, stack *st){B a,b;a=T;b=T;int i[max];int j=0;
do{
if(a!=NULL){IntoStack(st,a);i[j++]=1;a=a->lchild;}
else
{if(st->top!=1)
{
OutStack(st,&b);--j;a=b;b=b->rchild;if(b!=NULL){
IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;a=b->lchild;
}
else {visit(a);while(st->top!=1&&b==NULL){OutStack(st,&b);--j;a=b;b=b->rchild;
if(i[j]!=2&&b!=NULL){IntoStack(st,a);i[j++]=2;IntoStack(st,b);i[j++]=1;
a=b->lchild;
}else{
visit(a);a=NULL;b=NULL;
}
}
}
}
}
}while(st->top!=1&&(a!=NULL||b!=NULL));} //后序遍历 int main(){
stack st;st.top=1;B;creatBitree();printf("递归:nn");printf("
先序：");pre();printf("nn");printf("
中序：");zhong();printf("nn");printf("
后序：");hou();
14 printf("nn");printf("非递归:nn");printf("
先序：");fpre(,&st);printf("nn");printf("
中序：");fzhong(,&st);printf("nn");printf("
后序：");fhou(,&st);printf("nn");system("pause");}//主函数
15 四 运行结果
表7 运行结果
五 遇到的问题及解决
1遇到的问题：
(1)在非递归遍历中遇到结点值两次进栈的问题，在弹栈过程中虽然弹出同一值但根据进栈的次数不同处理方式不同必须有一标示指出结点是否已进过两次栈。
(2)树结点的返回查找问题，由于二叉树总是由根节点指向子节点的所以查到左子节点就不能查找右节点了。
2解决方法：
（1）创建了一个数组数组里的每一项存的值会根据结点的进栈出栈做出相应的改变在进行处理是添加对数组值得判断以保证结点不会第三次进栈。
（2）创建一个栈来保存根节点，当需要查询右节点是弹栈返回查找右节点。
16 六 心得体会
课程设计期间，遇见一些问题，一个就是怎样后序非递归遍历二叉树，经过分析和斟酌，终于得到比较满意的程序，使得这个程序变得有一点意义。这一次的课程设计给我们提供了一个既能动手又动脑，独立实践的机会，应该紧紧抓住这个机会把所学的专业课程进一步的巩固和加深，进一步培养我们的综合能力。灵活运用各种数据类型组成一个具有系统性的程序。在这之中，虽然每个人的思路不一样，但是拿一颗真诚热心去探讨问题就能更好的解决问题。我们应该更能了解我们自己，自己还是太嫩，需要我们学习的还有很多很多，成功是百分之九十九的汗水加上百分之一的灵感，所以我们的路还很长很长，或许是万里长城，或许还要翻山越岭，但是我们都应该永不放弃，不断提高，更好地运用课堂学习的知识。通过这次作业我学到了很多东西，将以前学过的C语言知识与现在的课堂知识进行结合应用。重要的是使我知道了自学知识和合作的重要性，提高了自己动手能力和沟通能力，学到了许多解决实际问题的宝贵经验．同时也挖掘出了我们潜在的能力，使我们对编程更有兴趣。我相信，只要努力、勤奋、坚持不懈，就没有什么做不到的事，不能还没开始就退缩，要勇于拼搏，敢于创新。总之，在通过又一次的真正动手之后，我在C语言设计方面获益匪浅，我会更加努力的学习编程方面的更多知识，提高自己的能力。然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较。
注：源代码可以优化，从流程图可以看出，自己修改了
第2篇：二叉树的遍历
# include # include typedef int Etype;typedef struct BiTNode /* 树结点结构 */
{ Etype data;
struct BiTNode *lch,*rch;
}BiTNode;/* 函数原形声明 */ BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void numb1(BiTNode *p);void numb2(BiTNode *p);void numb3(BiTNode *p);BiTNode *t;int n,n0,n1,n2;/* 主函数 */ main(){ char ch;int k;
do { printf("nnn");
printf("nn
1.建立二叉树方法1 ");
printf("nn
2.建立二叉树方法2");
printf("nn
3.前序递归遍历二叉树");
printf("nn
4.中序递归遍历二叉树");
printf("nn
5.后序递归遍历二叉树");
printf("nn
6.前序计算树中结点个数");
printf("nn
7.中序计算树中结点个数");
printf("nn
8.后序计算树中结点个数");
printf("nn
9.结束程序运行");
printf("n======================================");
printf("n
请输入您的选择(1-9)");scanf("%d",&k);
switch(k)
{ case 1:t=creat_bt1();break;/* 调用性质5建立二叉树算法 */
case 2:t=creat_bt2();break;/* 调用递归建立二叉树算法
*/
case 3: { preorder(t);
/* 调用前序遍历
*/
printf("nn
打回车键，继续。");ch=getch();
} break;
case 4: { inorder(t);
/* 调用中序遍历
*/
printf("nn
打回车键，继续。");ch=getch();
} break;
case 5: { postorder(t);
/* 调用后序遍历
*/
printf("nn
打回车键，继续。");ch=getch();
} break;
case 6:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb1(t);
printf("n
二叉树结点总数 n=%d",n);
printf("n
二叉树叶子结点数 n0=%d",n0);
printf("n
度为1的结点数 n1=%d",n1);
printf("n
度为2的结点数 n2=%d",n2);
printf("nn
打回车键，继续。");ch=getch();
} break;
case 7:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb2(t);
printf("n
二叉树结点总数 n=%d",n);
printf("n
二叉树叶子结点数 n0=%d",n0);
printf("n
度为1的结点数 n1=%d",n1);
printf("n
度为2的结点数 n2=%d",n2);
printf("nn
打回车键，继续。");ch=getch();
} break;
case 8:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb3(t);
printf("n
二叉树结点总数 n=%d",n);
printf("n
二叉树叶子结点数 n0=%d",n0);
printf("n
度为1的结点数 n1=%d",n1);
printf("n
度为2的结点数 n2=%d",n2);
printf("nn
打回车键，继续。");ch=getch();
} break;
case 9: exit(0);
} /* switch */
printf("n----------------");
}while(k>=1 && k
printf("n
再见！");
printf("n
打回车键，返回。");ch=getch();} /* main */
/* 利用二叉树性质5，借助一维数组V 建立二叉树 */ BiTNode *creat_bt1(){ BiTNode *t,*p,*v[20];int i,j;Etype e;
/* 输入结点的序号i、结点的数据e */
printf("n 序号i,数据data=?");scanf("%d%d",&i,&e);
while(i!=0 && e!=0)
/* 当 i ,e都为0时，结束循环
*/
{ p=(BiTNode *)malloc(sizeof(BiTNode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
/* 序号为1的结点是根 */
else{ j=i/2;
if(i%2==0)v[j]->lch=p;/* 序号为偶数，做左孩子*/
else
v[j]->rch=p;/* 序号为奇数，做右孩子*/
}
printf("n i,data=?");scanf("%d%d",&i,&e);
}
return(t);} /* creat_bt1 */ /* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2()
{ BiTNode *t;
int e;
printf("n data=");scanf("%d",&e);
if(e==0)t=NULL;
/* 对于0值，不分配新结点 */
else { t=(BiTNode *)malloc(sizeof(BiTNode));
t->data=e;
t->lch=creat_bt2();/* 左孩子获得新指针值
*/
t->rch=creat_bt2();/* 右孩子获得新指针值
*/
}
return(t);
} /* creat_bt2 */ /* 前序递归遍历二叉树
*/ void preorder(BiTNode *p){ if(p){
printf("%3d",p->data);
preorder(p->lch);
preorder(p->rch);
} } /* preorder */ /* 中序递归遍历二叉树
*/ void inorder(BiTNode *p){ if(p){ inorder(p->lch);
printf("%3d",p->data);
inorder(p->rch);
} } /* inorder */ /* 后序递归遍历二叉树
*/ void postorder(BiTNode *p){ if(p){
postorder(p->lch);
postorder(p->rch);
printf("%3d",p->data);
} } /* posorder */ /* 利用前序递归遍历二叉树的方法，计算树中结点个数 */ void numb1(BiTNode *p){ if(p){
{ printf("%3d",p->data);
n++;
if(p->lch==NULL && p->rch==NULL)n0++;
if((p->lch==NULL && p->rch!=NULL)||
(p->lch!=NULL && p->rch==NULL))n1++;
if(p->lch!=NULL && p->rch!=NULL)n2++;
}
numb1(p->lch);
numb1(p->rch);
} } /* numb1 */
/* 利用中序递归遍历二叉树的方法，计算树中结点个数 */ void numb2(BiTNode *p){ if(p){ numb2(p->lch);
{ printf("%3d",p->data);
n++;
if(p->lch==NULL && p->rch==NULL)n0++;
if((p->lch==NULL && p->rch!=NULL)||
(p->lch!=NULL && p->rch==NULL))n1++;
if(p->lch!=NULL && p->rch!=NULL)n2++;
}
numb2(p->rch);
} } /* numb2 */
/* 利用后序递归遍历二叉树的方法，计算树中结点个数 */ void numb3(BiTNode *p){ if(p){ numb3(p->lch);
numb3(p->rch);
{ printf("%3d",p->data);
n++;
if(p->lch==NULL && p->rch==NULL)n0++;
if((p->lch==NULL && p->rch!=NULL)||
(p->lch!=NULL && p->rch==NULL))n1++;
if(p->lch!=NULL && p->rch!=NULL)n2++;
}
} } /* numb3 */
第3篇：数据结构实验报告——中序遍历二叉树
班级：380911班
学号：57000211 姓名：徐敏
实验报告
一，实验目的：
·掌握二叉树的链式存储结构； ·掌握构造二叉树的方法；
·加深对二叉树的中序遍历的理解； 二，实验方法：
·用递归调用算法中序遍历二叉树。三，实验步骤：
·通过链式存储建立一颗二叉树。
·设计一个算法实现中序遍历二叉树。四，具体实验步骤：
#include #include #define LEFT 0 #define RIGHT 1 #define TRUE 1 #define FALSE 0
typedef struct _BTNODE{ char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE;
void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p);
void main(){ PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf("Input the data:");ConstructBTree(p);PrintBTree(p,0);printf("Now InorderTraverse:");InorderTraverse(p);printf("nPre any key to continue...");getchar();}
void PrintBTree(PBTNODE p,int depth){
班级：380911班
学号：57000211 姓名：徐敏
int i;if(p==NULL){
return;}else{ for(i=0;i
printf("--");} printf(">");
printf("%cn",p->c);
PrintBTree(p->lchild,depth+1);
PrintBTree(p->rchild,depth+1);} }
void ConstructBTree(PBTNODE p){ int side;char c;side=LEFT;while(TRUE){
scanf("%c",&c);
if(c=='n'){
//printf("EOFn");
return;
} // printf("%dn",c);
switch(c){
case '|':
break;
case')':
return;
case',':
side=RIGHT;
break;
case'(':
if(side==LEFT){
if(p->lchild==NULL){
p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));
}
ConstructBTree(p->lchild);
}else{
if(p->rchild==NULL){
p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));
}
班级：380911班
学号：57000211 姓名：徐敏
ConstructBTree(p->rchild);
}
break;
default:
if(side==LEFT){
p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));
p->lchild->c=c;
}else{
p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));
p->rchild->c=c;
}
} } }
void InorderTraverse(PBTNODE p){ if(p==NULL){
return;}else{
InorderTraverse(p->lchild);
printf("[%c] ",p->c);
InorderTraverse(p->rchild);} return;} 五，实验过程：
·输出：Input the date;
·输入：1(2(3,4),5(6,7));
·输出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上机实验体会：
·体会到熟练掌握各种程序算法的重要性；
·通过上机练习，充分理解了链式建立二叉树的算法；
·形象的了解二叉树的结构，能够熟练的进行先序，中序，后序遍历二叉树。
第4篇：二叉树的遍历算法
实验三 二叉树遍历算法
一、实验目的1． 进一步理解掌握二叉树二叉链表存储结构。2． 掌握二叉树遍历的递归与非递归算法。
二、实验要求
1． 认真阅读和掌握（先序、中序、后序和层次）遍历的递归与非递归算法。2． 上机调试（先序、中序、后序和层次）遍历的递归与非递归算法。3． 保存和打印出程序的运行结果，并结合程序进行分析。
4． 上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。
三、实验内容
先序、中序、后序遍历的递归与非递归算法和层次遍历的算法实现
程序：
#include "stdio.h" #include "stdlib.h" #include "conio.h" #define maxsize 100 typedef int datatype;typedef struct bnode{ datatype data;struct bnode *lchild,*rchild;}bnode,*btree;typedef struct { bnode *node;int flag;}DataType;typedef struct{ DataType data[maxsize];int top;}SeqStack,*PSeqStack;typedef struct { btree data[maxsize];int front,rear;}SeqQueue,*PSeqQueue;typedef struct{ btree data[maxsize];int top;}SeqStack1,*PSeqStack1;//建立一个二叉树
btree create(){ btree t;char ch;scanf("%c",&ch);if(ch=='?')
t=NULL;else {
t=(btree)malloc(sizeof(bnode));
t->data=ch;
t->lchild=create();
t->rchild=create();} return t;} //先序遍历
//入栈操作
void push1(PSeqStack1 s,btree sq){ if(s->top==maxsize-1)
printf("栈满不得入栈");else {
s->top++;
s->data[s->top]=sq;} } //出栈操作
void pop1(PSeqStack1 s,btree *sq){ if(s->top==-1)
printf("栈空不得出栈");else {
*sq=s->data[s->top];
s->top--;} } //先序遍历的递归算法
void PreOrder1(btree t){ if(t){
printf("%c",t->data);
PreOrder1(t->lchild);
PreOrder1(t->rchild);} } //先序遍历的非递归算法
void PreOrder2(btree t){ PSeqStack1 s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btree p=t;s->top=-1;while(p||s->top!=-1){
if(p)
{
printf("%c",p->data);
push1(s,p);
p=p->lchild;
}
else
{
pop1(s,&p);
p=p->rchild;
} } } //中序遍历的递归算法
void InOrder1(btree t){ if(t){
InOrder1(t->lchild);
printf("%c",t->data);
} } InOrder1(t->rchild);//中序遍历的非递归算法
void InOrder2(btree t){ PSeqStack1 s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btree p=t;s->top=-1;while(p||s->top!=-1){
if(p)
{
push1(s,p);
p=p->lchild;
}
else
{
pop1(s,&p);
printf("%c",p->data);
p=p->rchild;
} } } //后序遍历的递归算法
void PostOrder1(btree t){ if(t){
//t=(btree)malloc(sizeof(bnode));
PostOrder1(t->lchild);
PostOrder1(t->rchild);
printf("%c",t->data);} } //后序遍历的非递归算法
//入栈操作
void push(PSeqStack s,DataType sq){ if(s->top==maxsize-1)
printf("栈满不得入栈");else {
s->top++;
s->data[s->top]=sq;} } //出栈操作
void pop(PSeqStack s,DataType *sq){ if(s->top==-1)
printf("栈空不得出栈");else {
*sq=s->data[s->top];
s->top--;} } //后序遍历的非递归算法
void PostOrder2(btree t){ PSeqStack s;DataType sq;btree p=t;s=(PSeqStack)malloc(sizeof(SeqStack));s->top=-1;while(p||s->top!=-1){
if(p)
{
//s=(PSeqStack)malloc(sizeof(SeqStack));
sq.flag=0;sq.node=p;
push(s,sq);
p=p->lchild;
}
else
{
pop(s,&sq);
p=sq.node;
if(sq.flag==0)
{
sq.flag=1;
push(s,sq);
p=p->rchild;
}
}
} } else { printf("%c",p->data);p=NULL;} //按照层次遍历二叉树
//队列的初始化 PSeqQueue init(){ PSeqQueue q;q=(PSeqQueue)malloc(sizeof(SeqQueue));if(q){
q->front=0;
q->rear=0;} return q;} //判断队空
int empty(PSeqQueue q){ if(q&&q->front==q->rear)
return 1;else return 0;} //入队
void input(PSeqQueue q,btree x){ if((q->rear+1)%maxsize==q->front)
printf("队满");else {
q->rear=(q->rear+1)%maxsize;
q->data[q->rear]=x;} } //出队
void output(PSeqQueue q,btree *x){
} if(empty(q))printf("队空");else { q->front=(q->front+1)%maxsize;*x=q->data[q->front];} //按照层次遍历二叉树 void LevelOrder1(btree t){ PSeqQueue q;btree p=t;q=init();input(q,p);while(!empty(q)){
output(q,&p);
printf("%c",p->data);
if(p->lchild)
input(q,p->lchild);
if(p->rchild)
input(q,p->rchild);} } void main(){ btree t;t=create();printf("此二叉树的先序递归遍历输出为：");PreOrder1(t);printf("n");
printf("此二叉树的先序非递归遍历输出为：");PreOrder2(t);printf("n");printf("此二叉树的中序递归遍历输出为：");InOrder1(t);printf("n");printf("此二叉树的中序递归遍历输出为：");InOrder2(t);printf("n");printf("此二叉树的后序递归遍历输出为：");PostOrder1(t);printf("n");
} printf("此二叉树的后序递归遍历输出为：");PostOrder2(t);printf("n");printf("此二叉树的层次遍历输出为：");LevelOrder1(t);printf("n");程序结果：
五：实验心得、体会：
熟练地掌握递归算法的核心内容，能够较为熟练地使用递归算法的思想，了解二叉树的各种遍历的特点，了解各种遍历算法的递归算法和非递归算法。
第5篇：二叉树遍历课程设计】
数据结构程序设计报告
学院： 班级： 学号：
姓名：
实验名称：二叉树的建立与遍历
一、实验目的：
1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法；
3.掌握二叉树的先序、中序、后序的递归实现方法。
二、实验内容和要求：
创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。
三、叉树的建立与遍历代码如下：
#include #include struct tnode//结点结构体 {
};typedef struct tnode TNODE;
TNODE *creat(void){ TNODE *root,*p;TNODE *queue[50];char data;struct tnode *lchild,*rchild;
int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch;printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)n");
ch=getchar();
while(ch!='!'){ if(ch!='#')
{ p=(TNODE *)malloc(sizeof(TNODE));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;rear++;
queue[rear]=p;//把非#的元素入队
if(rear==0)//如果是第一个元素，则作为根节点 {
} else {
if(counter%2==1)//奇数时与其双亲的左子树连接 {
}
if(counter%2==0)//偶数时与其双亲的右子树连接 {
queue[front]->rchild=p;queue[front]->lchild=p;root=p;counter++;
}
}
}
}
front++;
counter++;
else//为#时，计数，但不连接结点 {
if(counter%2==0)
front++;counter++;
}
ch=getchar();} return root;void preorder(TNODE *bt)//先序遍历 {
if(bt!=NULL){
printf("%c
",bt->data);preorder(bt->lchild);preorder(bt->rchild);
} } void inorder(TNODE *bt)//中序遍历 {
if(bt!=NULL){
inorder(bt->lchild);printf("%c
",bt->data);inorder(bt->rchild);
} }
void postorder(TNODE *bt)//后序遍历 {
if(bt!=NULL){
postorder(bt->lchild);postorder(bt->rchild);printf("%c
",bt->data);
} } int main(){
TNODE *root;
root=creat();printf("递归先序遍历是:");
preorder(root);
printf("n");printf("递归中序遍历是：");inorder(root);printf("n");
} printf("递归后序遍历是：");postorder(root);printf("n");return 0;
四、程序运行结果：
五、程序设计指导：
1.创建二叉树的算法：首先对一般的二叉树，添加若干个虚结点使其成为完全二叉树，然后依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点，若是第一个，则令其为根结点，否则将新结点链接至它的双亲结点上。如此重复下去，直至遇到输入结束符（自定）为止。为了使新结点能够与双亲结点正确相连，并考虑到这种方法中先建立的结点其孩子结点也一定先建立的特点，可以设置一个指针类型的数组构成的队列来保存已输入结点的地址，并使队尾(rear)指向当前输入的结点，队头(front)指向这个结点的双亲结点的前一个位置。由于根结点的地址放在队列的第一个单元里，所以当rear为奇数时，则rear所指的结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则无须链接。若一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。
2.void preorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先读取，再进行进入下一个递归循环中。
3.void inorder(TNODE *bt)函数 ：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先左子树，再读取结点元素，再进行进入下一个递归循环中。
4.void postorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先分别进入左右子树，再进行读取，再进行进入下一个递归循环中。
六、心得体会：
本次数据结构程序设计对我有一定的帮助。通过这次的实践，使我对数据结构这门课程有了更深入地了解。在写程序的过程中，我重复地读课本上的知识，并且渐渐领悟到数据结构编程的方法。在编程中，虽然遇到了一些困难，但我并不气馁。当程序运行出来时，我感到了快乐。总之，通过自己地探索和努力，思维得到了锻炼，编程能力也有了较大地改善。
第6篇：二叉树的遍历学习心得
二叉树的非递归遍历学习心得
对于学习数据结构的新手来说，二叉树应该是遇到的一个比较大的难题。对于二叉树的遍历，如果使用递归的方法，代码非常简单，但是有些程序语言不支持递归，而且递归的执行效率偏低，使许多程序设计人员望而却步下面我将与大家分享我在学习二叉树的非递归遍历的过程中遇到的困惑与解答，以供学习和交流。
鉴于有些数据结构资料中没有介绍树的结点的栈的结点的构造，首先向大家介绍结点的构造。
typedef struct BitNode { char data;
树的结点的数据域（以字符型数据为
树的结点的结构
例）
struct BitNode *lchild,*rchild;
树的子树指针
}BitNode,*BitTree;
typedef struct node { BitNode stack;
栈的数据域类型为树的 结点
栈的结点结构
struct node *next;}LinkStack;遍历的前提当然是二叉树存在，下面为大家介绍树的建立。BitTree Creat_BitTree(){
BitTree bt;
树的根结点 char x;scanf("%c",&x);
树的建立的子函数类型为树的指针类型
} if(x=='#')bt=NULL;else {
} return bt;
如果输入为’#’，则返回空结点
bt=(BitTree)malloc(sizeof(BitNode));若输入有效，则申请结点空间 bt->data=x;
装填结点 插入左子树 插入右子树 bt->lchild=Creat_BitTree();bt->rchild=Creat_BitTree();
建立二叉树的过程使用了递归，如果理解不了，可以自己画图助于理解，建立决定了二叉树的形状，一定要弄清楚。如所要建立的二叉树的形状为
那么输入应该为ABD##EG###。
接下来是栈的一些操作，因为任何一本数据结构的资料都会在栈和队列的章节说得很清楚，下面只是做了一些比较小的改动，请读者自行体会。int Init_Stack(LinkStack **s){
}
int Push_Stack(LinkStack *s,BitNode *x)
*s=(LinkStack*)malloc(sizeof(LinkStack));(*s)->next=NULL;return 1;{
}
int Pop_Stack(LinkStack *s,BitNode *e){
return 0;}
}
int Empty_Stack(LinkStack *s){
}
if(s->next==NULL)return 1;return 0;LinkStack *p;
if(Empty_Stack(s)){ printf("Stack is NULLn");p=s->next;s->next=p->next;*e=p->stack;free(p);return 1;LinkStack *p;
p=(LinkStack*)malloc(sizeof(LinkStack));p->stack=*x;p->next=s->next;s->next=p;return 1;先介绍先序遍历的算法，先建立根结点，再建立左子树再到右子树，遍历是相对于每一棵子树来说的，这一点要格外注意。最重要的是要在脑海里建立模型，在后面的后序遍历中尤显模型的重要性。void Pre_Order(BitTree T){
} 以下是主函数。int main(){
BitTree T;
printf("nt********************欢迎来到二叉LinkStack *s;BitTree p;p=T;
Init_Stack(&s);Push_Stack(s,p);while(!Empty_Stack(s)){
Pop_Stack(s,p);
printf("t[%c]",p->data);
if(p->rchild)Push_Stack(s,p->rchild);if(p->lchild)Push_Stack(s,p->lchild);} 树世界********************n");
printf("nt请输入二叉树结点，"#"为空树nt");T=Creat_BitTree();printf("n");
printf("t先序遍历二叉树如下：");printf("n");
}
Pre_Order(T);printf("nt");getch();以下是二叉树的中序遍历的算法，先从左子树入栈到底，然后访问栈顶元素，同时栈顶出栈，再检测是否存在右子树，如果存在，从它的右子树的左子树入栈到底，如果不存在，访问栈顶元素，同时栈顶出栈，如此循环，直到栈空。void In_Order(BitTree T){
}
LinkStack *s;BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));p=T;
Init_Stack(&s);
while(p ||!Empty_Stack(s)){ if(p){
} else {
} }
Pop_Stack(s,q);
printf("t[%c]",q->data);p=q->rchild;Push_Stack(s,p);p=p->lchild;二叉树的遍历中要数后序遍历最为复杂，它的栈的构造与前面两种遍历方法有所不同，在栈里加了一个标记元素rvisited用来标记其结点的右子树是否被访问过，由此来达到最后才访问根结点的效果。由于程序比较复杂，下面为大家一步步分析。
typedef struct node {
}LinkStack;int Push_Stack(LinkStack *s,BitNode *x){
} void Post_Order(BitTree T){
BitTree p,q;LinkStack *s,*top;Init_Stack(&s);p=T;
q=(BitTree)malloc(sizeof(BitNode));while(p)
从左子树插入到底 {
LinkStack *p;
p=(LinkStack *)malloc(sizeof(LinkStack));p->stack=*x;p->rvisited=0;p->next=s->next;s->next=p;return 1;
插入栈的时候先设为右子树未被访问
int rvisited;BitNode stack;struct node *next;
标记元素，记录右子树是否已被访问
}
Push_Stack(s,p);p=p->lchild;
while(!Empty_Stack(s)){
top=s->next;
取栈顶元素
if(!top->stack.rchild || top->rvisited)若栈顶元素的右子树不存在或者被访问过，访问栈顶元素同时出栈
} else
若栈顶元素的右子树存
{
Pop_Stack(s,q);
printf("t[%c]",q->data);在而且未被访问过，先将其rvisited值设为1再向右检测右子树
} 二叉树的几种遍历方法就介绍到这里，以上程序均在ＶＣ++6.0编译环境下运行通过，值得注意的是，三种遍历方法不能放在同一个程序中使用，因为树的遍历过程伴随着销毁，遍历一次以后下一次的遍历就变得毫无意义。由于本人水平有限,难免有纰漏差错之处,请谅解.} } } {
top->rvisited=1;p=top->stack.rchild;while(p){
Push_Stack(s,p);p=p->lchild;
从根结点的左子树插入栈到底 参考文献
(稻草人)[ 1 ] 徐孝凯.数据结构简明教程[M ].北京: 清华大学出版社, 1995: 71291.[ 2 ] 严蔚敏,吴伟民.数据结构[M ].北京: 清华大学出版社, 2000: 962106.[ 3 ] 耿国华.数据结构—C语言描述[M ].西安: 西安电子科技大学 出版社, 2006: 1012104.[ ４]崔进平,郭小春,王霞.数据结构(Ｃ语言版)[M ].北京:清华大学出版社,2011: 245868.(稻草人)
