树与二叉树：核心结构、性质及存储方式详解

这种表示法的妙处在于，通过 firstChild 和 pNextBrother 两个指针，就能遍历整棵树的所有分支，无需复杂的数组管理。

3. 实际应用

树在实际中最典型的应用就是文件系统的目录树结构，层级分明，便于管理和检索。

二、二叉树的概念与结构

简单理解，二叉树就是每个结点最多只有两个'叉'的树。

1. 基本概念

二叉树是结点的有限集合，满足以下两种情况之一：

1. 为空集。
2. 由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。

关键点：

• 二叉树不存在度大于 2 的结点。
• 子树有左右之分，次序不能颠倒，因此是有序树。

2. 现实中的二叉树

二叉树在现实中随处可见，比如决策树模型、表达式树等。

3. 特殊二叉树

• 满二叉树：每一层的结点数都达到最大值。若层数为 K，结点总数为 $2^K - 1$。
• 完全二叉树：效率很高。对于深度为 K 且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。注意，满二叉树是一种特殊的完全二叉树。

4. 性质与证明

掌握这些性质对计算空间复杂度至关重要：

1. 第 h 层结点数：若规定根结点层数为 1，则第 h 层最多有 $2^{(h-1)}$ 个结点。
2. 最大结点数：深度为 h 的二叉树最大结点数为 $2^h - 1$。
3. 叶子与度为 2 的关系：对任何二叉树，若度为 0 的叶结点数为 $n_0$，度为 2 的分支结点数为 $n_2$，则有 $n_0 = n_2 + 1$。
   • 证明思路：可用假设法。单节点时 $n_0=1, n_2=0$ 成立。增加度为 1 的点不改变 $n_0-n_2$ 差值；增加度为 2 的点，$n_0$ 增 1，$n_2$ 增 1，差值仍不变。故恒成立。
4. 满二叉树深度：具有 n 个结点的满二叉树，深度 $h = \log_2(n+1)$。
5. 完全二叉树编号规律：若按从上至下、从左至右顺序从 0 开始编号，对序号 i 的结点：
   • 双亲序号：$(i-1)/2$（整数除法，无需分奇偶讨论）。
   • 左孩子序号：$2i+1$（若 $<n$）。
   • 右孩子序号：$2i+2$（若 $<n$）。

三、二叉树的存储结构

与其他数据结构类似，二叉树主要有两种存储方式。

1. 顺序存储

使用数组存储。一般只适合表示完全二叉树，因为非完全二叉树会有大量空间浪费。实际应用中，堆（Heap）常使用数组存储。二叉树顺序存储在物理上是数组，逻辑上是树。

2. 链式存储

用链表表示二叉树，每个结点包含数据域和左右指针域。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode {
    struct BinaryTreeNode* left;   // 左孩子
    struct BinaryTreeNode* right;  // 右孩子
    BTDataType data;               // 数据域
};

// 三叉链（带父指针）
struct BinaryTreeNode {
    struct BinaryTreeNode* parent; // 父结点
    struct BinaryTreeNode* left;   // 左孩子
    struct BinaryTreeNode* right;  // 右孩子
    BTDataType data;               // 数据域
};

顺序存储和链式存储各有优劣，具体选择需根据应用场景权衡。后续文章会针对具体实现做更深入的讲解。

四、总结

理解树与二叉树的基本概念是学习 AVL 树、红黑树、B 树等高级结构的基础，也是掌握霍夫曼编码、决策树等算法的前提。建议结合代码实践，加深对这些抽象结构的理解。