15. 二叉树的存储结构：顺序存储结构、链式存储结构、二叉树的建立

二叉树这东西，说白了就是每个节点最多有两个孩子。但怎么把它存到计算机里，却是个值得琢磨的问题。我早年做嵌入式开发时，内存就那么几KB，选错存储结构，程序直接跑不起来。今天咱们就把两种存储方式掰开揉碎了讲清楚。

15.1 顺序存储结构

顺序存储，就是用数组来存二叉树。听起来简单，但有个前提——你得知道节点之间的父子关系怎么映射到数组下标上。

规则其实就一句话：对于完全二叉树，根节点放在下标1（或0），那么左孩子就是 2i，右孩子就是 2i+1。嗯，这里要注意，如果数组从0开始，公式要微调一下。

我在项目中遇到过一种情况：用顺序存储存一棵满二叉树，效率极高。因为节点连续排列，CPU缓存命中率特别好。但如果是普通二叉树，尤其是那种斜树，那就惨了——数组里会空出大量位置，浪费空间。

顺序存储的代码实现其实很简单：

// 顺序存储结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType;

typedef struct {
    TElemType data[MAX_TREE_SIZE];  // 从下标1开始存储
    int nodeCount;                  // 实际节点数
} SeqBinaryTree;

// 初始化
void InitSeqTree(SeqBinaryTree *T) {
    T->nodeCount = 0;
    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        T->data[i] = 0;  // 0表示空节点
    }
}

// 插入根节点
void InsertRoot(SeqBinaryTree *T, TElemType val) {
    if (T->nodeCount == 0) {
        T->data[1] = val;
        T->nodeCount = 1;
    }
}

// 插入左孩子
void InsertLeft(SeqBinaryTree *T, int parentIdx, TElemType val) {
    int leftIdx = 2 * parentIdx;
    if (leftIdx < MAX_TREE_SIZE) {
        T->data[leftIdx] = val;
        T->nodeCount++;
    }
}

15.2 链式存储结构

链式存储就灵活多了。每个节点除了存数据，还要存两个指针——左孩子和右孩子。你想想看，这不就是双向链表的思想吗？只不过链表是前后指针，二叉树是左右指针。

我个人习惯用这种结构，因为99%的实际场景都是普通二叉树，链式存储既不浪费空间，插入删除也方便。

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

// 创建节点
BiTree CreateNode(TElemType val) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));
    if (node) {
        node->data = val;
        node->lchild = NULL;
        node->rchild = NULL;
    }
    return node;
}

15.3 两种存储结构的对比

对比维度	顺序存储	链式存储
空间利用率	完全二叉树高，普通二叉树低	始终较高，每个节点多两个指针开销
访问速度	随机访问O(1)，缓存友好	需要指针跳转，缓存不友好
插入/删除	需要移动大量元素	修改指针即可，O(1)
适用场景	堆、完全二叉树	普通二叉树、动态变化场景

说白了，没有绝对的好坏。我建议你根据实际需求来选：如果树的结构固定且接近完全二叉树，用顺序存储；如果树经常变化，或者形状不规则，用链式存储。

15.4 二叉树的建立

建立二叉树，最经典的方式就是递归建树。你想想看，二叉树本身就是递归定义的——左子树是一棵树，右子树也是一棵树。那建树自然也可以用递归。

我常用的方法是：先序遍历序列 + 空节点标记。比如用'#'表示空节点，那么序列 "AB#D##C##" 就能唯一确定一棵二叉树。

// 根据先序遍历序列建立二叉树（'#'表示空节点）
BiTree CreateByPreOrder() {
    char ch;
    scanf("%c", &ch);  // 读取一个字符
    
    if (ch == '#') {
        return NULL;  // 空节点
    }
    
    // 创建当前节点
    BiTree node = CreateNode(ch);
    
    // 递归建立左子树和右子树
    node->lchild = CreateByPreOrder();
    node->rchild = CreateByPreOrder();
    
    return node;
}

// 使用示例：输入 AB#D##C##
// 得到的树结构：
//     A
//    / \
//   B   C
//    \
//     D

除了先序建树，还有层序建树的方式。说白了就是用队列，一层一层地建。这种方式更符合人的直觉，但代码稍微复杂一点。

// 根据层序序列建立二叉树（-1表示空节点）
BiTree CreateByLevel(int arr[], int n) {
    if (n == 0 || arr[0] == -1) return NULL;
    
    // 创建根节点
    BiTree root = CreateNode(arr[0]);
    
    // 用队列辅助层序建树
    Queue Q;
    InitQueue(&Q);
    EnQueue(&Q, root);
    
    int i = 1;
    while (!IsEmpty(Q) && i < n) {
        BiTree cur = DeQueue(&Q);
        
        // 处理左孩子
        if (i < n && arr[i] != -1) {
            cur->lchild = CreateNode(arr[i]);
            EnQueue(&Q, cur->lchild);
        }
        i++;
        
        // 处理右孩子
        if (i < n && arr[i] != -1) {
            cur->rchild = CreateNode(arr[i]);
            EnQueue(&Q, cur->rchild);
        }
        i++;
    }
    
    return root;
}

我曾经在做一个文件目录树解析时，就用层序建树。因为输入数据是按层级给的，用层序建树天然匹配，代码写起来一气呵成。

15.5 知识体系总览

下面这张图把本章的核心逻辑串起来了，你看一眼就能明白：

嗯，到这里二叉树的存储和建立就讲完了。两种方式各有千秋，关键看你的应用场景。我个人更偏爱链式存储，因为它灵活，而且递归建树的代码写起来特别优雅。但如果你在做堆排序或者优先队列，顺序存储绝对是首选。

---

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