二叉树的遍历算法_遍历二叉树算法
二叉树的遍历算法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“遍历二叉树算法”。
实验三 二叉树遍历算法
一、实验目的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”);程序结果：
五：实验心得、体会：
熟练地掌握递归算法的核心内容，能够较为熟练地使用递归算法的思想，了解二叉树的各种遍历的特点，了解各种遍历算法的递归算法和非递归算法。
