求二叉链表非递归先序序列

Question

/*分别设计出先序、中序和后序遍历二叉树的非递归算法。
*/
#include <iostream>
using namespace std;
#define max 100
typedef char element;
typedef struct lBNode {
    element data;
    struct lBNode* lChild, * rChild;
}BiNode, * BiTree;
void  create(BiTree &T) {
    char ch;
     cin >> ch;
    if (ch == '#') {
        T = NULL;
        return;
    }
    else {
        T = new BiNode;
        T->data = ch;
        create(T->lChild);
        create(T->rChild);
    }
}
//顺序栈，元素为BiNode类型的指针
typedef struct sStack {
    BiNode data[max];
    int top;
}seqStack;
void initialStack(seqStack &S) {
    S.top = -1;
}
bool stackEmpty(seqStack& S) {
    if (S.top == -1)
        return true;
    else
        return false;
}
//取栈顶
bool stackTop(seqStack& S, BiNode* x) {
    if (stackEmpty(S))
        return false;
    else {
        *x = S.data[S.top];
        return true;
    }
}
//入栈
bool pushStack(seqStack& S, BiNode* x) {
    S.top++;
    S.data[S.top] = *x;
    return true;
}
//出栈
bool popStack(seqStack& S, BiNode*& x) {
    if (stackEmpty(S))
        return false;
    else {
        *x = S.data[S.top];
        S.top--;
        return true;
    }
}
//先序遍历非递归算法
void preTraverseNR(BiNode* T) {
    BiNode* p;
    seqStack S;
    initialStack(S);
    p = T;
    while (p || !stackEmpty(S)) {
        if (p) {
            cout << p->data << " ";
            pushStack(S, p);
            p = p->lChild;
        }
        else {
            popStack(S, p);
            p = p->rChild;
        }
    }
}
//中序遍历非递归算法
void InTraverseNR(BiNode* T) {
    BiNode* p;
    seqStack S;
    initialStack(S);
    p = T;
    while (p || !stackEmpty(S)) {
        if (p) {
            pushStack(S, p);
            p = p->lChild;
        }
        else {
            popStack(S, p);
            cout << p->data << " ";
            p = p->rChild;
        }
    }
}
//后序遍历非递归算法
void PostTraverseNR(BiNode* T) {
    BiNode* p;
    seqStack S;
    initialStack(S);
    int tag[max];//标记左子树，右子树
    int n;
    p = T;
    while (p || !stackEmpty(S)) {
        if (p) {
            pushStack(S, p);
            tag[S.top] = 0;//标记遍历左子树
            p = p->lChild;//循环遍历左子树
        }
        else {//左子树遍历完成
            stackTop(S, p);
            if (tag[S.top] == 0) {
                tag[S.top] = 1;
                p = p->rChild;
            }
            else {//左右子树均已经遍历
                popStack(S, p);
                cout << p->data << " ";
                p = NULL;
            }
        }
    }
}

int main() {
    BiNode* T=new BiNode;
    create(T);
     preTraverseNR(T);
    return 0;
}

如题，为什么入栈函数有问题呢，报错是什么意思？

Answer 1

• 你可以看下这个问题的回答https://ask.csdn.net/questions/192169
• 这篇博客也不错, 你可以看下【数据结构】计算二叉树的所有单，双分支结点个数，叶节点个数
• 除此之外, 这篇博客: 字节跳动暑期实习面试题准备中的 讲解算法：一个连连看小游戏（二维数组存储），如何判断两个点可以消去？时间复杂度？连线最多只有两个拐点，怎么判断？ 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• ---

  题目来源：
  牛客网：字节跳动后端一面面试经验
  CSDN：字节跳动后端开发实习面试一
  牛客网：字节跳动一面二面凉经
  牛客网：字节跳动后台开发实习三面
  牛客网：字节跳动（上海）后端开发实习一面二面
  知识点总结：
  GitHub大佬总结

• 您还可以看一下 刘伶华老师的软件测试经典面试题剖析课程中的 你还有什么问题想问？小节, 巩固相关知识点