一、树与二叉树：从现实到代码的桥梁

说实话，树这种结构，我第一次接触时觉得挺抽象的。但后来做项目多了才发现——你每天都在用它。文件系统、编译器语法分析、网络路由……背后全是树。今天我们就从最基础的东西开始，把树和二叉树彻底讲透。

1.1 树的定义与基本术语

树是一种非线性的数据结构。它由 n（n≥0）个节点组成，节点之间有明确的层次关系。如果 n=0，我们叫它空树。

为什么叫“树”？你想想看，一棵倒着长的树——根在上，叶子在下。根节点只有一个，往下分叉，最后到叶子节点。嗯，就是这么来的。

下面这些术语，我建议你死记硬背——因为面试必问，项目里也经常用到：

术语	含义	我的经验
根节点	没有父节点的节点	一棵树只有一个根
叶子节点	度为0的节点	没有孩子的节点
父节点/子节点	直接上下层关系	注意是“直接”
兄弟节点	同一父节点的子节点	别搞成堂兄弟
节点的度	节点拥有的子树个数	度=孩子数
树的度	所有节点中最大的度	决定了这棵树的分叉能力
深度/高度	从根到最远叶子的层数	根深度为1或0，看约定
森林	m棵互不相交的树	去掉根就是森林

1.2 二叉树的定义与性质

二叉树是树的一种特例——每个节点最多有两个孩子。说白了，就是每个节点最多分两叉。左孩子、右孩子，位置是固定的，不能颠倒。

为什么二叉树这么重要？我个人的理解是：它既简单又强大。简单是因为只有两个分支，好实现；强大是因为任何树都能转换成二叉树来处理。

这里有个小故事。有一次我在做内存池管理，需要快速定位空闲块。用完全二叉树的性质，通过下标直接算父子关系，省掉了指针开销。嗯，这就是理论落地的感觉。

1.3 二叉树的存储结构

存储二叉树，主要有两种方式。我两种都用过，各有优劣。

1.3.1 顺序存储（数组）

用数组存二叉树，核心思想就是利用完全二叉树的性质。根节点放下标1，左孩子2i，右孩子2i+1。适合完全二叉树，空间利用率高。

// 顺序存储示例
#define MAX_TREE_SIZE 100
typedef struct {
    int data[MAX_TREE_SIZE];  // 0号位置不用或存根
    int last_index;           // 最后一个节点的下标
} SeqBinaryTree;

// 访问节点 i 的左孩子
int left_child(int i) {
    return 2 * i;
}

// 访问节点 i 的右孩子
int right_child(int i) {
    return 2 * i + 1;
}

// 访问节点 i 的父节点
int parent(int i) {
    return i / 2;
}

1.3.2 链式存储（链表）

这是最常用的方式。每个节点包含数据域和两个指针域——左孩子指针和右孩子指针。灵活，不浪费空间。

// 链式存储结构
typedef struct BiTNode {
    int data;                    // 数据域
    struct BiTNode *lchild;      // 左孩子指针
    struct BiTNode *rchild;      // 右孩子指针
} BiTNode, *BiTree;

// 创建一个新节点
BiTNode* create_node(int data) {
    BiTNode *node = (BiTNode*)malloc(sizeof(BiTNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

1.4 二叉树的遍历

遍历，说白了就是把树里的每个节点都访问一遍。怎么访问？有四种经典方式。我个人觉得，前序、中序、后序是深度优先，层序是广度优先。这个理解很重要。

1.4.1 前序遍历（根左右）

先访问根，再遍历左子树，最后遍历右子树。递归实现非常简洁：

void pre_order(BiTree root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);   // 访问根
    pre_order(root->lchild);     // 遍历左子树
    pre_order(root->rchild);     // 遍历右子树
}

1.4.2 中序遍历（左根右）

先遍历左子树，再访问根，最后遍历右子树。对于二叉搜索树，中序遍历得到的是有序序列。

void in_order(BiTree root) {
    if (root == NULL) return;
    
    in_order(root->lchild);      // 遍历左子树
    printf("%d ", root->data);   // 访问根
    in_order(root->rchild);      // 遍历右子树
}

1.4.3 后序遍历（左右根）

先遍历左子树，再遍历右子树，最后访问根。这个顺序在释放树的内存时特别有用——先释放孩子，再释放父节点。

void post_order(BiTree root) {
    if (root == NULL) return;
    
    post_order(root->lchild);    // 遍历左子树
    post_order(root->rchild);    // 遍历右子树
    printf("%d ", root->data);   // 访问根
}

// 释放整棵树（后序遍历的典型应用）
void free_tree(BiTree root) {
    if (root == NULL) return;
    
    free_tree(root->lchild);     // 先释放左子树
    free_tree(root->rchild);     // 再释放右子树
    free(root);                  // 最后释放根节点
}

1.4.4 层序遍历（广度优先）

从上到下，从左到右，一层一层地访问。这需要借助队列来实现：

#include <queue.h>  // 假设有队列库

void level_order(BiTree root) {
    if (root == NULL) return;
    
    Queue q;
    init_queue(&q);
    enqueue(&q, root);
    
    while (!is_empty(&q)) {
        BiTNode *node = dequeue(&q);
        printf("%d ", node->data);
        
        if (node->lchild != NULL)
            enqueue(&q, node->lchild);
        if (node->rchild != NULL)
            enqueue(&q, node->rchild);
    }
}

你可能会问：递归遍历这么简单，为什么还要学非递归？嗯，我在实际项目中遇到过——树深度太大，递归导致栈溢出。那时候你就知道非递归遍历有多重要了。不过那是进阶内容，我们后面再讲。

好了，这一章的内容就到这里。树和二叉树是后续所有高级数据结构的基础——平衡树、红黑树、B树、堆……全都从这里延伸出去。把今天的内容吃透，后面的路就好走了。

---

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