文档介绍：基于二叉树的二叉链表存储结构实现以下操作:
用先序遍历创建二叉树
对二叉树进行非递归遍历(先序、中序、后序)
求二叉树所有结点和叶子结点个数
求二叉树的深度
#include""
#include""
#include""
#include""
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//#define OVERFLOW
#define NULL 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
typedef BiTree SElemType;//tepedef BiNode SElemType;
//#define MAX_TREE_SIZE 100
//typedef TElemtype SqBiTree[MAX_TREE_SIZE ];
//SqBiTree bt;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
Status InitStack(SqStack &S)
{
=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!)exit(OVERFLOW);
=;
=STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S,SElemType &e)
{
if(==) return ERROR;
e=*(-1);
return OK;
}
Status Push(SqStack &S,SElemType e)
{
if(->=)
{
=(SElemType *)realloc(,(+STACKINCREMENT)*sizeof(SElemType));
if(!)exit(OVERFLOW);
=+;
+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
if(==)return ERROR;
e=*--;
return OK;
}
Status StackEmpty(SqStack S)
{
if(==)return TRUE;
else return FALSE;
}
Status 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;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}//CreateBiTree
Status PreoderTraverse(BiTree T)
{//二叉树先序遍历非递归算法
SqStack S;BiTree p;
InitStack(S); p=T;
while(p||!StackEmpty(S))
{
if(p)
{
printf("%c\t",p->data);p=p->lchild;
Push(S,p->rchild);
}
else Pop(S,p);