二叉树.cpp

自己写的数据结构代码

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;

#define maxsize 100000
#define STACK_INIT_SIZE 100000
#define STACKINCREMENT 2

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

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

Status InitStack(SqStack &S)
{
	S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}

Status Push(SqStack &S,BiTree e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));
		S.top=S.base+S.stacksize;
		S.stacksize=S.stacksize+STACKINCREMENT;
	}
	*S.top++=e;
	
	return OK;
}

Status Pop(SqStack &S,BiTree &e)
{
	if(S.top==S.base) return ERROR;
	
	e=* --S.top;
	return OK;
}


Status StackEmpty(SqStack S)
{
	if(S.top==S.base) return OK;
	return ERROR;
}



Status InsertBiTree(BiTree &T,int e)
{
	if(!T) 
	{
		T=(BiTNode *)malloc(sizeof(BiTNode));
		T->data=e;
		T->lchild=NULL;
		T->rchild=NULL;
		return OK;
	}
	if(e<=T->data)
	{
		InsertBiTree(T->lchild,e);
		return OK;
	}
	else
	{
		InsertBiTree(T->rchild,e);
		return OK;
	}
	return OK;
}

Status PrintElement(ElemType e)
{
	printf("%d ",e);
	return OK;
}

Status PreOrderTraverse(BiTree T,Status(*Visit)(ElemType))
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild,Visit)) 
				if(PreOrderTraverse(T->rchild,Visit))   return OK;
				return ERROR;
	}
	else return OK;
}

Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType))
{
	if(T)
	{
		if(InOrderTraverse(T->lchild,Visit))
			if(Visit(T->data)) 
				if(InOrderTraverse(T->rchild,Visit))   return OK;
				return ERROR;
	}
	else return OK;
}

Status PostOrderTraverse(BiTree T,Status(*Visit)(ElemType))
{
	if(T)
	{
		if(PostOrderTraverse(T->lchild,Visit))
			if(PostOrderTraverse(T->rchild,Visit)) 
				if(Visit(T->data))   return OK;
				return ERROR;
	}
	else return OK;
}

Status SearchBiTree(BiTree &T,int e)
{
	if(!T) return ERROR;
	else if(e==T->data) return OK;
	else if(e<T->data)
	{
		return SearchBiTree(T->lchild,e);
	}
	else
	{
		return SearchBiTree(T->rchild,e);
	}
}


Status InOrder(BiTree T,Status(*Visit)(ElemType))
{
	SqStack s;
	BiTree p;
	InitStack(s);
	p=T;
	while(p || !StackEmpty(s))
	{
		if(p)  
		{
			Push(s,p);
			p=p->lchild;
		}
		else
		{
			Pop(s,p);
			if(!Visit(p->data))  return ERROR;
			p=p->rchild;
		}
	}
	return OK;
}
	
void Travel(BiTree T)                         /*层次遍历二叉树*/
{
    BiTree qu[maxsize];
    int front,rear;
    front=rear=0;
    if(T!=NULL)
        printf("%d ",T->data);
    rear++;
    qu[rear]=T;
    while(rear!=front)
    {   front=(front+1)%maxsize;
        T=qu[front];
        if(T->lchild!=NULL)
        {   printf("%d ",T->lchild->data);
            rear=(rear+1)%maxsize;
            qu[rear]=T->lchild;
        }
        if(T->rchild!=NULL)
        {   printf("%d ",T->rchild->data);
            rear=(rear+1)%maxsize;
            qu[rear]=T->rchild;
        }
    }
}  

	
int main()
{
	int a[100000];
	int n,i;
	int e;
	BiTree T;
	
	scanf("%d",&n);
	for(i=0;i<=n-1;i++)
	{
		scanf("%d",&a[i]);
	}
	T=NULL;
	for(i=0;i<=n-1;i++)
	{
		InsertBiTree(T,a[i]);
	}
	
	PreOrderTraverse(T,PrintElement);
	printf("\n");
	InOrderTraverse(T,PrintElement);
	printf("\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n");
	
	for(i=1;i<=2;i++)
	{
		scanf("%d",&e);
		printf("%d\n",SearchBiTree(T,e));
	}

	scanf("%d",&e);
	InsertBiTree(T,e);
	
	PreOrderTraverse(T,PrintElement);
	printf("\n");
	InOrderTraverse(T,PrintElement);
	printf("\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n");

	InOrder(T,PrintElement);
	printf("\n");

	Travel(T);
	printf("\n");
	return 0;
}