二叉树非递归遍历算法

栈及二叉树的非递归遍历
本题要求根据相关数据类型的定义，写出相关的函数实现，包括：

栈的初始化函数、取栈顶元素，栈是否为空，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;
        }
    }
}

请问为什么错了啊？

二叉树非递归遍历算法可以参考下这个

二叉树的非递归遍历（c/c++）_消逝者的博客-CSDN博客_c++二叉树非递归遍历二叉树的非递归遍历分为三种：先序非递归遍历，中序非递归遍历和后续非递归遍历。这和递归遍历的结果是一样的，区别只是在于采用了循环结构。先序非递归遍历采用辅助数据结构栈来实现，先序遍历是按照先根，后左子树，再右子树的顺序进行递归访问的。由于栈是先入后出的，所以入栈顺序为先右孩子后左孩子。非递归的算法是先将根结点入栈，栈不为空时：根结点出栈并访问，然后将右孩子入栈，再将左孩子入栈；左孩子出栈并访问...

https://blog.csdn.net/Little_ant_/article/details/104234868

bool stackEmpty(SqStack S) {
if (S.top == S.base)
return false;
return true;
}
好像返回值有问题，题上说，栈是否为空,为空则返回true，否则返回false。

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632

所以怎么写啊qwq

15行
bool stackEmpty(SqStack S) {
if (S.top == S.base)
return false;
return true;

==时，应该为true
后面为false


//在这里描述函数接口：
#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 Push(SqStack &S,SElemType e)
{
    if(S.top-S.base==S.stacksize) return ERROR;
    *S.top=e;
    S.top++;
    return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
    if(S.top==S.base) return ERROR;
    S.top--;
    e=*S.top;
    return OK;
}
//下面三个函数请提供实现代码
Status InitStack(SqStack &S);  /*栈初始化 */
SElemType GetTop(SqStack S);    /* 仅返回S的栈顶元素 */
bool stackEmpty(SqStack S);   /*栈是否为空,为空则返回true，否则返回false*/
/*--------------------------堆栈的定义结束------------------*/
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 true;
    else return false;    
}
//下面三个函数请提供实现代码
void CreateBiTree(BiTree& BT);//先序遍历的顺序建立二叉链表
void InorderTraverse( BiTree BT );//非递归中序遍历
void PreorderTraverse( BiTree BT );//非递归先序遍历

void CreateBiTree(BiTree& BT)
{
    char ch;
    cin>>ch;
    if(ch=='#') BT=NULL;
    else
    {
        BT=new BiTNode;
        BT->Data=ch;
        cout<<BT->Data; 
        CreateBiTree(BT->lchild);
        CreateBiTree(BT->rchild);
    }
}
void PreorderTraverse( BiTree 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,q);
            p=q->rchild;
        }
    }
}
void InorderTraverse( BiTree 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,q);
            cout<<q->Data;
            p=p->rchild;
        }
    }
}
//下面函数由裁判程序实现，无需提供实现代码
void PostorderTraverse( BiTree BT );//非递归后序遍历
//void TestStack();
//void CreateBiTree1(BiTree& BT);
void PostorderTraverse(BiTree BT){
//二叉树的非递归后序遍历 
    BiTree r=NULL;
    SqStack S;
    InitStack(S);
    BiTree p=BT;
    BiTree q=new BiTNode;
    while(p||!stackEmpty(S)){
        if(p!=NULL){//当结点不为空时，该结点压栈并遍历其左子树 
            Push(S,p);
            p=p->lchild;
        }
        else{//当左子树结点为空时，取栈顶元素进行右子树的遍历， 
            p=GetTop(S);
            if(p->rchild!=NULL&&p->rchild!=r){
            //右子树不为空且右子树没有被遍历过 
                p=p->rchild;
                Push(S,p);//将该结点压栈，遍历其左子树 
                p=p->lchild;
            }
            else{//右子树为空或已遍历则取栈顶元素访问该结点的信息 
                Pop(S,p);
                cout<<p->Data;
                r=p;//标记遍历过的点，用于判断右子树是否已遍历 
                p=NULL;//遍历结点的指针置空，下次遍历直接取栈中的值 
            }
        }
    }
}

//在这里给出函数被调用进行测试：
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()函数
            CreateBiTree(BT);
            pushCount = popCount = 0;
            cout<<"Preorder:"; PreorderTraverse(BT); cout<<endl;
            cout<<"pushCount:"<<pushCount<<endl;
            cout<<"popCount:"<<popCount<<endl;
            break;
        default: //测试InorderTraverse()函数
            CreateBiTree(BT);
            pushCount = popCount = 0;
            cout<<"Inorder:"; InorderTraverse(BT); cout<<endl;
            cout<<"pushCount:"<<pushCount<<endl;
            cout<<"popCount:"<<popCount<<endl;
    }
    return 0;
}
/* 请在这里填写答案 */