stackfortree.cpp

数据结构中的二叉树的遍历（前序、中序、后序）算法

#include "stdafx.h"

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include "..\\header\\Bitree.h"

Status InitStack(SqStack &S)
{
	S.base = (BiTNode*)malloc(sizeof(BiTNode) * STACK_INIT_SIZE);
	if(!S.base) exit(OVERFLOW);

	S.top = S.base;
	//memset(S.base, 0, (sizeof(BiTNode) * STACK_INIT_SIZE));
	S.stacksize = STACK_INIT_SIZE;
	return OK;
} //InitStack

Status DestroyStack(SqStack &S)
{
	if(!S.base) return ERROR;

	free(S.base);
	S.base = NULL;
	S.top = NULL;

	S.stacksize = 0;

	return OK;
}

Status ClearStack(SqStack &S)
{
	if(!S.base) return ERROR;           //栈不存在，返回

	if(S.top == S.base) return ERROR;   //栈为空，返回

	S.top = S.base;

	return OK;
}

Status IsStackEmpty(SqStack S)
{
	if(!S.base) return ERROR;           //栈不存在，返回

	if(S.top == S.base)
	    return true;
	else
	    return false;
}//IsStackEmpty

int StackLength(SqStack S)
{
	if(!S.base) return ERROR;           //栈不存在，返回

	return S.top - S.base;
}//StackLength

Status Push(SqStack &S,BiTNode* e)
{
	if(S.top - S.base >= S.stacksize)       //栈满，追加存储空间
	{
		S.base = (BiTNode*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof \
				(BiTNode));

		if(!S.base) exit(OVERFLOW);

		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}

	if(e != NULL)
	{
		(*S.top) = (*e);			//e的值(*e)入栈
		S.top++;
	}

	return OK;
} //Push

/*
*       说明：该函数通过参数e将栈顶元素返回
*			但此时的e传递进来时，必须已经赋值
*/
Status Pop(SqStack &S, BiTNode* e)
{
	if(S.base == S.top || !e)
	{
		return ERROR;
	}

	--S.top;
	(*e) = (*S.top);				//弹出的值赋予给*e
	//e = S.top;					//error.

	return OK;
}

/*
*       说明：该函数通过函数返回值将栈顶元素返回
*			
*/
BiTNode* Pop(SqStack &S)
{
	if(S.base == S.top)
	{
		return NULL;
	}

	--S.top;

	return S.top;
}

Status GetTop(SqStack& S, BiTNode* e)
{
	if(!S.base) return ERROR;           //栈不存在，返回

	if(S.base == S.top)
	{
		return ERROR;
	}

	(*e) = *(S.top - 1);
	//e = S.top - 1;

	return OK;
} //GetTOp

BiTNode* GetTop(SqStack& S)
{
	if(!S.base) return ERROR;           //栈不存在，返回

	if(S.base == S.top)
	{
		return ERROR;
	}

	return (S.top - 1);
} //GetTOp