二叉树
definition.h
=========================================
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef char TElemType;
typedef struct{
TElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree;//二叉树的二叉链表存储表示
typedef struct{
BiTree *top, *base; //栈顶指针和栈底指针
unsigned stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
BiTree CreateBiTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树
void PreOrderTraverse(BiTree);//先序遍历二叉树
int InOrderTraverse(BiTree);//中序遍历二叉树，非递归
int InOrderTraverse2(BiTree);
int InitStack(SqStack *);//创建一个空栈
int Push(SqStack *, BiTree); //插入栈顶
===========================================================================
main.c
================================================
#include <stdio.h>
#include "definition.h"
int main()
{
BiTree bt;
printf("请输入根结点：");
bt = CreateBiTree();//按先序次序创建二叉树
PreOrderTraverse(bt); //先序遍历二叉树
printf("\n");
if( InOrderTraverse(bt) )//中序遍历二叉树，非递归
return 1;//遍历失败，返回
printf("\n");
if( InOrderTraverse2(bt) )//中序遍历二叉树，非递归
return 1;//遍历失败，返回
printf("\n");
return 0;
}
===================================================================
function.c
======================================================
#include <stdio.h>
#include <malloc.h>
#include "definition.h"
BiTree CreateBiTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树
{
TElemType e;
BiTree tmp = NULL;
if( (e=getchar())!='#' ){
getchar();//接收回车符
tmp=(BiTree)malloc(sizeof(BiTNode));
if(!tmp)
return NULL;
tmp->data=e;
printf("请输入左孩子：");
tmp->lchild=CreateBiTree();
printf("请输入右孩子：");
tmp->rchild=CreateBiTree();
}
else
getchar();//接收回车符
return tmp;
}
void PreOrderTraverse(BiTree bt)//先序遍历二叉树
{
if(bt){
printf("%c", bt->data);
PreOrderTraverse(bt->lchild);
//printf("%c", bt->data);不要上面的printf，而用这个printf，则为中序遍历
PreOrderTraverse(bt->rchild);
//printf("%c", bt->data);不要上面的printf，而用这个printf，则为后序遍历
}
}
int InOrderTraverse(BiTree bt)//中序遍历二叉树，非递归
{
SqStack S;
BiTree tmp;
if( InitStack(&S) )
return 1;//如果创建空栈失败，返回1
if( Push(&S, bt) )//根指针进栈
return 1;//如果压栈失败，返回1
while(S.base!=S.top){
while( tmp=*(S.top-1) ){
if( Push(&S, tmp->lchild) )//向左走到尽头
return 1;
//printf("%c", tmp->data);//printf放于此处即为先序遍历
}
--S.top;//空指针退栈
//访问结点，向右一步
if(S.base!=S.top){
tmp = *(--S.top);
printf("%c", tmp->data);
if( Push(&S, tmp->rchild) )
return 1;
}
}
free(S.base);
return 0;
}
int InOrderTraverse2(BiTree bt)
{
SqStack S;
BiTree tmp = bt;
if( InitStack(&S) )
return 1;//如果创建空栈失败，返回1
while( tmp||(S.base!=S.top) ){
if(tmp){
if( Push(&S, tmp) )//根指针进栈，遍历左子树
return 1;
//printf("%c", tmp->data);//printf放于此处即为先序遍历
tmp = tmp->lchild;
}
//根指针退栈，访问根结点，遍历右子树
else{
tmp = *(--S.top);
printf("%c", tmp->data);
tmp = tmp->rchild;
}
}
free(S.base);
return 0;
}
int InitStack(SqStack *S) //创建一个空栈
{
S->base=(BiTree *)malloc( INIT_SIZE * sizeof(BiTree) );
if(!S->base) //空间分配失败
return 1;
//空间分配成功
S->top=S->base;//置栈顶指针
S->stacksize=INIT_SIZE;//栈大小
return 0;
}
int Push(SqStack *S, BiTree T) //插入栈顶
{
if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间
S->base=(BiTree *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof(BiTree) );
if(!S->base)//分配失败，返回1
return 1;
//分配成功
S->top = S->base + S->stacksize;//置栈顶指针
S->stacksize += INCREMENT;//栈大小
}
*S->top++ = T;//接收输入后，S->top指向栈顶元素的下一个位置
return 0;
}
