#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data
struct bitree *lchild,*rchild
}bitree //二叉树结点定义
typedef struct {
bitree **base
bitree **top
int stacksize
}sqstack // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree))//栈底指向开辟空间
if(!s->base) exit(1) //抛出异常
s->top=s->base //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE //栈长度为开辟空间大小
return 1
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree))
if(!s->base) exit(1)//抛出异常
s->top=s->base+s->stacksize//感觉这一句没用
s->stacksize+=STACKINCREMENT}
*(s->top)=es->top++ //进栈 栈顶后移
return 1
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0 //栈空 返回0
--s->top*e=*(s->top) //栈顶前移 取出栈顶元素给e
return 1}
//取栈顶
int gettop(sqstack *s,bitree **e)//去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0 //所以 s->top-1
*e=*(s->top-1)
return 1
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char chbitree *ht,*p,*q
sqstack *s
s=malloc(sizeof(bitree)) //加上这一句为s 初始化开辟空间
ch=getchar()
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示*/
{ht=(bitree *)malloc(sizeof(bitree))
ht->data=ch
ht->lchild=ht->rchild=NULL
p=ht
initstack(s)
push(s,ht) //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)) // 法
q->data=ch //
if(p==*(s->top-1)) p->lchild=q // 核
else p->rchild=q //
push(s,q)p=q // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL // 的
else p->rchild=NULL //
pop(s,&p)} // 步
//
} // 骤
return ht
}
else return NULL
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch
scanf("%c",&ch)
if(ch=='#') *T=NULL
else{
*T=(bitree * )malloc(sizeof(bitree))
if(!*T) exit(1)
(*T)->data=ch //生成根结点
CreateBiTree(&(*T)->lchild)//构造左子树
CreateBiTree(&(*T)->rchild)//构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m
initstack(&m)
while(h||m.base!=m.top)
{if(h) {push(&m,h)printf("%c",h->data)h=h->lchild}
else{pop(&m,&h)
h=h->rchild}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m
initstack(&m)
while(h||m.base!=m.top)
{if(h) {push(&m,h)h=h->lchild}
else {
pop(&m,&h)
printf("%c",h->data)
h=h->rchild
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m
initstack(&m)
while(h||m.base!=m.top)
{if(h) {
push(&m,h)
h=h->lchild}
else {
bitree *r//使用r结点表示访问了右子树 代替标志域
gettop(&m,&h)
if(h->rchild&&h->rchild!=r)
{h=h->rchild
push(&m,h)
h=h->lchild}
else{pop(&m,&h)
printf("%c",h->data)
r=hh=NULL}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht
printf("先序非递归建立一个二叉树:")
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht)
//if(ht!=NULL)//递归建立
{
printf("先序遍历输出二叉树:")
preordertraverse(ht)
putchar('\n')
printf("中序遍历输出二叉树:")
inordertraverse(ht)
putchar('\n')
printf("后序遍历输出二叉树:")
postordertraverse(ht)
putchar('\n')
}
else printf("空二叉树\n")
}
#include "stdio.h"#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data
struct node *lchild
struct node *rchild
}
//先序，中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head
int ordsit
head=null
if(n<=0)
{
return null
}
else
{
head=(struct node *)malloc(sizeof(struct node))
head->data=*pre
head->lchild=head->rchild=null
ordsit=0
while(ord[ordsit]!=*pre)
{
ordsit++
}
head->lchild=create(pre+1,ord,ordsit)
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1)
return head
}
}
//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return
else
{
inorder(head->lchild )
printf("%c",head->data )
inorder(head->rchild )
}
}
//中序非递归遍历
void inorder1(struct node *head)
{
struct node *p
struct node *stack[20]
int top=0
p=head
while(p||top!=0)
{
while (p)
{
stack[top++]=p
p=p->lchild
}
p=stack[--top]
printf("%c ",p->data )
p=p->rchild
}
}
//主函数
int main()
{
struct node * head
char pre[30],ord[30]
int n
gets(pre)
gets(ord)
n=strlen(pre)
head=create(pre,ord,n)
inorder(head)
printf("\n")
inorder1(head)
printf("\n")
}
//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写，原版
vc++ 6.0实验通过
怎么样，老板，第一次上百度知道，好激动
给点面子
给分！给分啊
