树与二叉树基础：从现实到代码的桥梁

说实话，每次讲到树结构，我都会想起刚入行时的一个项目。那时候我负责一个文件系统的索引模块，用数组硬生生地存层级关系，结果查找一个文件要遍历整个数组，性能惨不忍睹。后来一位老前辈看了一眼代码，说：「小伙子，你该用树。」嗯，从那以后，我才真正开始理解树的价值。

树这种结构，说白了就是「一对多」的关系。你想想看，公司的组织架构、电脑里的文件夹、甚至你家的族谱，都是活生生的树。今天我们就从最基础的东西聊起，把树的定义、术语、二叉树的形态，以及怎么在内存里存它，一次性讲清楚。

树的定义与基本术语

树是 n（n≥0）个结点的有限集合。n=0 时叫空树，这没什么好说的。n>0 时，有且只有一个根结点，其余结点可以分成 m 个互不相交的子树。

这里有几个术语，我建议你死记硬背下来，因为后面所有操作都离不开它们：

  • 根（Root）：唯一没有前驱的结点。就像公司的CEO，上面没人了。
  • 叶子（Leaf）：度为0的结点，也就是没有孩子的结点。像基层员工，下面没人了。
  • 度（Degree）：一个结点拥有的子树个数。比如一个经理管3个人，他的度就是3。
  • 深度（Depth）：从根到该结点的唯一路径上的边数。根深度为0，它的孩子深度为1，以此类推。
  • 森林（Forest）：m 棵互不相交的树的集合。把根砍掉，剩下的子树就是森林。

我个人习惯：在定义结构体时，我会把「度」这个字段也带上。虽然大多数教材不这么做，但我在调试时能快速判断结点是否异常，省了不少事。

二叉树的五种基本形态

二叉树是树里最特殊也最常用的一种。每个结点最多有两个孩子，分别叫左孩子和右孩子。注意，是「最多两个」，不是必须两个。

二叉树的五种基本形态，我画个图你就明白了：

① 空二叉树 没有结点 ② 只有根 A ③ 只有左子树 A B ④ 只有右子树 A B ⑤ 左右子树都有 A B C

这五种形态，你写代码时都会遇到。尤其是第三种和第四种，很多初学者容易搞混——左子树为空不等于没有左孩子，只是左孩子指针指向 NULL 而已。

满二叉树与完全二叉树

这两个概念，面试时经常被问到。我简单说说区别：

  • 满二叉树：每一层的结点数都达到最大值。深度为 k 的满二叉树，结点总数是 2^(k+1) - 1。说白了就是「一个萝卜一个坑，每个坑都填满了」。
  • 完全二叉树：除了最后一层，其他层都是满的。最后一层的结点必须从左到右连续排列，中间不能有空位。

我曾经踩过一个坑：在实现堆排序时，我把完全二叉树和满二叉树搞混了。满二叉树一定是完全二叉树，但反过来不一定成立。堆排序用的是完全二叉树，不是满二叉树。那次调试了整整一个下午，才发现是初始化时多分配了结点。

这里有个实用技巧：完全二叉树可以用数组来存，而且父子关系可以通过下标直接计算。这个特性太重要了，堆、优先队列都靠它。

二叉树的顺序存储

顺序存储，就是用数组来存二叉树。对于完全二叉树，这是最省空间的方式。

假设数组下标从 0 开始，那么：

  • 下标为 i 的结点，左孩子下标为 2*i + 1
  • 右孩子下标为 2*i + 2
  • 父结点下标为 (i-1)/2（整数除法）
// 顺序存储示例：用数组表示完全二叉树
#define MAX_TREE_SIZE 100

typedef struct {
    int data[MAX_TREE_SIZE];  // 存储结点值
    int last;                 // 最后一个结点的下标
} SeqBinaryTree;

// 初始化
void initTree(SeqBinaryTree *tree) {
    tree->last = -1;
}

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

// 获取左孩子
int leftChild(int index) {
    int child = 2 * index + 1;
    return child;  // 调用者需判断是否越界
}

我个人习惯：在顺序存储中，我会预留一个哨兵位（下标0不用，从1开始存）。这样父子关系变成：左孩子 2*i，右孩子 2*i+1，父结点 i/2。虽然浪费了一个元素，但代码更直观，尤其在堆排序中。

顺序存储的缺点也很明显：如果树不是完全二叉树，会有大量空间浪费。比如一个深度为 4 的右斜树，需要 2^4 - 1 = 15 个数组元素，但实际只存了 4 个结点。这种场景下，链式存储更合适。

二叉树的链式存储

链式存储是更通用的方式。每个结点包含三部分：数据域、左孩子指针、右孩子指针。

// 链式存储结构定义
typedef struct BTNode {
    int data;                 // 数据域
    struct BTNode *left;      // 左孩子指针
    struct BTNode *right;     // 右孩子指针
} BTNode, *BTree;

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

// 构建一个简单的二叉树
//      A
//     / \
//    B   C
//   /
//  D
BTree buildSampleTree() {
    BTNode *root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    return root;
}

链式存储的好处是灵活，任意形态的二叉树都能存，而且插入删除操作只需要改指针，时间复杂度 O(1)。但缺点也很明显：每个结点多存了两个指针，空间开销大。对于 n 个结点的二叉树，有 n+1 个空指针域（这个结论你可以自己推导一下）。

这里有个实用经验：我在嵌入式项目中，如果内存紧张，会用「孩子兄弟表示法」来压缩存储。把多叉树转成二叉树，每个结点只存第一个孩子和下一个兄弟，这样指针域从 m 个降到了 2 个。虽然操作复杂了点，但内存省了一半以上。

两种存储方式的选择

对比项 顺序存储 链式存储
空间利用率 完全二叉树高，非完全二叉树低 始终较高，但有指针开销
随机访问 O(1)，通过下标直接访问 O(n)，需要遍历
插入/删除 O(n)，需要移动大量元素 O(1)，改指针即可
适用场景 堆、优先队列、完全二叉树 一般二叉树、动态变化的结构

你想想看，如果你要实现一个堆排序，用顺序存储就对了。但如果你要做一个表达式树解析器，结点随时增删，那链式存储才是正道。

好了，树的基础就聊到这里。记住一句话：树是递归定义的，所以大部分树的操作都可以用递归来实现。后面我们会深入遍历、线索化、哈夫曼树等内容，到时候你会发现，今天打下的基础会反复用到。

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

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