用非递归算法中序遍历二叉树，输出其中序序列

非递归算法中序遍历二叉树需要用到栈，具体步骤如下：

1. 将根节点入栈。
2. 只要栈不为空，执行以下操作：
- 将栈顶节点弹出，访问该节点。
- 如果该节点有右子树，将右子树入栈。
- 如果该节点有左子树，将左子树入栈。
3. 遍历结束。

代码如下：

def inorder_traversal(root):
    if not root: # 如果根节点为空，直接返回空列表
        return []
    stack = [] # 栈
    res = [] # 用于存储遍历结果
    cur = root # 当前节点
    while stack or cur:
        if cur: # 如果当前节点不为空，将当前节点入栈，并将当前节点更新为左子节点
            stack.append(cur)
            cur = cur.left
        else: # 如果当前节点为空，弹出栈顶节点，访问该节点，将当前节点更新为右子节点
            node = stack.pop()
            res.append(node.val)
            cur = node.right
    return res

其中，`root` 表示二叉树的根节点，`val` 表示节点的值。函数返回中序遍历的结果列表。

相关问题

// 用非递归算法实现中序遍历二叉树，输出遍历序列 void InOrderTraverseNon (BiTree T) { }

// 非递归方式实现中序遍历二叉树，中序遍历的顺序通常是左子树 -> 根节点 -> 右子树。这里可以借助栈来辅助完成：

#include <iostream>
using namespace std;

// 假设已经有一个定义好的二叉树结点结构 BiTree 和其基本操作

void push(BiTree* &T, stack<BiTree*> s) {
    if (T != nullptr) {
        s.push(T);
        T = T->left;
    }
}

void pop(stack<BiTree*> &s, BiTree *&T) {
    if (!s.empty()) {
        T = s.top();
        s.pop();
        T = T->right;
    }
}

void InOrderTraverseNon(BiTree *T) {
    stack<BiTree*> s;
    while (T || !s.empty()) {
        // 当前节点不为空或者栈不空，继续遍历
        while (T) {
            push(&T, s);   // 先将根节点压入栈，并转向左子树
            T = T->left;
        }
        T = s.top();      // 弹出栈顶元素作为当前节点
        cout << T->val << " ";  // 访问该节点
        pop(s, T);       // 结束访问后转向右子树
    }
}

int main() {
    // 测试实例
    BiTree testTree; // 初始化二叉树
    InOrderTraverseNon(&testTree);
    return 0;
}

非递归中序遍历二叉树：要求从键盘输入二叉树各结点的值，并使用二叉链表来存储二叉树；使用非递归算法遍历二叉树，在屏幕上打印出二叉树中序遍历序列。

好的，我可以为您解答这个问题。

首先，我们需要定义二叉树的结构体，包括节点的值，左右子树指针：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

然后，我们可以使用一个栈来模拟递归的过程，将根节点及其左子树的所有节点依次压入栈中，然后依次出栈进行遍历。

具体的算法流程如下：

1. 定义一个栈和一个指针cur，初始时cur指向根节点。
2. 当cur不为空或栈不为空时，进行循环：
* 如果cur不为空，则将cur入栈，并令cur指向其左子节点。
* 如果cur为空，则从栈中弹出一个节点，并将其值打印出来，然后令cur指向其右子节点。
3. 当栈为空且cur为空时，遍历结束。

下面是代码实现：

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur != NULL || !s.empty()) {
        if (cur != NULL) {
            s.push(cur);
            cur = cur->left;
        } else {
            cur = s.top();
            s.pop();
            printf("%d ", cur->val);
            cur = cur->right;
        }
    }
}

这样，我们就可以从键盘输入二叉树的各节点值，使用二叉链表来存储二叉树，并使用非递归算法遍历二叉树，输出中序遍历序列了。