二叉树的非递归中序遍历（栈）不知道哪里错了
#include <iostream>#include <stdlib.h>
#define OK 1
#define MAXSIZE 100
#define ERROR -2
#define MAXSIZE 100
using namespace std;
typedef char TElemType;//二叉树的数据域数据类型为char型
typedef int Status;
typedef struct BiTNode { //首先定义二叉树的结点
TElemType data;
struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;
typedef struct {//定义栈的结构体
BiTree* base;//栈的指针类型为二叉树指针型
BiTree* top;
int stacksize;
}SqStack;
void InitStack(SqStack &S) {//初始化栈
S.base = new BiTree;
if (!S.base)exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
}
Status StackEmpty(SqStack S) {
if (S.top == S.base) return true;
else return false;
}
int Push(SqStack &S, BiTree e) {//入栈
if (S.top - S.base == S.stacksize)
return ERROR;
*S.top++ = e;//头指针所指内容为e
return OK;
}
int POP(SqStack &S, BiTree &q) { //出栈
if (S.top == S.base)
return ERROR;
q = *S.top;
S.top--;
return OK;
}
void InOrdertraverse(BiTree T) {
SqStack S;//建立栈
InitStack(S);//初始化栈
BiTree p = T;//建立一个指向根节点的指针
//BiTNode* q = new BiTNode;//申请一个指向二叉树的地址空间
while (p || !StackEmpty(S)) {//只有当p地址为空或者栈为空时循环才会停止
if (p) {//如果p不为空的话
Push(S, p);//把p内的地址入栈
p = p->lchild;//p指向左孩子
}
else {//如果p为空的话
POP(S, p);//把上一个结点出栈并输出
cout << p->data;
p = p->rchild;//把指针指向上一个结点的右孩子
}
}
}
void InOrderTraverse(BiTree T) {//中序遍历
if (T) {
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
}
}
void CreateBiTree(BiTree& T) {
char ch;
cin >> ch;
if (ch == '#')
T = NULL;
else {
T = new BiTNode;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
int main() {
BiTree T;
CreateBiTree(T);
InOrdertraverse(T);
return 0;
}
页:
[1]