c++中如何实现后序遍历_c++二叉树后序遍历方法-C++-PHP中文网

c++中如何实现后序遍历_c++二叉树后序遍历方法

尼克

发布： 2025-09-26 08:53:02

原创

808人浏览过

答案是：C++中二叉树后序遍历有递归和迭代两种方法，顺序为左→右→根，递归简洁但可能栈溢出，迭代用栈模拟，适合深树。

c++中如何实现后序遍历_c++二叉树后序遍历方法

在C++中实现二叉树的后序遍历，主要有两种方法：递归和迭代。后序遍历的顺序是“左子树 → 右子树 → 根节点”，适合用于释放树节点或计算表达式树等场景。

定义二叉树节点结构

在开始前，先定义一个基本的二叉树节点结构：

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

登录后复制

方法一：递归实现

递归是最直观的方式，按照“左→右→根”的顺序访问节点。

<pre class="brush:php;toolbar:false;">
void postorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) return;
<pre class="brush:php;toolbar:false;"><code>postorderTraversalRecursive(root->left);  // 遍历左子树
postorderTraversalRecursive(root->right); // 遍历右子树
std::cout << root->val << " ";            // 访问根节点

登录后复制

}

优点是代码简洁易懂，缺点是在树很深时可能引发栈溢出。

方法二：迭代实现（使用栈）

迭代法用显式栈模拟递归过程。关键点是判断节点是否已经处理过右子树。

一种常见做法是使用一个指针记录上一个访问的节点，避免重复进入右子树：

void postorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) return;
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">std::stack<TreeNode*> stack;
TreeNode* lastVisited = nullptr;
TreeNode* current = root;

while (current != nullptr || !stack.empty()) {
    if (current != nullptr) {
        stack.push(current);
        current = current->left;  // 一直向左走
    } else {
        TreeNode* peekNode = stack.top();
        // 如果右子树存在且未被访问过，进入右子树
        if (peekNode->right != nullptr && lastVisited != peekNode->right) {
            current = peekNode->right;
        } else {
            std::cout << peekNode->val << " ";
            lastVisited = stack.top();
            stack.pop();
        }
    }
}

登录后复制

}

这种方法空间复杂度为O(h)，h为树的高度，适合深度较大的树。

测试示例

你可以这样测试上述代码：

UP简历

基于AI技术的免费在线简历制作工具

128

查看详情

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">std::cout << "后序遍历结果: ";
postorderTraversalRecursive(root); // 输出: 3 2 1
std::cout << std::endl;

return 0;

登录后复制

}

基本上就这些。递归写起来快，迭代更安全。根据实际需求选择合适的方法即可。

立即学习“C++免费学习笔记（深入）”；

以上就是c++++中如何实现后序遍历_c++二叉树后序遍历方法的详细内容，更多请关注php中文网其它相关文章！