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

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

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` 表示节点的值。函数返回中序遍历的结果列表。

相关问题

C语言用非递归算法中序遍历二叉树，输出其中序序列，写出完整代码

假设二叉树的结构体定义如下：

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

非递归中序遍历二叉树的基本思路是使用栈来模拟递归过程，这里给出完整代码实现：

void inorderTraversal(TreeNode* root) {
    if (root == NULL)
        return;

    TreeNode* stack[1000];
    int top = -1;
    TreeNode* p = root;

    while (p != NULL || top != -1) {
        // 将当前节点的左子树全部压入栈中
        while (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }

        // 弹出栈顶元素并输出
        p = stack[top--];
        printf("%d ", p->val);

        // 移动到右子树
        p = p->right;
    }
}

在主函数中调用该函数即可输出二叉树的中序序列。

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

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

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

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

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