c++ 二叉树的非递归遍历

二叉树的非递归遍历方式有三种，分别是前序遍历、中序遍历和后序遍历。

前序遍历：前序遍历的非递归实现需要借助一个辅助栈。首先将根节点入栈，然后开始循环，每次循环先取出栈顶元素，并输出该元素的值，然后判断该节点是否有右子节点，如果有，则入栈，再判断是否有左子节点，如果有，则入栈。需要注意的是，因为栈是后进先出的数据结构，所以在入栈的时候，先入右子节点再入左子节点，这样才能保证访问节点的顺序符合前序遍历。

中序遍历：中序遍历的非递归实现同样需要借助一个辅助栈。首先将根节点压入栈，然后不断将根节点的左子节点入栈，并将指针指向左子节点，直到左子节点为空。这时开始循环，每次循环先取出栈顶元素，并输出该元素的值，然后判断该节点是否有右子节点，如果有，则将右子节点压入栈。

后序遍历：后序遍历的非递归实现需要两个栈。首先将根节点入栈1，然后开始循环，从栈1中取出栈顶元素，将其值保存到一个临时变量中，然后将该节点的左子节点和右子节点入栈1。然后判断栈1是否为空，如果不为空，则重复上述操作，否则开始循环栈2，从栈2中取出栈顶元素，并输出该元素的值。在将节点入栈1时，先入左子节点再入右子节点，这样遍历完后输出的顺序就是后序遍历的顺序。

相关问题

二叉树的非递归遍历c++

以下是二叉树的非递归遍历C语言代码：

1. 非递归先序遍历

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

2. 非递归中序遍历

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

3. 非递归后序遍历

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

二叉树dfs递归遍历

二叉树的深度优先遍历(DFS)是一种递归的遍历方式，它按照根节点-左子树-右子树的顺序进行遍历。具体的步骤如下：

1. 若二叉树为空，则直接返回。
2. 遍历根节点，可以进行相应的操作。
3. 递归地对左子树进行深度优先遍历。
4. 递归地对右子树进行深度优先遍历。

这样就可以实现对二叉树的深度优先遍历。具体的遍历顺序取决于遍历的顺序，可以选择先序遍历、中序遍历或后序遍历。例如，对于下面的二叉树：

1
/ \
2 3
/ \ / \
4 5 6 7

先序遍历的结果为：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
中序遍历的结果为：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
后序遍历的结果为：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

通过递归遍历二叉树，我们可以按照先序、中序或后序的方式获取节点的值，进而对二叉树进行处理。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [数据结构—树和二叉树-二叉树的递归遍历（DFS）](https://blog.csdn.net/karry_zzj/article/details/68951349)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [二叉树非递归遍历（先序、中序、后序）（C++）](https://blog.csdn.net/AAAAA1235555/article/details/121898358)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]