当前位置：首页 > news >正文

后序遍历的递归算法核心思想是：按照“左子树 → 右子树 → 根节点”的顺序访问二叉树中的每个节点

news 2026/5/12 18:38:23

后序遍历的递归算法核心思想是：按照“左子树 → 右子树 → 根节点”的顺序访问二叉树中的每个节点。以下是完整的C语言实现示例：

#include<stdio.h>#include<stdlib.h>// 二叉树节点定义typedefstructTreeNode{intdata;structTreeNode*lchild;structTreeNode*rchild;}TreeNode;// 后序遍历递归实现voidPostOrder(TreeNode*root){if(root!=NULL){PostOrder(root->lchild);// 遍历左子树PostOrder(root->rchild);// 遍历右子树printf("%d ",root->data);// 访问根节点}}

关于三种遍历的路线逻辑，可以形象地理解为从根节点出发，沿二叉树外缘逆时针走一圈，每个节点会被经过三次：

第一次经过时访问 → 先序遍历（根左右）
第二次经过时访问 → 中序遍历（左根右）
第三次经过时访问 → 后序遍历（左右根）

时间复杂度分析：
由于每个节点仅被访问一次，无论哪种遍历方式，总时间复杂度均为O(n)。

空间复杂度分析：
主要消耗在系统调用栈上，取决于递归深度，即树的高度 h：

平均情况（平衡树）：O(log n)
最坏情况（单枝树，退化为链表）：O(n)

非递归遍历的基本思路是使用显式栈模拟函数调用栈的行为。以中序遍历为例，其非递归实现如下：

#include<stdbool.h>voidInOrderNonRecursive(TreeNode*root){TreeNode*stack[100];inttop=-1;TreeNode*p=root;while(p!=NULL||top!=-1){if(p!=NULL){stack[++top]=p;p=p->lchild;// 一直向左走}else{p=stack[top--];// 出栈printf("%d ",p->data);// 访问根p=p->rchild;// 转向右子树}}}

对于后序遍历的非递归实现，较为复杂，通常需要记录前驱节点或使用标志位来判断是否已遍历完左右子树。
实现二叉树的后序遍历非递归算法的关键在于：在不使用递归的情况下，正确判断何时访问根节点。由于后序遍历是“左→右→根”，我们必须确保在访问根节点前，其左右子树都已处理完毕。

常用方法是使用一个栈来保存待处理的节点，并借助一个指针记录上一次访问的节点（prev），从而判断当前节点是否可以被访问。

✅ 后序遍历非递归算法（单栈 + 标记法）

#include<stdio.h>#include<stdlib.h>typedefstructTreeNode{intdata;structTreeNode*lchild;structTreeNode*rchild;}TreeNode;voidPostOrderNonRecursive(TreeNode*root){if(root==NULL)return;TreeNode*stack[100];// 模拟栈inttop=-1;TreeNode*prev=NULL;// 记录上一次访问的节点TreeNode*curr=root;while(curr!=NULL||top!=-1){// 一直走到最左边if(curr!=NULL){stack[++top]=curr;curr=curr->lchild;}else{// 查看栈顶元素（不弹出）curr=stack[top];// 如果右子树为空或已被访问过，则可以访问当前节点if(curr->rchild==NULL||curr->rchild==prev){printf("%d ",curr->data);top--;// 弹出栈prev=curr;// 更新已访问节点curr=NULL;// 当前节点置空，避免重复入栈}else{// 否则转向右子树curr=curr->rchild;}}}}