C++编写代码实现二叉树遍历

Question

C++编写程序，非递归算法实现对二叉树的中序遍历。
按先序序列建立二叉树的二叉链表(用#补齐空结点)，然后借助栈对二叉树进行非递归方式的中序遍历，并输出遍历结果。提示:
1.顺序栈和链栈均可，涉及到的操作:初始化栈、入栈、出栈和判断栈是否为空;
2.若定义二叉链表类型为BiTree，则栈的数据元素类型SElemType为BiTree类型。建议定义:typedef BiTree SElemType:
输入说明:按先序方式依次输入二叉树中各结点的值，注意:用#补齐空结点。输出说明:输出对二叉树进行非递归方式的中序遍历序列。
输入样例:
124##56##7##3##输出样例:
二叉树非递归算法的中序遍历序列:4265713

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题要求我们使用非递归算法实现对二叉树的中序遍历。具体步骤如下：

1. 声明一个顺序栈或链栈用于存储二叉树节点。
2. 定义一个指针p指向当前需要遍历的节点，初始时指向根节点。
3. 在循环中，先将当前节点的所有左子节点依次入栈，直到左子节点为空。入栈之前，先将当前节点p入栈。
4. 当左子节点为空时，从栈顶取出一个节点并打印，然后指针p指向该节点的右子节点。
5. 如果右子节点为空且栈为空，则说明遍历完成，循环结束；否则，返回步骤3。

下面是一个实现示例：

#include <iostream>
#include <stack>
using namespace std;

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

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);
    }
}

void InOrderNonRecursion(BiTree T) {
    stack<BiTree> s;
    BiTree p = T;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            cout << p->data;
            p = p->rchild;
        }
    }
}

int main() {
    BiTree T;
    CreateBiTree(T);
    cout << "二叉树非递归算法的中序遍历序列:";
    InOrderNonRecursion(T);
    cout << endl;
    return 0;
}

输入样例:

124##56##7##3##

输出样例:

二叉树非递归算法的中序遍历序列:4265713