二叉树地遍历算法
- 格式：doc
- 大小：62.62 KB
- 文档页数：8
实用文档
实验三 二叉树遍历算法
一、 实验目的
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)
{
