CC++ & Algorithm

树的构造与存储

较难24
语言版本：C++Python(暂无)
概述：用C++的指针和结构体把树“搭”出来，就像用积木拼成一个分形图案。

好，我们来一起把“树的构造与存储”写成一篇更适合中小学生阅读的文章。我会保留原文的正确内容，并补充更多生活中的比喻、分步讲解、常见错误和完整示例，让每个概念都像搭积木一样简单。

树的构造与存储：像搭积木一样建一棵树

在前面，我们已经知道了树是一种“父子”关系的数据结构，就像一个家族的族谱，或者学校里的年级班级结构。那么，我们能不能在电脑里也造出一棵树来呢？当然可以！在C++里，我们就像用积木搭模型：先有一个“根积木”（根节点），然后往它下面插上“子积木”（子节点），一层一层堆叠起来。最直观的方法是用结构体定义节点，用指针将节点串成链。

一、我们需要什么“积木”？——定义节点结构体

每一个树节点可以看作一个小盒子，盒子里装着：

  • 数据：比如数字、名字、分数等。
  • 通往子节点的指针：就像盒子上的挂钩，可以挂上其他小盒子。

对于一棵普通的树（多叉树），一个节点可以有多个孩子，所以我们用C++的vector（可变数组）来存放所有子节点的指针。如果是二叉树（每个节点最多两个孩子），我们可以更简单：直接定义左孩子和右孩子两个指针。

生活中的例子：想象你在画一个家族树。爷爷（根节点）有两个孩子：爸爸和姑姑。每个孩子又可以有他们的孩子。每个“人”就是一个节点，记录姓名（数据），以及指向孩子（指针）。在电脑里，我们就是通过指针把这些人连起来。

二、两种常见的“搭积木”方式

  1. 链式存储（用指针）：每个节点用new动态创建，然后通过指针“挂”到父节点上。最灵活，也最符合树的自然结构。
  2. 数组存储（静态模拟）：用数组下标来模拟父子关系。比如节点编号1是根，它的左孩子编号2，右孩子编号3……适合存储完全二叉树（比如堆排序），但写起来不如指针直观。

对于初学者，我们先掌握链式存储，就像用手搭积木，每一步都能看得很清楚。

三、一步步造一棵树

假设我们要建造下面这棵二叉树：

        1（根）
       / \
      2   3
     /
    4

步骤：

  1. 定义节点结构体（准备积木的图纸）。
  2. 创建根节点：用new从内存里要出一块空间，放好数据，把左右孩子指针设为nullptr（空）。
  3. 创建子节点并挂接：比如给根节点挂上左孩子（值为2）和右孩子（值为3）。
  4. 继续挂接：给节点2挂上左孩子（值为4）。
  5. 检查：通过指针访问每个节点的数据，确认树搭对了。

下面就是具体的代码。我们用BinaryTreeNode结构体，里面包含一个整数data，以及指向左孩子的指针left和指向右孩子的指针right。

#include <iostream>
#include <vector>   // 多叉树时用vector存孩子，但这里是二叉树
using namespace std;

// 二叉树节点结构体
struct BinaryTreeNode {
    int data;                    // 节点中存放的数据（比如数字）
    BinaryTreeNode* left;        // 指向左孩子的指针
    BinaryTreeNode* right;       // 指向右孩子的指针
};

// 辅助函数：创建一个新节点，并初始化数据和孩子指针
BinaryTreeNode* createNode(int value) {
    BinaryTreeNode* newNode = new BinaryTreeNode;   // 从内存申请一个节点空间
    newNode->data = value;                           // 放入数据
    newNode->left = nullptr;                         // 左孩子先设成空
    newNode->right = nullptr;                        // 右孩子先设成空
    return newNode;                                  // 返回新节点的地址
}

int main() {
    // 开始搭积木：先搭根节点1
    BinaryTreeNode* root = createNode(1);        // 根节点，数据为1
    
    // 给根节点挂上左孩子2和右孩子3
    root->left = createNode(2);                   // 左孩子，数据为2
    root->right = createNode(3);                  // 右孩子，数据为3
    
    // 再给节点2挂上左孩子4
    root->left->left = createNode(4);             // 节点2的左孩子，数据为4
    
    // 现在树已经建好，我们可以通过指针一路访问
    cout << "根节点: " << root->data << endl;                  // 输出1
    cout << "左子: " << root->left->data << endl;              // 输出2
    cout << "右子: " << root->right->data << endl;             // 输出3
    cout << "左子的左子: " << root->left->left->data << endl;  // 输出4
    
    // 重要：用new申请的内存，用完要归还（释放）
    // 这里我们暂时不写释放代码，但实际程序中应该delete每个节点
    return 0;
}

运行结果：

根节点: 1
左子: 2
右子: 3
左子的左子: 4

四、新手最容易犯的错（一定要看！）

  1. 忘记初始化指针：定义结构体后，如果不用nullptr初始化，指针可能指向一个乱七八糟的地址，访问时会直接崩溃。所以每次创建节点，一定要把left和right设为nullptr。

  2. 访问空指针：比如我只给根节点挂了左孩子，却去访问root->right->data，而root->right是nullptr，程序会报“段错误”。访问前先判断是不是空指针。

  3. 忘记释放内存：用new创造节点后，程序结束时如果没有用delete释放，就会造成内存泄漏。虽然程序结束会自动回收，但长期运行的程序（比如服务器）会慢慢吃掉内存。正确的做法：写一个递归函数freeTree，从根开始依次删除每个节点。

    void freeTree(BinaryTreeNode* node) {
    if (node == nullptr) return;
    freeTree(node->left);   // 先删除左子树
    freeTree(node->right);  // 再删除右子树
    delete node;            // 最后删除自己
}

    在main函数末尾调用freeTree(root);。

  4. 混淆二叉树和多叉树：二叉树用left和right，多叉树要用vector<BinaryTreeNode*> children。如果用二叉树的结构去存多叉树，就会漏掉孩子。

五、完整可运行的代码（含释放内存）

下面是一份更完整的代码，包含了创建、输出和释放树的过程。我们把输出放在一个简单的printTree函数里（先序遍历），方便你看到整棵树的结构。

#include <iostream>
using namespace std;

// 二叉树节点结构体
struct BinaryTreeNode {
    int data;                    // 存放数据
    BinaryTreeNode* left;        // 左孩子指针
    BinaryTreeNode* right;       // 右孩子指针
};

// 创建新节点
BinaryTreeNode* createNode(int value) {
    BinaryTreeNode* newNode = new BinaryTreeNode; // 申请内存
    newNode->data = value;                        // 赋值
    newNode->left = nullptr;                      // 左孩子初始为空
    newNode->right = nullptr;                     // 右孩子初始为空
    return newNode;
}

// 递归释放整个树（后序遍历）
void freeTree(BinaryTreeNode* node) {
    if (node == nullptr) return;
    freeTree(node->left);   // 先释放左子树
    freeTree(node->right);  // 再释放右子树
    delete node;            // 最后释放自己
}

// 先序遍历打印树（根、左、右）
void printTree(BinaryTreeNode* node) {
    if (node == nullptr) return;
    cout << node->data << " ";           // 打印当前节点
    printTree(node->left);               // 递归打印左子树
    printTree(node->right);              // 递归打印右子树
}

int main() {
    // 构造一棵树：
    //       1
    //      / \
    //     2   3
    //    /
    //   4
    BinaryTreeNode* root = createNode(1);       // 根节点
    root->left = createNode(2);                 // 左孩子
    root->right = createNode(3);                // 右孩子
    root->left->left = createNode(4);           // 左孩子的左孩子

    cout << "树的先序遍历结果: ";
    printTree(root);                            // 输出: 1 2 4 3
    cout << endl;

    // 释放所有节点内存，防止内存泄漏
    freeTree(root);
    root = nullptr;  // 避免野指针

    return 0;
}

运行结果：

树的先序遍历结果: 1 2 4 3

六、树建好了，接下来做什么？

树造出来后，我们可以在上面玩很多花样：

  • 遍历：按不同顺序访问每个节点（前序、中序、后序、层序）。
  • 查找：看某个数在不在树里。
  • 求深度：树有多少层？叶子节点在哪里？
  • 修改：给某个节点换个值，或者插入新节点。
  • 二叉搜索树：让左孩子小于根，右孩子大于根，就能像查字典一样快速找到数据。

如果你已经学会了怎么造一棵树，下一步可以试试用vector来存多叉树，比如一个“文件夹系统”：根目录下有若干子文件夹，每个文件夹里又有文件。或者试试用数组存二叉树，常用于堆（优先队列）。这些都会让树的世界更加丰富。

相关知识点指引：

记住：造树就像搭积木，先有节点，再有指针连接。动手多写几遍，你就会发现树其实很有趣！

例题精讲

1单选题

在C++中，使用结构体定义二叉树节点时，以下哪种定义是正确的？

Astruct Node { int data; Node left; Node right; };
Bstruct Node { int data; Node* left; Node* right; };
Cstruct Node { int data; struct Node left; struct Node right; };
Dstruct Node { int data; *left; *right; };
2单选题

下列代码中，函数 buildTree 的功能是什么？假设输入数组 pre 和 in 分别表示前序和中序遍历序列。

A根据前序和后序遍历重建二叉树
B根据前序和中序遍历重建二叉树
C根据中序和后序遍历重建二叉树
D根据层次遍历和前序遍历重建二叉树
3判断题

用指针和结构体存储一棵有n个节点的树，每个节点只包含一个数据域和指向子节点的指针，则该树占用的内存空间（不考虑对齐）一定大于用数组方式（如父亲数组）存储同一棵树所需的空间。

4填空题
以下函数实现二叉树的前序遍历（递归），请补全代码。
void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    ___(1)___;
    ___(2)___;
}
5填空题
下面是创建一个二叉树新节点的函数，请补全代码。
struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* createNode(int val) {
    Node* node = ___(1)___;
    node->data = val;
    node->left = ___(2)___;
    node->right = ___(3)___;
    return node;
}