中序遍历和层次遍历相同的二叉树的特征
- 提问者网友：我的未来我做主
- 2021-02-04 11:56
- 五星知识达人网友：duile
- 2021-02-04 13:19
- 1楼网友：罪歌
- 2021-02-04 13:54
#include<stdlib.h>
#include<stdio.h>
#define stack_init_size 100//栈初始分配的空间数
#define stackincreament 10//栈空间不够时增加的空间数
typedef char eletype;//二叉树结点信息类型
typedef struct bitnode//二叉树结点类型
{
struct bitnode *lchild,*rchild;
eletype data;
}bitnode;
typedef bitnode *elemtype;//elemtype声明为指针类型
typedef struct stack//栈的存储类型，采用动态分配
{
elemtype *base;
elemtype *top;
int stacksize;
}sqstack;
sqstack *initstack()//创建栈
{
sqstack *s;
if (!(s = (sqstack *)malloc(sizeof(sqstack))))exit(-1);
s->base = (elemtype *)malloc(stack_init_size*sizeof(elemtype));//初始化为栈分配stack_init_size个elemtype类型的空间
if (!s->base)//分配空间失败
{
exit(-2);
printf("栈空间分配失败!\n");
}
if (s->base)//分配空间成功
printf("栈空间分配成功!\n");
s->top = s->base;//初始化栈的头尾指针
s->stacksize = stack_init_size;
return s;
}
void push(sqstack *s,elemtype e)//压栈，e要是一个地址
{
if (s->top-s->base>=s->stacksize)//栈满
{
s->base = (elemtype *)realloc(s->base,(s->stacksize+stackincreament)*sizeof(elemtype));//栈满时增加空间
if (!s->base)//增加分配空间失败
exit(-2);
s->stacksize += stackincreament;
}
*(s->top) = e;
s->top++;
}
elemtype pop1(sqstack *s)//出栈1，返回的e为栈顶元素是一个地址
{
elemtype e;
if (s->top == s->base)return 0;//栈空时返回
s->top--;
e = *(s->top);
return e;
}
int stackempty(sqstack *s)//判断栈空，栈空返回1，否则返回0
{
if (s->base == s->top)return 1;
else return 0;
}
bitnode *createbitree()//先序递归法建树
{
char x;
bitnode *t;
scanf("%c",&x);
if (x == ' ')t = null;
else
{
if (!(t = (bitnode *)malloc(sizeof(bitnode))))exit(-1);
t->data = x;//建立节点
t->lchild = createbitree();//建左子树
t->rchild = createbitree();//建右子树
}
return t;
}
int inorder(bitnode *t)//中序遍历二叉树非递归算法
{
sqstack *s;
bitnode *p;
s = initstack();//初始化栈
p = t;
printf("中序遍历二叉树，字符序列为:\n");
while (p||!stackempty(s))
{
while (p)//找最左结点
{
push(s,p);
p = p->lchild;//p指针顺lchild而下
}
p = pop1(s);//栈顶元素出栈以访问最左结点
printf("%c",p->data);//访问最左结点
p = p->rchild;
}
printf("\n");
return 1;
}
void main()
{
bitnode *t;
printf("请输入建树字符序列,以空格表示null:\n");
t = createbitree();
inorder(t);
}