tree.cpp

属于数据结构的C++编程

#include<stdio.h>
#include<malloc.h>
#include<iostream.h>
#define NULL 0
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 5

typedef struct BiTNode
{
	char date;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

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

int InitStack(SqStack &S)
{
	S.base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
	if(!S.base) return(0);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 1;
}
int Push(SqStack &S,BiTree &p)
{
	/*if(S.top-S.base>=S.stacksize)
	{
		S.base=(BiTNode *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
		if(!S.base) return(0);
		S.top=S.base;
		S.stacksize+=STACKINCREMENT;
	}*/
	S.top->date=p->date;
	S.top++;
	return 1;
}
int Pop(SqStack &S,BiTree &p)
{
	if(S.top==S.base) 
		return 0;
	--S.top;
	p->date=S.top->date;
	return 1;
}
int StackEmpty(SqStack S)
{
	if(S.base==NULL) return 1;
	else return 0;
}
int CreatBiTree(BiTree &T)
{
	char ch;
	cin>>ch;
	if(ch==';') T=NULL;
	else
	{
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
			return 0;
		T->date=ch;
		CreatBiTree(T->lchild);
		CreatBiTree(T->rchild);
	}
	return 1;
}
int PrintElement(char e)
{
	cout<<e<<endl;
	return 1;
}
//先序遍历二叉树的递归算法
/*
int PreOrderTraverse(BiTree T,int (* visit)(char e))
{
	if(T)
	{
		if(visit(T->date))
			if(PreOrderTraverse(T->lchild,visit))
				if(PreOrderTraverse(T->rchild,visit))
					return 1;
		return 0;
	}
	else 
		return 1;
}
*/
//中序遍历二叉树的非递归算法
int InOrderTraverse(BiTree T)
{
	BiTree p,q;
	SqStack S;
	InitStack(S);
	p=T;
	while(p||!StackEmpty(S))
	{
		if(p) 
		{
			Push(S,p); 
			if(p->lchild==NULL)
				q=p;
			p=p->lchild;
		}
		else
		{
			Pop(S,p);
			cout<<p->date<<endl;
			p=p->rchild;
		}
	}
	return 1;
}

int main()
{
	BiTree T;
	CreatBiTree(T);
//	PreOrderTraverse(T,PrintElement);
	InOrderTraverse(T);
	return 1;
}