第22章指针与二叉树

课程目录第22章指针与二叉树

第22章指针与二叉树：指针的进阶应用

二叉树，说白了就是用指针把一堆节点串起来的数据结构。我刚开始学的时候，总觉得这东西离实际开发很远。直到有一次做嵌入式文件系统的目录树管理，才发现——嗯，二叉树就在我们身边。

22.1 二叉树的指针表示

每个二叉树节点，本质上就是一个结构体，里面存着数据，还有两个指针：一个指向左孩子，一个指向右孩子。我个人习惯这样定义：

typedef struct TreeNode {
    int data;                 // 数据域
    struct TreeNode *left;    // 左孩子指针
    struct TreeNode *right;   // 右孩子指针
} TreeNode;

你看，这个结构体里有两个指针。它们指向的是同类型的节点。这就是所谓的「自引用结构体」。C语言里，结构体不能包含自身类型的实例，但可以包含指向自身类型的指针。这一点，我在面试新人时经常考。

核心理解：二叉树的指针表示，就是用两个指针分别记录左右分支的入口。左指针为空，说明左边没节点了；右指针为空，说明右边没节点了。

创建一个节点很简单：

TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

我曾经在一个资源受限的MCU项目里，malloc失败导致系统直接挂掉。从那以后，我每次malloc都会检查返回值。你想想看，嵌入式环境里内存本来就紧张，不检查就是给自己挖坑。

22.2 二叉树的构建

构建二叉树，说白了就是不断创建节点，然后把它们用指针连起来。我习惯先创建根节点，再递归地创建左右子树。

// 构建一棵简单的二叉树
//       1
//      / \
//     2   3
//    / \
//   4   5
TreeNode* buildTree() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    return root;
}

这里要注意：每个节点的左右指针，要么指向另一个节点，要么是NULL。NULL就是终点标志。遍历的时候，遇到NULL就该回头了。

避坑指南：我曾经在删除二叉树时，忘了递归释放子节点，直接free了根节点。结果子节点变成了野指针，后续程序跑着跑着就崩了。记住：释放二叉树一定要从叶子节点开始，一层层往上释放。

22.3 前序遍历

前序遍历的顺序是：根节点 → 左子树 → 右子树。说白了就是「先访问自己，再访问左边，最后访问右边」。

void preOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);  // 先访问根
    preOrder(root->left);       // 再遍历左子树
    preOrder(root->right);      // 最后遍历右子树
}

对于上面那棵树，前序遍历的结果是：1 2 4 5 3。

你想想看，为什么叫「前序」？因为访问根节点的操作，发生在遍历左右子树之前。这个「前」字，指的就是根节点被优先处理。

22.4 中序遍历

中序遍历的顺序是：左子树 → 根节点 → 右子树。也就是「先左边，再自己，最后右边」。

void inOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);        // 先遍历左子树
    printf("%d ", root->data);  // 再访问根
    inOrder(root->right);       // 最后遍历右子树
}

中序遍历结果：4 2 5 1 3。

这里有个有意思的点：对于二叉搜索树，中序遍历得到的结果是有序的。我在做嵌入式配置表管理时，就用这个特性来实现有序数据的快速查找。

22.5 后序遍历

后序遍历的顺序是：左子树 → 右子树 → 根节点。也就是「先左边，再右边，最后自己」。

void postOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);      // 先遍历左子树
    postOrder(root->right);     // 再遍历右子树
    printf("%d ", root->data);  // 最后访问根
}

后序遍历结果：4 5 2 3 1。

后序遍历有个实际用途：释放二叉树。因为你要先释放子节点，才能释放父节点。这正好符合后序遍历的顺序。

个人经验：我建议你写代码时，把三种遍历放在一起对比着看。你会发现，代码结构几乎一模一样，只是printf的位置不同。理解了这一点，遍历就掌握了八成。

22.6 三种遍历的对比

遍历方式	访问顺序	示例结果	典型应用
前序遍历	根 → 左 → 右	1 2 4 5 3	复制二叉树
中序遍历	左 → 根 → 右	4 2 5 1 3	二叉搜索树排序
后序遍历	左 → 右 → 根	4 5 2 3 1	释放二叉树

22.7 知识体系图

下面这张图，帮你理清二叉树指针与遍历的核心逻辑：

22.8 完整示例代码

把上面所有代码拼在一起，就是一个完整的二叉树遍历程序：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) return NULL;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

TreeNode* buildTree() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    return root;
}

void preOrder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode *root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

void postOrder(TreeNode *root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

void freeTree(TreeNode *root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    TreeNode *root = buildTree();
    
    printf("前序遍历: ");
    preOrder(root);
    printf("\n");
    
    printf("中序遍历: ");
    inOrder(root);
    printf("\n");
    
    printf("后序遍历: ");
    postOrder(root);
    printf("\n");
    
    freeTree(root);
    return 0;
}

运行结果：

前序遍历: 1 2 4 5 3
中序遍历: 4 2 5 1 3
后序遍历: 4 5 2 3 1

嗯，到这里，二叉树的指针表示和三种遍历就讲完了。说白了，指针就是用来「指路」的，遍历就是按照一定规则去「走路」。你只要记住：前序先看自己，中序左边看完再看自己，后序最后看自己。这个规律，我在实际项目中用了无数次，从来没出过问题。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录