另一个人写的
BiTree.h
代码:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
typedef int Status;
typedef int TElemType;
/*
定义结构及基本操作
*/
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
typedef BiTree SElemType;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
Status InitStack(SqStack &S) {
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S, SElemType &e) {
if(S.top==S.base) return ERROR;
e=* (S.top-1);
return OK;
}
Status Push(SqStack &S,SElemType e) {
if(S.top-S.base>=S.stacksize) {
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e) {
if(!S.top) return ERROR;
e=*--S.top;
return OK;
}
bool StackEmpty(SqStack s) {
return s.base==s.top;
}
//创建二叉树
void CreateBiTree(BiTree &t) {
int ch=getchar();
if(ch==' ') t=NULL;
else {
if( !( t=(BiTNode*)malloc(sizeof(BiTNode))) ) exit(OVERFLOW);
t->data=ch;
CreateBiTree(t->lchild);
CreateBiTree(t->rchild);
}
}
//递归遍历二叉树
void PreOrderTraverse(BiTree t) {
if(t) {
/* 以先序方式遍历,若要以中序或后序遍历
只需改变以下三句顺序*/
printf("%c ",t->data);
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
}
//非递归遍历二叉树(中序)
void InOrderTraverse(BiTree t) {
SqStack s;
BiTree p;
InitStack(s);
Push(s,t);
while( !StackEmpty(s) ) {
while( GetTop(s,p)&&p ) { Push(s,p->lchild); }
Pop(s,p);
if( !StackEmpty(s) ) {
Pop(s,p);
printf("%c ",p->data);
Push(s,p->rchild);
}
}
}
//递归求二叉树叶子数
int Leaf(BiTree t) {
if(t==NULL) return 0;
if( t->lchild==NULL && t->rchild==NULL ) return 1;
else {
return Leaf(t->lchild)+Leaf(t->rchild);
}
}
//非递归求二叉树叶子数
static int counter=0;
int NumOfLeaf(BiTree t) {
SqStack s;
BiTree p;
InitStack(s);
Push(s,t);
while( !StackEmpty(s) ) {
while( GetTop(s,p)&&p ) { Push(s,p->lchild); }
Pop(s,p);
if( !StackEmpty(s) ) {
Pop(s,p);
if(p->lchild==NULL&&p->rchild==NULL) counter++;
Push(s,p->rchild);
}
}
return counter;
}
int max(int x,int y) {
return x>y?x:y;
}
//递归求二叉树的高
int HeightOfBiTree(BiTree t) {
if(t==NULL) return 0;
if( t->lchild==NULL && t->rchild ) return 1;
else {
return 1+max( HeightOfBiTree(t->lchild) , HeightOfBiTree(t->rchild) );
}
}
BiTree.cpp
代码:
#include "stdio.h"
#include "stdlib.h"
#include "BiTree.h"
/*
* http://shakesmin.javaeye.com/blog/43107
*/
/*
测试二叉树结构及相关算法
*/
int main() {
BiTree t;
printf("请按先序正确输入二叉树(空格为空树):\n");
CreateBiTree(t);
printf("先序历遍: ");
PreOrderTraverse(t);
printf("\n中序历遍: ");
InOrderTraverse(t);
printf("\n递归法求叶子数:%d\n",Leaf(t));
printf("非递归法求叶子数:%d\n",NumOfLeaf(t));
printf("二叉树高:%d\n",HeightOfBiTree(t));
return 0;
}