3. 二叉树的存储结构：顺序存储与链式存储

聊到二叉树的存储，我脑子里第一个蹦出来的问题就是：这棵树，到底该怎么放进内存里？

你想想看，树是一种非线性结构，每个节点可能有左孩子、右孩子，甚至还有父节点。而我们的内存，说白了就是一维的线性空间。把一棵立体的树塞进一条直线上，这事本身就挺有意思的。

实际开发中，我见过两种主流做法：顺序存储和链式存储。各有各的脾气，也各有各的坑。今天咱们就把它掰开揉碎了讲清楚。

3.1 顺序存储结构（数组实现）

顺序存储，说白了就是用数组来存二叉树。它的核心思想是：按照完全二叉树的编号规则，把节点依次放进数组里。

具体怎么放？规则很简单：

  • 根节点放在下标为 1 的位置（有些教材从0开始，但我个人习惯从1开始，这样公式更直观）
  • 对于下标为 i 的节点：
    • 左孩子下标：2 * i
    • 右孩子下标：2 * i + 1
    • 父节点下标：i / 2（整数除法）

举个例子，一棵这样的完全二叉树：

        1
       / \
      2   3
     / \   \
    4   5   7

用数组存储就是：

下标1234567
值12345空7

注意下标6是空的，因为节点3没有左孩子，但右孩子7占了下标7的位置。这就是顺序存储的一个特点——必须按完全二叉树来占位。

核心公式（记住这组公式，面试常考）：

  • 左孩子：2 * i
  • 右孩子：2 * i + 1
  • 父节点：i / 2
  • 判断叶子节点：2 * i > n（n为节点总数）

3.1.1 代码实现

下面是一个简单的顺序存储实现，我当年在嵌入式项目里就用过类似的写法：

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

#define MAX_SIZE 100

// 顺序存储的二叉树
typedef struct {
    int data[MAX_SIZE];  // 存储节点值
    int size;            // 当前节点数
} SeqBinaryTree;

// 初始化
void initTree(SeqBinaryTree *tree) {
    tree->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        tree->data[i] = -1;  // -1表示空节点
    }
}

// 插入根节点
void insertRoot(SeqBinaryTree *tree, int value) {
    if (tree->size == 0) {
        tree->data[1] = value;
        tree->size = 1;
    }
}

// 插入左孩子
void insertLeft(SeqBinaryTree *tree, int parent, int value) {
    int index = 2 * parent;
    if (index < MAX_SIZE && tree->data[index] == -1) {
        tree->data[index] = value;
        tree->size++;
    }
}

// 插入右孩子
void insertRight(SeqBinaryTree *tree, int parent, int value) {
    int index = 2 * parent + 1;
    if (index < MAX_SIZE && tree->data[index] == -1) {
        tree->data[index] = value;
        tree->size++;
    }
}

// 获取左孩子
int getLeft(SeqBinaryTree *tree, int index) {
    int left = 2 * index;
    if (left < MAX_SIZE && tree->data[left] != -1) {
        return tree->data[left];
    }
    return -1;
}

// 获取右孩子
int getRight(SeqBinaryTree *tree, int index) {
    int right = 2 * index + 1;
    if (right < MAX_SIZE && tree->data[right] != -1) {
        return tree->data[right];
    }
    return -1;
}

// 获取父节点
int getParent(SeqBinaryTree *tree, int index) {
    if (index > 1) {
        return tree->data[index / 2];
    }
    return -1;
}

我的经验：顺序存储最适合完全二叉树和满二叉树。如果树形很歪斜，比如只有右孩子，那数组里会空出大量位置，浪费空间。我曾经在一个堆排序项目里用过这种结构，因为堆本身就是完全二叉树，用数组存简直天作之合。

注意：顺序存储的数组大小是固定的。如果树在运行时会动态增长，你得提前预估最大节点数，否则会越界。我曾经在早期的一个项目中没注意这个问题，结果树长到一半数组满了……嗯，调试了一下午。

3.2 链式存储结构

链式存储，就是用指针把节点串起来。每个节点除了存数据，还存指向左右孩子的指针。这种方式更灵活，也更符合树的「天然形态」。

链式存储有两种常见形式：二叉链表和三叉链表。

3.2.1 二叉链表

二叉链表是最基础的链式存储。每个节点包含三个部分：

  • data：数据域
  • left：指向左孩子的指针
  • right：指向右孩子的指针

结构体定义如下：

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

这种结构，说白了就是每个节点只知道自己「往下」的路，不知道「往上」的路。想找父节点？你得从根节点重新遍历一遍。

我画了一张图，帮你直观理解二叉链表的连接方式：

根节点 data=1 左孩子 data=2 右孩子 data=3 左-左 data=4 左-右 data=5 右-左 data=6 右-右 data=7 left right left right left right 图：二叉链表结构示意图 —— 每个节点包含 data、left 指针、right 指针

3.2.2 三叉链表

三叉链表在二叉链表的基础上，多了一个指向父节点的指针。结构体长这样：

typedef struct TriTNode {
    int data;                    // 数据域
    struct TriTNode *left;       // 左孩子指针
    struct TriTNode *right;      // 右孩子指针
    struct TriTNode *parent;     // 父节点指针
} TriTNode, *TriTree;

多了这个 parent 指针，好处很明显：

  • 你可以从任意节点出发，向上回溯到根节点
  • 某些算法（比如求两个节点的最近公共祖先）会变得简单很多
  • 删除节点时，可以方便地更新父节点的孩子指针

但代价也很直接：每个节点多了一个指针，内存开销增加了。对于一棵有 n 个节点的树，三叉链表比二叉链表多占 n 个指针的空间。

两种链式存储的对比：

特性二叉链表三叉链表
每个节点指针数2 个3 个
能否找父节点不能（需遍历）能（直接访问）
内存开销较小较大
适用场景一般遍历、搜索需要频繁回溯父节点

3.2.3 二叉链表的常用操作

下面我写几个最常用的操作，都是我在实际项目中反复用到的：

// 创建新节点
BiTree createNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 前序遍历（根左右）
void preOrder(BiTree root) {
    if (root == NULL) return;
    printf("%d ", root->data);   // 访问根
    preOrder(root->left);        // 遍历左子树
    preOrder(root->right);       // 遍历右子树
}

// 中序遍历（左根右）
void inOrder(BiTree root) {
    if (root == NULL) return;
    inOrder(root->left);         // 遍历左子树
    printf("%d ", root->data);   // 访问根
    inOrder(root->right);        // 遍历右子树
}

// 后序遍历（左右根）
void postOrder(BiTree root) {
    if (root == NULL) return;
    postOrder(root->left);       // 遍历左子树
    postOrder(root->right);      // 遍历右子树
    printf("%d ", root->data);   // 访问根
}

// 求树的高度
int treeHeight(BiTree root) {
    if (root == NULL) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 求节点个数
int treeSize(BiTree root) {
    if (root == NULL) return 0;
    return treeSize(root->left) + treeSize(root->right) + 1;
}

我的建议：如果你刚开始学二叉树，先用二叉链表。它结构简单，代码好写，也足够应付大部分场景。等遇到需要频繁找父节点的需求时，再考虑升级到三叉链表。别一开始就上三叉链表，容易把自己绕晕。

3.3 三种存储结构的对比总结

好了，三种存储方式都讲完了。我帮你总结一下，方便你以后选型时参考：

存储方式优点缺点适用场景
顺序存储（数组） 访问快，O(1) 定位节点；内存连续，缓存友好 空间浪费（非完全二叉树）；大小固定，不易扩展 完全二叉树、堆、线段树
二叉链表 结构灵活，空间利用率高；动态扩展方便 无法直接找父节点；每个节点有指针开销 一般二叉树、表达式树、搜索树
三叉链表 可快速回溯父节点；删除节点方便 内存开销更大；代码复杂度略高 需要频繁回溯父节点的场景

我个人在实际项目中，用得最多的是二叉链表。它就像一把瑞士军刀，够用、灵活、不花哨。顺序存储我只在堆排序和线段树里用过，因为那两种场景下树本身就是完全二叉树，用数组存简直是天作之合。三叉链表嘛，说实话用得不多，但有一次在做表达式求值的时候，需要从叶子节点回溯到根，三叉链表帮了大忙。

嗯，存储结构就聊到这儿。记住一句话：没有最好的结构，只有最合适的结构。选哪种，取决于你的树长什么样，以及你要对它做什么操作。

← 上一章 📖 返回目录 下一章 →