数据结构：二叉树的表示方式（Representation of Binary Trees）

目录

链式表示法 (Linked Representation)

步骤1：定义“节点”这个基本单元

步骤2：创建节点并建立连接

步骤3：封装成函数（代码的演进）

数组表示法 (Array / Sequential Representation)

步骤1：发现规律

步骤2：用数组存储

步骤3：处理非完全二叉树

最终结论：如何选择？

我们正式进入实践环节。知道了树的理论概念后，下一步就是思考：如何在计算机的内存中把这个抽象的“树”结构给搭建出来？

计算机内存本质上是线性的，像一条长长的街道，每个位置都有一个地址。而树是非线性的、分叉的结构。

所以，我们面临的核心问题是：如何用线性的内存来表达非线性的树状关系？

从第一性原理出发，我们有两种根本不同的方法来解决这个问题。

链式表示法 (Linked Representation)

第一性原理: 抓住树最核心的关系——“连接”。一个父节点“连接”到它的子节点。

在C/C++中，什么工具最擅长表示这种“指向”或“连接”的关系，尤其当被连接的对象在内存中位置不固定时？

答案是 指针 (Pointer)。

这种方法是最直观、最符合树的逻辑定义的。

步骤1：定义“节点”这个基本单元

我们首先需要设计一个“零件”。这个零件，也就是树的节点，需要包含什么信息？

1. 它自身存储的数据 (Data)。

2. 一个指向其左孩子的“连接”。

3. 一个指向其右孩子的“连接”。

好了，让我们把这个设计草图翻译成C/C++代码。

// 步骤 1: 定义一个树节点的结构体
// 这是我们构建一棵树所需的最基本的“砖块”
struct TreeNode {
    int data;         // 1. 用于存储节点自身的数据，这里以整数为例

    TreeNode* left;   // 2. 一个指针，用于“指向”左孩子节点
    TreeNode* right;  // 3. 一个指针，用于“指向”右孩子节点
};

代码解读:

• TreeNode* left; 这一行是精髓。它定义了一个名为 left 的成员，它的类型是 TreeNode*，即“指向TreeNode结构体的指针”。它可以存储另一个TreeNode结构体的内存地址。

• 如果一个节点没有左孩子或右孩子怎么办？很简单，让对应的指针指向一个特殊的地方，即 NULL (或在C++11及以后版本中用 nullptr)。这就像一条路的尽头，告诉我们“这里没路了”。

步骤2：创建节点并建立连接

现在我们有了“砖块”，怎么把它们砌成一棵小树呢？比如，我们要创建下面这棵树：

    10 (根)
   /  \
  20  30

我们不能只在函数里简单地创建变量 TreeNode node;，因为这样的变量在函数结束后就会被销毁。

我们需要在一种叫做“堆 (Heap)”的内存区域里创建节点，这样它们才能一直存在，直到我们手动释放。在C++里我们用 new，在C里用 malloc。

 root
  ↓
+-------+-------------+--------------+
|  A    | left:ptrB   | right:ptrC   |
+-------+-------------+--------------+
    ↓                       ↓
+-------+-------------+--------------+
|  B    |   NULL      |    NULL      |
+-------+-------------+--------------+

+-------+-------------+--------------+
|  C    |   NULL      |    NULL      |
+-------+-------------+--------------+

// 步骤 2: 尝试创建并连接节点

// 首先，创建根节点。它现在是孤立的。
TreeNode* root = new TreeNode; // 在堆内存中申请一个TreeNode的空间
root->data = 10;
// 重要！新创建的节点，它的孩子指针是未初始化的，必须手动设为NULL
root->left = NULL;
root->right = NULL;

// 然后，创建它的左孩子，它目前也是孤立的
TreeNode* leftChild = new TreeNode;
leftChild->data = 20;
leftChild->left = NULL;
leftChild->right = NULL;

// 创建右孩子
TreeNode* rightChild = new TreeNode;
rightChild->data = 30;
rightChild->left = NULL;
rightChild->right = NULL;

// 最后，建立“连接”
root->left = leftChild;   // 将root节点的left指针指向leftChild节点的地址
root->right = rightChild; // 将root节点的right指针指向rightChild节点的地址

root->left = leftChild; 这一步是连接的关键。它把 leftChild 这个指针变量里存储的内存地址，复制到了 root 所指向的那个结构体的 left 成员里。从此，通过 root 就可以找到它的孩子们了。

步骤3：封装成函数（代码的演进）

手动创建和连接非常繁琐且容易出错。一个好的实践是把“创建并初始化节点”这个重复性工作封装成一个函数。

// 步骤 3: 将节点创建过程封装成一个辅助函数
#include <iostream> // 引入用于输出

// (这里是步骤1定义的TreeNode结构体)
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

// 辅助函数：传入一个值，返回一个创建好的、指向新节点的指针
TreeNode* createNode(int value) {
    TreeNode* newNode = new TreeNode; // 申请内存
    newNode->data = value;            // 设置数据
    newNode->left = NULL;             // 初始化左右孩子为NULL
    newNode->right = NULL;
    return newNode;                   // 返回新节点的地址
}

// 最终的、更简洁的建树代码
int main() {
    // 使用辅助函数，代码变得清晰多了
    TreeNode* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);

    // 我们可以验证一下连接是否成功
    std::cout << "根节点的值: " << root->data << std::endl;
    std::cout << "左孩子的值: " << root->left->data << std::endl;
    std::cout << "右孩子的值: " << root->right->data << std::endl;

    // TODO: 释放内存 (暂时省略，但实际项目中非常重要)
    return 0;
}

链式表示法总结

• 优点:

  • 灵活: 插入、删除节点非常方便，只需改变指针即可，不需要移动大量数据。

  • 空间: 大小不受限制，只要内存足够，理论上可以无限增长。

• 缺点:

  • 空间开销: 每个节点都需要额外的空间来存储左、右两个指针。

  • 访问效率: 节点在内存中可能是分散的，不连续，这可能导致CPU缓存命中率降低。

  • 寻父困难: 从一个子节点出发，无法直接找到其父节点（除非我们在结构体中再增加一个parent指针）。

数组表示法 (Array / Sequential Representation)

第一性原理: 能否不用指针，而是通过数学计算来找到父子关系？

如果我能把树的节点整齐地排放在一个数组里，并且能通过一个节点的数组下标 i，直接算出它孩子的下标和父亲的下标，那就不需要指针了。

这种想法要成为现实，需要一个前提：树的结构必须非常有规律，不能有“空隙”。

哪种树最符合这个要求？完全二叉树 (Complete Binary Tree)。

步骤1：发现规律

让我们画一棵完全二叉树，并把它的节点按层序（从上到下，从左到右）在数组中编号，从下标 0 开始。

        节点值: A         数组下标: 0
       /     \
      B       C         数组下标: 1, 2
     / \     / \
    D   E   F   G       数组下标: 3, 4, 5, 6

我们来寻找下标之间的数学关系：

• 找孩子:

  • 节点0 (A) 的孩子是 1 (B) 和 2 (C)。 1 = 2*0 + 1, 2 = 2*0 + 2。

  • 节点1 (B) 的孩子是 3 (D) 和 4 (E)。 3 = 2*1 + 1, 4 = 2*1 + 2。

  • 节点2 (C) 的孩子是 5 (F) 和 6 (G)。 5 = 2*2 + 1, 6 = 2*2 + 2。

• 规律: 对于任意下标为 i 的节点：

  • 其左孩子的下标是 2*i + 1。

  • 其右孩子的下标是 2*i + 2。

• 找父亲:

  • 节点1 (B) 和 2 (C) 的父亲是 0 (A)。 (1-1)/2 = 0, (2-1)/2 = 0 (整数除法)。

  • 节点3 (D) 和 4 (E) 的父亲是 1 (B)。 (3-1)/2 = 1, (4-1)/2 = 1。

• 规律: 对于任意下标为 i (且i>0) 的节点：

  • 其父节点的下标是 (i-1) / 2。

+----+----+----+----+----+----+----+
| A  | B  | C  | D  | E  | F  | G  |
+----+----+----+----+----+----+----+
 0    1    2    3    4    5    6   ← 数组索引

步骤2：用数组存储

有了这些雷打不动的公式，我们就可以用一个简单的数组来表示一棵（完全）二叉树了。

// 步骤 2: 将树 {10, 20, 30} 存入数组
// 10是根，在下标0
// 20是10的左孩子，在下标 2*0+1 = 1
// 30是10的右孩子，在下标 2*0+2 = 2
int treeArray[100] = {10, 20, 30}; // 假设数组足够大
int treeSize = 3;

// 演示如何通过计算来遍历
int root_idx = 0;
std::cout << "根节点的值: " << treeArray[root_idx] << std::endl;

// 检查左孩子是否存在并访问
int left_child_idx = 2 * root_idx + 1;
if (left_child_idx < treeSize) {
    std::cout << "左孩子的值: " << treeArray[left_child_idx] << std::endl;
}

// 检查右孩子是否存在并访问
int right_child_idx = 2 * root_idx + 2;
if (right_child_idx < treeSize) {
    std::cout << "右孩子的值: " << treeArray[right_child_idx] << std::endl;
}

步骤3：处理非完全二叉树

如果树不是完全二叉树怎么办？比如，节点10只有右孩子30。

    10
      \
       30

• 原理:  我们必须维护公式的正确性。节点10（下标0）的左孩子（下标1）虽然不存在，但它的“位置”必须被占住，否则公式就乱了。

• 解决方案:  用一个特殊值（哨兵值），比如 -1，来表示这个位置是空的。

        A
       / \
      B   C
     /
    D

数组：[A, B, C, D, -1, -1, -1]

// 步骤 3: 存储一个非完全二叉树
// 树: 10(根), 右孩子30.
// 数组表示:
// 下标0: 10
// 下标1 (10的左孩子): 空，用-1表示
// 下标2 (10的右孩子): 30
int treeArray[100] = {10, -1, 30};
int treeSize = 3;

数组表示法总结

• 优点:

  • 节约空间: 不需要存储指针，对于满二叉树或完全二叉树，空间利用率极高。

  • 访问高效: 节点在内存中是连续的，CPU缓存友好。找父亲的操作极其简单快速 (O(1))。

• 缺点:

  • 空间浪费: 对于非完全二叉树，特别是“又高又瘦”的树，会浪费大量数组空间来存储 -1。一个只有n个节点的右斜树可能需要 2n 大小的数组！

  • 不灵活: 增删节点可能需要移动大量元素，或者导致数组需要重新分配、拷贝，开销很大。

最终结论：如何选择？

两种表示方法，源于我们解决“用线性内存表达非线性结构”这个核心矛盾的两种不同思路。

• 链式法: “既然内存地址不连续，我就用指针把它们连接起来”，忠实于逻辑结构。

• 数组法: “我不管逻辑结构，我强行定义一套数学规则，把所有节点映射到连续的数组下标上”，忠实于物理存储。

在绝大多数应用场景中，链式表示法因其灵活性而成为首选。

而数组表示法，则在像“堆排序”这样需要频繁寻找父节点且能保证树总是完全二叉树的特定算法中，大放异彩。