困难C++6 分钟2,169 字

树的构造与存储

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


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

在前面,我们已经知道了树是一种“父子”关系的数据结构,就像一个家族的族谱,或者学校里的年级班级结构。那么,我们能不能在电脑里也造出一棵树来呢?当然可以!在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。

cpp
#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函数里(先序遍历),方便你看到整棵树的结构。

cpp
#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来存多叉树​​,比如一个“文件夹系统”:根目录下有若干子文件夹,每个文件夹里又有文件。或者试试用数组存二叉树​​,常用于堆(优先队列)。这些都会让树的世界更加丰富。


相关知识点指引​​:

  • 树的遍历(前序、中序、后序)
  • 二叉树搜索与插入
  • 用数组实现二叉堆
  • 多叉树的存储与遍历

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

同类知识点