s)
{
if (s != NULL)
{
free(s->base);
s->top = NULL;
s->base = NULL;
s->stackSize = 0;
}
}
//
// 入栈
void Push(Stack *s, StackElemType e)
{
StackElemType *tmp;
if (s->top - s->base >= s->stackSize) // 栈已经满
{
tmp = (StackElemType *)realloc(s->base, (STACK_SIZE_INCREMENT + s->stackSize)
* sizeof(StackElemType));
if (!tmp)
{
exit(OVERFLOW); // 重新分配失败则退出
}
s->base = tmp;
s->top = s->base + s->stackSize;
s->stackSize += STACK_SIZE_INCREMENT;
}
*(s->top) = e;
s->top++;
}
//
// 出栈
void Pop(Stack *s, StackElemType *e)
{
if (s->top == s->base) // 如果栈为空栈
{
return;
}
*e = *(--s->top);
}
//
// 判断栈是否为空
// 返回非0表示空
int IsStackEmpty(Stack s)
{
return !(s.top - s.base);
}
//
// 取栈顶元素
int GetTop(Stack s, StackElemType *e)
{
if (!IsStackEmpty(s))
{
*e = *(s.top - 1); // 此处出错，原因？
return OK;
}
else
{
return ERROR;
}
}
[cpp]
二叉树头文件：
#include
//
// 二叉树的头文件：BinaryTree.h
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//
// 结点的数据的类型
typedef char ElemType;
//
// 二叉树结构体
typedef struct tagBinaryTree
{
ElemType data; // 数据
struct tagBinaryTree *lchild; // 指向左孩子
struct tagBinaryTree *rchild; // 指向右孩子
}BTree;
#endif
二叉树头文件：
#include
//
// 二叉树的头文件：BinaryTree.h
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//
// 结点的数据的类型
typedef char ElemType;
//
// 二叉树结构体
typedef struct tagBinaryTree
{
ElemType data; // 数据
struct tagBinaryTree *lchild; // 指向左孩子
struct tagBinaryTree *rchild; // 指向右孩子
}BTree;
#endif
[cpp]
二叉树实现文件及测试：
#include
#include
#include "BinaryTree.h"
#include "Queue.h"
#include "Stack.h"
/*****************************************************************************
* 方法名：CreateBinaryTree
* 描述： 递归创建一棵二叉树,按先序输入二叉树中结点的元素的值，“#”号表示空树
* 参数： pBTree--指向BTree结构体的指针的指针
* 返回值：返回OK--表示创建成功
* 返回ERROR--表示创建失败
******************************************************************************/
int CreateBinaryTree(BTree **pBTree)
{
ElemType data;
scanf("%c", &data);
if (data == '#')
{
*pBTree = NULL;
return OK;
}
else
{
if (((*pBTree) = (BTree *)malloc(sizeof(BTree))) == NULL)
{
exit(OVERFLOW);
}
(*pBTree)->data = data;
CreateBinaryTree(&(*pBTree)->lchild); // 创建左子树
CreateBinaryTree(&(*pBTree)->rchild); // 创建右子树
}
return OK;
}
/*****************************************************************************
* 方法名：PreOrderTraverse
* 描述： 先序遍历二叉树
* 参数： pBTree--指向BTree结构体的指针
******************************************************************************/
void PreOrderTraverse(BTree *pBTree)
{
if (pBTree)
{
printf("%c", pBTree->data); // 先序访问根结点
PreOrderTraverse(pBTree->lchild); // 先序遍历左子树
PreOrderTraverse(pBTree->rchild); // 先序遍历右子树
}
}
/*****************************************************************************
* 方法名：InOrderTraverse
* 描述： 中序遍历二叉树
* 参数： pBTree--指向BTree结构体的指针
******************************************************************************/
void InOrderTraverse(BTree *pBTree)
{
if (pBTree)
{
InOrderT