二叉树递归非递归遍历
西 安 邮 电 大 学
,计算机学院,
课内
实验报告
化学实验报告单总流体力学实验报告观察种子结构实验报告观察种子结构实验报告单观察种子的结构实验报告单
实验名称: 二叉树遍历
专业名称: 通信
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
班 级: 通工1309
学生姓名: 张睿
学号(8位): 03131304
指导教师: 季树滨
实验日期: 2014年 11月17 日
一. 实验目的及实验环境
1， 实验目的:
二叉树的遍历。
2， 实验环境:VC++
二. 实验内容
从键盘接受输入先序序列，一二叉链表作为存储结构，建立二叉树(以先序来建立)，并对其进行遍历，然后将遍历结果打印输出。
三(
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
设计
typedef struct BiTNode
{ // 二叉树结点结构
char data; // 结点数据
struct BiTNode *lchild; // 左孩子
struct BiTNode *rchild; // 右孩子
}BiTNode,*BiTree;
typedef BiTree SElemType;
typedef struct
{//栈结构定义
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S); //构造一个空栈S
Status DestroyStack(SqStack *S); //销毁栈S，S不再存在
Status ClearStack(SqStack *S); //把栈S置为空栈
Status StackEmpty(SqStack S); //若栈S为空栈，则返回TRUE，否则返回FALSE
int StackLength(SqStack S); //返回S元素的个数，即栈的长度
Status GetTop(SqStack S,SElemType *e); //若栈不为空，则用e返回S的栈顶元素，并返回OK;否则返回FALSE Status Push(SqStack *S,SElemType e); //插入元素e为新的栈顶元素
Status Pop(SqStack *S,SElemType *e); //若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR Status StackTraverse(const SqStack *S); //从栈底到栈顶依次对每个元素进行访问
BiTree CreateBiTree(BiTree T); // 按先后次序输入二叉树中结点的值(一个字符)，空格表示空树 // 构造二叉链表表示的二叉树T
Status PreOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构，Visit是对数据元素操作的应用
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
Status InOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
Status PostOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
Status PreOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
Status InOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
Status PostOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 后序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
Status Visit(ElemType e);
// 对二叉树中的数据元素访问
四(测试数据及运行结果
1(正常测试数据(3组)及运行结果;
2(非正常测试数据(2组)及运行结果。
五(总结
1(实验过程中遇到的问题及解决办法;
起初代码总是出错，不过仔细检查之后，便找到了错误所在，更加加深了对
程序算法的理解。
2(对设计及调试过程的
心得
信息技术培训心得 下载关于七一讲话心得体会关于国企改革心得体会关于使用希沃白板的心得体会国培计划培训心得体会
体会。
更加深刻体会了编程的乐趣，对于c语言也有了更多的了解。 六(附录:(电子版)
#include
#include
#include
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
typedef int Status;
typedef char ElemType; // 二叉树结点元素类型 typedef struct BiTNode
{ // 二叉树结点结构
char data; // 结点数据
struct BiTNode *lchild; // 左孩子
struct BiTNode *rchild; // 右孩子
}BiTNode,*BiTree;
typedef BiTree SElemType;
typedef struct
{//栈结构定义
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S); //构造一个空栈S
Status DestroyStack(SqStack *S); //销毁栈S，S不再存在
Status ClearStack(SqStack *S); //把栈S置为空栈
Status StackEmpty(SqStack S); //若栈S为空栈，则返回TRUE，否则返回FALSE
int StackLength(SqStack S);
//返回S元素的个数，即栈的长度
Status GetTop(SqStack S,SElemType *e); //若栈不为空，则用e返回S的栈顶元素，并返回OK;否则返回FALSE Status Push(SqStack *S,SElemType e); //插入元素e为新的栈顶元素
Status Pop(SqStack *S,SElemType *e); //若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR Status StackTraverse(const SqStack *S); //从栈底到栈顶依次对每个元素进行访问
BiTree CreateBiTree(BiTree T); // 按先后次序输入二叉树中结点的值(一个字符)，空格表示空树
// 构造二叉链表表示的二叉树T
Status PreOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e));
// 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit Status InOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e));
// 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit Status PostOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e));
// 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit Status PreOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e));
// 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit Status InOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e));
// 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit Status PostOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e));
// 采用二叉链表存储结结构，Visit是对数据元素操作的应用函数
// 后序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit Status Visit(ElemType e);
// 对二叉树中的数据元素访问
int main()
{
BiTree T=NULL;
Status(*visit)(ElemType e)=Visit;
printf("请按先序遍历输入二叉树元素(每个结点一个字符，空结点为' '):\n");
T=CreateBiTree(T);
printf("\n递归先序遍历:\n");
PreOrderRecursionTraverse(T,visit);
printf("\n递归中序遍历:\n");
InOrderRecursionTraverse(T,visit);
printf("\n递归后序遍历:\n");
PostOrderRecursionTraverse(T,visit);
printf("\n非递归先序遍历:\n");
PreOrderNonRecursionTraverse(T,visit);
printf("\n非递归中序遍历:\n");
InOrderNonRecursionTraverse(T,visit);
printf("\n非递归后序遍历:\n");
PostOrderNonRecursionTraverse(T,visit);
printf("\nEnd of main.\n");
return 0;
}
BiTree CreateBiTree(BiTree T)
{
// 按先后次序输入二叉树中结点的值(一个字符)，空格表示空树
// 构造二叉链表表示的二叉树T
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch; // 生成根节点
T->lchild=CreateBiTree(T->lchild); // 构造左子树
T->rchild=CreateBiTree(T->rchild); // 构造右子树
}
return T;
}
Status PreOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e))
{ // 先序遍历递归算法
if(T)
{
if(!Visit(T->data)) return ERROR;
PreOrderRecursionTraverse(T->lchild,Visit);
PreOrderRecursionTraverse(T->rchild,Visit);
}
return OK;
}
Status InOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e))
{ // 中序遍历递归算法
if(T)
{
InOrderRecursionTraverse(T->lchild,Visit);
if(!Visit(T->data)) return ERROR;;
InOrderRecursionTraverse(T->rchild,Visit);
}
return OK;
}
Status PostOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e))
{ //后序遍历递归算法
if(T)
{
PostOrderRecursionTraverse(T->lchild,Visit);
PostOrderRecursionTraverse(T->rchild,Visit);
if(!Visit(T->data)) return ERROR;;
}
return OK;
}
Status PreOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e))
{
// 先序遍历二叉树T的非递归算法
SqStack S;
SElemType p;
InitStack(&S); Push(&S,T); // 根指针入栈
while(!StackEmpty(S))
{
Pop(&S,&p); //访问根节点
if(!Visit(p->data)) return ERROR;
if (p->rchild)
Push(&S,p->rchild);
if(p->lchild)
Push(&S,p->lchild);
}//while
DestroyStack(&S);
return OK;
}
Status InOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e))
{
// 中序遍历二叉树T的非递归算法
SqStack S;
SElemType p;
InitStack(&S); p=T;
while (p||!StackEmpty(S))
{
if (p)
{
Push(&S,p);p=p->lchild; //根指针进栈，遍历左子树
}
else
{//根指针退栈，访问根节点，遍历右子树
Pop(&S,&p); if(!Visit(p->data)) return ERROR;
p=p->rchild;
}//else
}//while
DestroyStack(&S);
return OK;
}
Status PostOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e))
{
// 后序遍历二叉树T的非递归算法
SqStack S;
SElemType p,q;
InitStack(&S); Push(&S,T); // 根指针入栈
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p) Push(&S,p->lchild); //向左走到尽头
Pop(&S,&p); //空指针出栈
GetTop(S,&p);
if(p->rchild)
{
Push(&S,p->rchild);
continue;
}
if(!StackEmpty(S))
{//访问结点，向右一步
Pop(&S,&p);
if(!Visit(p->data)) return ERROR;
while (GetTop(S,&q)&&q&&p==q->rchild)
{//若当前为右子树，则继续出栈
Pop(&S,&p);
if(!Visit(p->data)) return ERROR;
}
GetTop(S,&p);
if(p->rchild)
{
Push(&S,p->rchild);
continue;
}
else
{
Pop(&S,&p);
if(!Visit(p->data)) return ERROR;
}
}//if
}//while
DestroyStack(&S);
return OK;
}
Status Visit(ElemType e) {
// 对二叉树中的数据元素访问
if(e=='\0')
{
return ERROR;
}
else
{
printf("%c",e);
}
return OK;
}
//-----------顺序栈操作--------------//
Status InitStack(SqStack *S) {
//构造一个空栈S
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)//分配失败
{
printf("分配内存失败.\n");
exit(0);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S) {
//销毁栈S，S不再存在
if(!S)//S为空
{
printf("指针为空，释放失败.\n");
exit(0);
}
free(S->base);
return OK;
}
Status ClearStack(SqStack *S) {
//把栈S置为空栈
if(!S)//S不存在
return FALSE;
S->top=S->base;//直接将栈顶指针指向栈底
return OK;
}
Status StackEmpty(SqStack S) {
//若栈S为空栈，则返回TRUE，否则返回FALSE
if(S.top==S.base)
return TRUE;
else
return FALSE; }
int StackLength(SqStack S) {
//返回S元素的个数，即栈的长度
return S.stacksize; }
Status GetTop(SqStack S,SElemType *e)
{
//若栈不为空，则用e返回S的栈顶元素，并返回OK;否则返回FALSE
if(S.top==S.base)
{
return FALSE;
}
else
{
*e=*(S.top-1);
return OK;
}
}
Status Push(SqStack *S,SElemType e)
{
//插入元素e为新的栈顶元素
if(S->top-S->base>=S->stacksize)
{//栈已满，追加存储空间
S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S->base)
{
printf("重新申请空间失败.\n");
exit(0);
}
S->top=S->base+S->stacksize;//更改栈顶指针
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e) {
//若栈S不为空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR
if(S->top==S->base)
{//栈为空
return ERROR;
}
*e=*(--S->top);
return OK;
}
浙公网安备 33021202002483