C语言后序遍历详解（手把手教你实现二叉树的后序遍历算法）

为什么需要后序遍历？

后序遍历常用于需要先处理子节点再处理父节点的场景，比如：

• 释放二叉树内存（先释放左右子树，再释放根）
• 计算目录大小（先统计子目录，再加总到父目录）
• 表达式求值（后缀表达式）

C语言实现后序遍历

我们先定义一个简单的二叉树节点结构：

// 定义二叉树节点结构typedef struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;

接下来是核心的C语言递归遍历函数：

// 后序遍历函数void postOrderTraversal(TreeNode* root) {    // 递归终止条件：如果节点为空，直接返回    if (root == NULL) {        return;    }        // 1. 遍历左子树    postOrderTraversal(root->left);        // 2. 遍历右子树    postOrderTraversal(root->right);        // 3. 访问根节点（这里我们只是打印数据）    printf("%d ", root->data);}

完整示例程序

下面是一个完整的可运行程序，演示如何构建一棵树并进行数据结构后序遍历：

#include <stdio.h>#include <stdlib.h>typedef struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;// 创建新节点TreeNode* createNode(int data) {    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));    newNode->data = data;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}// 后序遍历void postOrderTraversal(TreeNode* root) {    if (root == NULL) return;    postOrderTraversal(root->left);    postOrderTraversal(root->right);    printf("%d ", root->data);}int main() {    // 构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5        TreeNode* root = createNode(1);    root->left = createNode(2);    root->right = createNode(3);    root->left->left = createNode(4);    root->left->right = createNode(5);        printf("后序遍历结果: ");    postOrderTraversal(root);  // 输出: 4 5 2 3 1    printf("\n");        return 0;}

运行结果

运行上述程序，输出为：

后序遍历结果: 4 5 2 3 1

总结

通过本文，你已经掌握了C语言后序遍历的基本原理和实现方法。记住后序遍历的口诀“左 → 右 → 根”，并在实际项目中灵活运用。无论是面试还是实际开发，二叉树后序遍历都是数据结构中的基础技能之一。

如果你觉得这篇文章对你有帮助，不妨动手敲一遍代码，加深理解！