深入理解二叉树遍历（从零开始掌握C语言中的前序、中序与后序遍历）

二叉树的三种遍历方式

遍历二叉树就是按照某种顺序访问树中的每一个节点。常见的三种遍历方式都基于“深度优先搜索”（DFS），区别仅在于访问根节点的时机不同。

1. 前序遍历（Preorder Traversal）

访问顺序：根节点 → 左子树 → 右子树

前序遍历常用于复制一棵树或生成前缀表达式。

// 前序遍历函数void preorder(struct TreeNode* root) {    if (root == NULL) return;    printf("%d ", root->data);   // 访问根节点    preorder(root->left);        // 遍历左子树    preorder(root->right);       // 遍历右子树}

2. 中序遍历（Inorder Traversal）

访问顺序：左子树 → 根节点 → 右子树

对于二叉搜索树（BST），中序遍历会按升序输出所有节点值。

// 中序遍历函数void inorder(struct TreeNode* root) {    if (root == NULL) return;    inorder(root->left);         // 遍历左子树    printf("%d ", root->data);   // 访问根节点    inorder(root->right);        // 遍历右子树}

3. 后序遍历（Postorder Traversal）

访问顺序：左子树 → 右子树 → 根节点

后序遍历常用于释放内存（先释放子节点再释放父节点）或计算目录大小等场景。

// 后序遍历函数void postorder(struct TreeNode* root) {    if (root == NULL) return;    postorder(root->left);       // 遍历左子树    postorder(root->right);      // 遍历右子树    printf("%d ", root->data);   // 访问根节点}

完整C语言示例

下面是一个完整的C语言程序，演示如何定义二叉树并实现三种遍历方式：

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

总结

通过本教程，你已经掌握了C语言中二叉树遍历的三种核心方法：前序遍历、中序遍历和后序遍历。每种遍历方式都有其独特的应用场景，理解它们的执行顺序和递归逻辑是解决更复杂树问题的关键。

建议你动手编写代码并调试运行，加深对递归调用栈的理解。当你能熟练运用这三种遍历方式时，你就离掌握高级树结构（如AVL树、红黑树）又近了一步！