不使用递归可以遍历二叉树吗

是的，可以使用迭代的方式来遍历二叉树，从而避免使用递归。下面以中序遍历为例说明如何使用迭代的方式遍历二叉树。

中序遍历的迭代实现使用了栈（Stack）。首先，将根节点压入栈中，然后将左子树的所有节点依次压入栈中，直到左子树为空；此时，从栈中弹出一个节点，并输出该节点的值。然后，将该节点的右子树的所有节点依次压入栈中，重复上述操作，直到栈为空。

以下是中序遍历的迭代实现的示例代码（假设二叉树的节点类型为Node）：

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

需要注意的是，迭代实现的中序遍历中，每个节点都会被压入和弹出栈中恰好一次，因此时间复杂度为 O(n)。

相关问题

先序非递归遍历算法遍历二叉树 ​中序非递归遍历算法遍历二叉树 ​后序非递归遍历算法遍历二叉树 ​层序遍历二叉树

好的，我可以给您介绍一下二叉树的四种非递归遍历算法以及层序遍历。

先序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 当栈不为空时，取出栈顶元素并访问它。
3. 将当前节点的右子节点（如果存在）入栈，再将左子节点（如果存在）入栈。
4. 重复步骤2-3，直到栈为空。

中序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 如果当前节点不为空，则将当前节点的左子节点全部入栈，并将当前节点置为左子节点。
3. 如果当前节点为空，则取出栈顶元素并访问它，将当前节点置为它的右子节点。
4. 重复步骤2-3，直到栈为空。

后序非递归遍历算法：
1. 新建两个栈：s1和s2，将根节点入s1。
2. 当s1不为空时，取出栈顶元素并将其压入s2中。
3. 将当前节点的左子节点（如果存在）入s1，再将右子节点（如果存在）入s1。
4. 重复步骤2-3，直到s1为空。
5. 依次访问s2中的元素即可得到后序遍历结果。

层序遍历算法：
1. 新建一个队列，将根节点入队。
2. 当队列不为空时，取出队首元素并访问它。
3. 将当前节点的左子节点（如果存在）入队，再将右子节点（如果存在）入队。
4. 重复步骤2-3，直到队列为空。

C语言用递归算法遍历二叉树

递归算法是二叉树遍历中最常用的方法之一，以下是C语言中使用递归算法遍历二叉树的代码示例：

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

// 定义二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 中序遍历二叉树
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    // 创建二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // 中序遍历二叉树
    inorderTraversal(root);

    return 0;
}

以上代码中，我们定义了一个二叉树结构体，包含节点值以及左右子树指针。使用递归算法，我们可以通过中序遍历的方式遍历整个二叉树。如果节点为空，则直接返回；否则，递归遍历左子树，输出当前节点的值，再递归遍历右子树。最后，在主函数中我们创建了一个二叉树，并对其进行中序遍历。