栈及二叉树的非递归遍历
本题要求根据相关数据类型的定义，写出相关的函数实现，包括：
栈的初始化函数、取栈顶元素，栈是否为空，push和pop函数由裁判程序给出，无需再写。
二叉树的先序遍历函数和中序遍历函数，要求使用非递归算法。后序遍历的非递归算法由裁判程序给出，无需再写。
函数接口定义：
在这里描述函数接口：
#include <iostream>
#define MAXSIZE 100 //顺序栈存储控件的初始分配量
#define OK 1
#define ERROR 0
#define OVERFLOW -1
using namespace std;
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType Data;
struct BiTNode *lchild,*rchild;
int flag;//用于非递归后序遍历
}BiTNode,*BiTree;
static int pushCount = 0; //用于统计入栈的次数
static int popCount = 0; //用于统计出栈的次数
/*------------------------顺序栈的定义---------------------*/
typedef BiTNode* SElemType;//栈中存储的是结点的指针而非结点本身
typedef struct{
SElemType *base;//栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;
/*栈的实现 */
//下面两个函数由裁判程序实现，无需再写
Status Push(SqStack &S,SElemType e);/*元素e入栈*/
Status Pop(SqStack &S,SElemType &e);/* 删除并仅返回S的栈顶元素 */
//下面三个函数请提供实现代码
Status InitStack(SqStack &S); /*栈初始化 */
SElemType GetTop(SqStack S); /* 仅返回S的栈顶元素 */
bool stackEmpty(SqStack S); /*栈是否为空,为空则返回true，否则返回false*/
/*--------------------------堆栈的定义结束------------------*/
//下面三个函数请提供实现代码
void CreateBiTree(BiTree& BT);//先序遍历的顺序建立二叉链表
void InorderTraverse( BiTree BT );//非递归中序遍历
void PreorderTraverse( BiTree BT );//非递归先序遍历
//下面函数由裁判程序实现，无需提供实现代码
void PostorderTraverse( BiTree BT );//非递归后序遍历
void TestStack();
void CreateBiTree1(BiTree& BT);
裁判测试程序样例：
在这里给出函数被调用进行测试：
int main()
{
BiTree BT;
int mode ;
cin>>mode;
switch(mode){
case 0: //测试栈的相关函数定义
TestStack();break;
case 1: //测试CreateBiTree()函数
CreateBiTree(BT);
cout<<"Postorder:";
PostorderTraverse(BT);
cout<<endl;
break;
case 2: //测试PreorderTraverse()函数
CreateBiTree1(BT);
pushCount = popCount = 0;
cout<<"Preorder:"; PreorderTraverse(BT); cout<<endl;
cout<<"pushCount:"<<pushCount<<endl;
cout<<"popCount:"<<popCount<<endl;
break;
default: //测试InorderTraverse()函数
CreateBiTree1(BT);
pushCount = popCount = 0;
cout<<"Inorder:"; InorderTraverse(BT); cout<<endl;
cout<<"pushCount:"<<pushCount<<endl;
cout<<"popCount:"<<popCount<<endl;
}
return 0;
}
/* 请在这里填写答案 */
输入的第一行为测试模式mode赋值：
当输入的mode为0时，测试堆栈的三个函数InitStack、
GetTop、stackEmpty是否正确；
当输入的mode为1时，接着第二行输入二叉树先序的字符顺序，#表示空树，测试先序顺序建立二叉树的函数CreateBiTree是否正确，由裁判程序对二叉树进行后序遍历来测试。
当输入的mode为2时，接着第二行输入二叉树先序的字符顺序，#表示空树，测试先序遍历的非递归函数，因为非递归算法需要使用栈，因此裁判程序中会输出栈的push和pop次数；
当输入的mode为3时，接着第二行输入二叉树先序的字符顺序，#表示空树，测试中序遍历的非递归函数，因为非递归算法需要使用栈，因此裁判程序中会输出栈的push和pop次数。
输入样例：
在这里给出一组输入：
1
ABC##DE#G##F###
输出样例：
在这里给出相应的输出：
Postorder:CGEFDBA
我的答案如下：
Status InitStack(SqStack &S) {
S.base = new SElemType[MAXSIZE];
if (!S.base)
return (OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
SElemType GetTop(SqStack S) {
return *(S.top - 1);
}
bool stackEmpty(SqStack S) {
if (S.top == S.base)
return false;
return true;
}
void CreateBiTree(BiTree &BT) {
char ch;
cin >> ch;
if (ch != '#')
{
BT = new BiTNode;
BT->Data = ch;
CreateBiTree(BT->lchild);
CreateBiTree(BT->lchild);
}
}
void InorderTraverse( BiTree BT ) {
//CreateBiTree(BT);
SqStack S;
InitStack(S);
BiTree p = BT;
//BiTree q = new BiTNode;
while (p || !stackEmpty(S)) {
if (p) {
Push(S, p);
p = p->lchild;
} else {
Pop(S, p);
cout << p->Data;
p = p->rchild;
}
}
}
void PreorderTraverse( BiTree BT ) {
//CreateBiTree(BT);
SqStack S;
InitStack(S);
BiTree p = BT;
//BiTree q = new BiTNode;
while (p || !stackEmpty(S)) {
if (p) {
cout << p->Data;
Push(S, p);
p = p->lchild;
} else {
Pop(S, p);
p = p->rchild;
}
}
}
请问为什么错了啊？
