中序遍历二叉树T的非递归算法代码

中序遍历二叉树的非递归算法代码如下：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node || !s.empty()) {
        while (node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

其中，stack是用来存储待访问的节点的，node是当前访问的节点。算法的思路是，先把当前节点的所有左子树节点入栈，然后访问栈顶节点并出栈，最后访问栈顶节点的右子树。重复这个过程直到栈为空。

相关问题

中序遍历二叉树T的非递归算法的代码

下面是中序遍历二叉树T的非递归算法的代码实现，其中假设二叉树节点类型为TreeNode，具有val、left、right三个属性：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        res.add(cur.val);
        cur = cur.right;
    }
    return res;
}

该算法使用了一个栈来辅助遍历，首先将根节点入栈，然后在每次迭代中取出栈顶节点并访问，如果该节点有右子节点，则将右子节点入栈，然后再将左子节点入栈。这样可以保证在访问某个节点时，其左子树已经全部访问完毕。当栈为空时，整个二叉树的中序遍历就完成了。

二叉树的层序遍历先序遍历中序遍历后序遍历非递归算法代码

当然，二叉树的遍历有三种主要方式：先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。非递归的层次遍历（也叫广度优先遍历，从上到下、从左到右）通常使用队列来辅助实现。

这里分别给出这些遍历的非递归算法代码：

1. 层序遍历（广度优先遍历）：

#include <stdio.h>
#include <stdlib.h>
#include <queue>

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

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

    // 使用队列存储每一层的节点
    queue<struct TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = q.front();
            q.pop();
            printf("%d ", node->val); // 打印当前节点值

            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
        }
        printf("\n"); // 换行表示新的一层
    }
}

2. 先序遍历（递归和非递归两种方式，这里是非递归版本，使用栈）：

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

    stack<struct TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        struct TreeNode* node = s.top();
        s.pop();
        printf("%d ", node->val); // 打印当前节点值

        if (node->right != NULL) s.push(node->right);
        if (node->left != NULL) s.push(node->left);
    }
}

3. 中序遍历（非递归，同样使用栈）：

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

    stack<struct TreeNode*> s;
    struct TreeNode* curr = root;

    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        printf("%d ", curr->val); // 打印当前节点值
        curr = curr->right;
    }
}

4. 后序遍历（非递归，使用两个栈）：

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

    stack<struct TreeNode*> s1, s2;
    s1.push(root);

    while (!s1.empty()) {
        struct TreeNode* node = s1.top();
        s1.pop();

        s2.push(node);
        if (node->left != NULL) s1.push(node->left);
        if (node->right != NULL) s1.push(node->right);
    }

    while (!s2.empty()) {
        struct TreeNode* node = s2.top();
        s2.pop();
        printf("%d ", node->val); // 打印当前节点值
    }
}