二叉树基础：从定义到两种存储方式

说实话，二叉树这东西，我刚入行时觉得它就是个理论玩具。直到有一次做嵌入式协议栈，需要快速查找配置参数，用数组硬查太慢，链表又不好管理。后来一拍脑袋——用二叉搜索树啊！从那以后，我对二叉树的态度彻底变了。

今天咱们就把二叉树的基础打牢。说白了，它就是每个节点最多有两个孩子的树结构。左孩子、右孩子，就这么简单。

二叉树的定义与性质

先给个正式定义：二叉树是n个节点的有限集合。要么是空集（n=0），要么由一个根节点加上两棵互不相交的左子树和右子树组成。

嗯，这里要注意——左右子树是有顺序的，不能随便换。我在项目中见过有人把左右子树搞反，结果遍历出来的数据顺序全乱了，排查了半天。

二叉树有几个重要性质，我挑最常用的说：

• 性质1：第i层最多有 2^(i-1) 个节点（i≥1）。比如第3层最多4个节点。
• 性质2：深度为k的二叉树，最多有 2^k - 1 个节点。深度为3的树最多7个节点。
• 性质3：叶子节点数 = 度为2的节点数 + 1。这个性质在验证树结构时特别有用。

你想想看，为什么完全二叉树适合顺序存储？因为它的节点编号和数组下标能完美对应，没有空洞。

二叉树的顺序存储

顺序存储，就是用数组来存二叉树。核心思路：把根节点放在下标1的位置（有人从0开始，但我习惯从1），然后：

• 下标为i的节点，左孩子下标是 2*i
• 右孩子下标是 2*i + 1
• 父节点下标是 i/2（整数除法）

举个例子，一个完全二叉树，节点值分别是 A、B、C、D、E，存储到数组里就是：

// 顺序存储二叉树
// 下标:  1   2   3   4   5
// 值:    A   B   C   D   E

// 访问节点
char getLeftChild(char tree[], int i) {
    int left = 2 * i;
    if (left <= MAX_SIZE && tree[left] != '\0')
        return tree[left];
    return '\0';
}

char getRightChild(char tree[], int i) {
    int right = 2 * i + 1;
    if (right <= MAX_SIZE && tree[right] != '\0')
        return tree[right];
    return '\0';
}

char getParent(char tree[], int i) {
    if (i == 1) return '\0';  // 根节点没有父节点
    return tree[i / 2];
}

顺序存储的优缺点很明显：

优点	缺点
内存连续，访问快	插入删除要移动大量数据
通过下标直接定位父子节点	非完全二叉树浪费空间
实现简单，代码量少	树的大小固定，不易扩展

二叉树的链式存储

链式存储才是真正灵活的方式。每个节点就是一个结构体，包含数据域和两个指针域。

// 二叉树的链式存储节点定义
typedef struct TreeNode {
    char data;                 // 数据域
    struct TreeNode *left;     // 左孩子指针
    struct TreeNode *right;    // 右孩子指针
} TreeNode;

// 创建一个新节点
TreeNode* createNode(char 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;
}

// 构建一棵简单的二叉树
//        A
//       / \
//      B   C
//     / \
//    D   E
TreeNode* buildTree() {
    TreeNode *root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');
    return root;
}

链式存储的好处是灵活，想加节点就加，想删就删。但每个节点多了两个指针的开销。在32位系统上，每个节点额外占8字节（两个指针），64位系统上就是16字节。

我个人习惯在嵌入式项目里这样选：

• 如果树的结构固定，不会频繁增删 → 用顺序存储
• 如果树经常变化，或者不是完全二叉树 → 用链式存储
• 如果内存极度紧张 → 优先考虑顺序存储

两种存储方式对比

对比项	顺序存储	链式存储
内存分配	静态数组，一次性分配	动态分配，按需申请
空间利用率	完全二叉树高，普通树低	较高，但有指针开销
访问速度	O(1) 通过下标	O(n) 需要遍历
插入/删除	需要移动数据	修改指针即可
适用场景	完全二叉树、堆	普通二叉树、搜索树

下面这张图展示了两种存储方式的核心区别，我画了很久才调好布局：

这张图左边是顺序存储，数组下标和节点一一对应。右边是链式存储，每个节点通过指针串联起来。你看，同样的树结构，两种存储方式差别很大。

最后说一句：二叉树的基础就这些，但它是后面所有高级树结构（二叉搜索树、平衡树、堆）的基石。把今天的内容吃透了，后面的路就好走了。

---

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