二叉树.cpp

数据结构课程中

#include<iostream>
using namespace std;

#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INT_SIZE 100
#define STACKINCREMENT 10

typedef struct BiTNode
{int data;
struct BiTNode * lchild,* rchild;
}BiTNode,* BiTree;

typedef struct
{
	BiTree *base;
	BiTree *top;
	int stacksize;
}SqStack;


int InitStack(SqStack &S)
{
	S.base=(BiTree *)malloc(STACK_INT_SIZE*sizeof(BiTNode));
	if(!S.base)   return OVERFLOW; 
	S.top=S.base;
	S.stacksize=STACK_INT_SIZE;
	return OK;
}
int Push(SqStack &S, BiTree e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
		if(!S.base)    return   OVERFLOW;
		S.top=S.base+S.stacksize;
		S.stacksize+=STACK_INT_SIZE;
	}
	*S.top++=e;
	return OK;
}
int Pop(SqStack &S,BiTree &e)
{
	if(S.top==S.base)   return ERROR;
	e=*--S.top;
	return OK;
}
int StackEmpty(SqStack S)
{
	if(S.top!=S.base)   return false;
	else return true;
}
int CreateBiTree(BiTree &T)
{int ch;
scanf("%d",&ch);
if(ch==0)T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);

}
return OK;
}

char InOrderT(BiTree &T)
{ BiTree p;SqStack S;
	InitStack(S); p=T;
	while(p||!StackEmpty(S))
	{if(p){Push(S,p);p=p->lchild;}
	else{Pop(S,p);
	printf("%d ",p->data);
         p=p->rchild;
	}
	}
	return OK;


}
void main()
{BiTree T; 
 CreateBiTree(T);
InOrderT(T);
}
/*输入说明：按二叉树的结构输入
 例如输入：1 2 0 0 3 0 0
 */