非递归中序遍历二叉树c

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

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

其中，stack是用来存储节点的栈，curr是当前遍历到的节点。首先将根节点压入栈中，然后遍历其所有左子节点并依次压入栈中，直到没有左子节点为止。然后取出栈顶元素，输出其值，将curr指向其右子节点。重复上述过程，直到所有节点都被遍历完毕。

相关问题

二叉树的非递归中序遍历

二叉树的非递归中序遍历可以通过使用栈来实现。具体实现思路如下：

1. 从根节点开始，将所有左子树节点依次入栈，直到最左边的叶子节点。
2. 弹出栈顶节点并访问它。
3. 如果该节点有右子树，则将右子树节点入栈。
4. 重复步骤2和3，直到栈为空。

下面是C++代码实现：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur != nullptr || !s.empty()) {
        while (cur != nullptr) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        // 访问节点
        cout << cur->val << " ";
        cur = cur->right;
    }
}

其中，`TreeNode`是二叉树节点的结构体，包含`val`、`left`和`right`三个成员变量。

中序遍历二叉树非递归思路

中序遍历二叉树的非递归思路可以使用栈来实现。具体步骤如下：

1. 初始化一个空栈和一个指向二叉树根节点的指针。
2. 将根节点入栈。
3. 当栈不为空时，执行以下步骤：
- 将当前节点的左子树依次入栈，直到当前节点的左子树为空。
- 弹出栈顶节点，访问该节点。
- 将当前指针指向弹出节点的右子树。
4. 重复步骤3，直到栈为空且当前指针为空。

这样就可以按照中序遍历的顺序遍历整个二叉树，而不使用递归。

以下是一个示例代码，演示了如何使用栈实现中序遍历的非递归算法：

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr != nullptr || !s.empty()) {
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }

        curr = s.top();
        s.pop();
        cout << curr->val << " ";

        curr = curr->right;
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "Inorder traversal: ";
    inorderTraversal(root);

    return 0;
}

以上代码会输出二叉树的中序遍历结果。注意，在实际应用中，可以根据需要修改输出方式或者保存遍历结果。