二叉树中序遍历的非递归算法实现
试验五
课程名称 实验室名称 实验名称 二叉树中序遍历的非递归算法实现 指导教师 成绩 1、 实验目的
二叉树中序遍历的非递归算法实现
2、 实验原理和内容
二叉树中序遍历的非递归算法实现
3、 实验步骤
1.链式存储结构的定义和栈结构的定义
2.编写进栈函数push和出栈函数pop实现中序遍历过程中需存储的数的进栈和出栈过程
3.创建一棵二叉树
4.对该二叉树进行中序遍历,采用非递归算法实现
4、 程序及运行结果(或实验数据记录及分析)
#include
#include
typedef char datatype; //* 链式存储结构*//
typedef struct node{
datatype data;
struct node *lchild,*rchild; }bintnode;
typedef bintnode *bintree;
typedef struct stack{ /* 栈结构定义*/
bintree data[100];
int top;
}seqstack;
void push(seqstack *s,bintree t) {
s->data[s->top]=t; s->top++; }
bintree pop(seqstack *s) {
if (s->top!=0)
{
s->top--;
return(s->data[s->top]);
}
else
return NULL;
}
void createbintree(bintree *t) {
char ch;
if ((ch=getchar())==' ')
*t=NULL;
else
{
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
void inorder1(bintree t)
{
seqstack s;
s.top=0;
while((t!=NULL) || (s.top!=0))
{
while (t)
{
push(&s,t);
t=t->lchild;
}
if (s.top!=0)
{
t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
main()
{
bintree root;
printf("input the tree as preorder:");
createbintree(&root);
printf("\n中序遍历结果是: ");
inorder1(root);
}
在屏幕上输出的结果:
本文档为【二叉树中序遍历的非递归算法实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。