CC++ & Algorithm

树的定义与相关概念

简单6
语言版本：C++
概述：树是一种像家谱一样的数据结构，由节点和边组成，有一个根节点和若干分支。

树：像家谱一样的数据结构

你见过家谱图吗？最上面是爷爷奶奶，他们生了爸爸和姑姑，爸爸又生了你和弟弟。如果把这张图倒过来看——根在上，枝叶在下——它就像一棵真正的树。在计算机里，这种结构就叫树（Tree）。树用来表示有层级关系的数据，比如电脑里的文件夹、公司的组织架构、网页的导航菜单，甚至比赛中的淘汰赛签表。

树由节点（Node）和边（Edge）组成。最顶上的节点叫根节点，最底下的、没有子节点的叫叶子节点。一个节点的直接上级叫父节点，直接下级叫子节点，同父的子节点之间是兄弟关系。每个节点可以有多个子节点，但只能有一个父节点（根节点没有父节点）。

树的关键概念

1. 根、叶子、父子、兄弟

  • 根节点：树的起点，就像家里的老祖宗。在电脑文件夹里，C盘就是根节点。
  • 叶子节点：没有孩子的节点，就像你这一代还没生孩子。一个空文件夹或者只包含文件的文件夹就是叶子节点。
  • 父节点：直接管着你的那个节点。比如“我的文档”是“作业”的父节点。
  • 子节点：被你管着的节点。“照片”是“我的文档”的子节点。
  • 兄弟节点：同属于一个父节点的节点。比如“作业”和“照片”是兄弟，因为它们都在“我的文档”下面。

生活中的例子：班级的班干部结构。班长是根节点，下面有学习委员、体育委员、劳动委员（子节点），每个委员下面还有小组长。学习委员和体育委员是兄弟关系。

2. 节点的度

一个节点有多少个直接子节点，就叫它的度。叶子节点的度是0。例如，如果根节点有3个孩子，根的度就是3。整棵树中最大的度称为树的度。

例子：二叉树就是每个节点最多有两个孩子（度≤2），三叉树就是每个节点最多有三个孩子。

3. 树的深度、高度、层

  • 深度：从根节点到某个节点经过的边数。根节点的深度是0。
  • 高度：从某个节点到最远叶子节点经过的边数。叶子节点的高度是0。
  • 层：深度+1。根节点在第1层，它的孩子在第2层，以此类推。

例子：你的家谱中，爷爷奶奶在第1层，爸爸在第2层，你在第3层。爸爸的深度是1，高度是1（到你这条分支）。

生活中的树形结构

除了家谱和文件夹，还有哪些地方用到了树？

  • 计算机的文件系统：C盘 → 我的文档 → 作业、照片、音乐……每打开一个文件夹，就相当于进入一个子节点。
  • 公司组织架构：CEO → 技术部、市场部、财务部 → 各小组 → 普通员工。
  • 图书馆图书分类：文学类 → 中国文学、外国文学 → 小说、散文、诗歌。
  • 体育比赛：淘汰赛的晋级图，两两比赛，胜者向上，最终决出冠军（根节点）。

这些例子都说明：树是把复杂关系变得清晰的好工具。

C++ 代码实现树

在代码中，我们用指针来连接节点。每个节点里面存着数据，还有指向子节点的指针。下面以二叉树（每个节点最多有两个孩子）为例，演示如何定义节点、创建树、并遍历它。

1. 定义二叉树节点

struct TreeNode {
    int val;                // 节点里存的数据（比如名字或编号）
    TreeNode* left;         // 指向左子节点的指针
    TreeNode* right;        // 指向右子节点的指针

    // 构造函数：初始化节点时给一个值，左右孩子先设为空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 创建一棵简单的树

我们创建三个节点：根节点值为1，左孩子值为2，右孩子值为3。然后用 -> 符号把指针连起来。

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int main() {
    // 创建三个节点
    TreeNode* root = new TreeNode(1);   // 根节点，值为1
    TreeNode* child1 = new TreeNode(2); // 左子节点，值为2
    TreeNode* child2 = new TreeNode(3); // 右子节点，值为3

    // 链接成树：根节点的左指针指向child1，右指针指向child2
    root->left = child1;
    root->right = child2;

    // 打印验证
    cout << "根节点值: " << root->val << endl;          // 输出1
    cout << "左孩子值: " << root->left->val << endl;    // 输出2
    cout << "右孩子值: " << root->right->val << endl;   // 输出3

    // 释放内存（实际项目中建议用智能指针，这里简化）
    delete root;
    delete child1;
    delete child2;
    return 0;
}

运行结果：

根节点值: 1
左孩子值: 2
右孩子值: 3

3. 给树加点功能：计算节点数量（遍历）

我们可以写一个函数，用递归来数一数树里有多少个节点。递归就像沿着树枝一直往下走，走到叶子再回头。

// 递归计算树的节点总数
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;                // 空树，节点数为0
    return 1 + countNodes(root->left) + countNodes(root->right); // 自己 + 左子树 + 右子树
}

在主函数里调用它：

int total = countNodes(root);
cout << "树中总共有 " << total << " 个节点" << endl; // 输出3

新手容易犯的错误

  1. 忘记初始化指针
    创建节点后，必须把 left 和 right 设为 nullptr（空指针），否则指针是乱指的，程序会崩溃。我们在构造函数里已经做了这件事。

  2. 指针搞混，连接成环
    比如 root->left = child1; child1->right = root; 就形成了一个环，不再是树。树不允许出现环路。

  3. 内存泄漏
    用 new 创建的节点，一定要用 delete 释放。如果只 new 不 delete，程序运行久了会占用越来越多内存。实际项目中可以用 std::unique_ptr 或 std::shared_ptr 自动管理内存。

  4. 访问空指针
    比如 root->left->val 如果 root->left 是空指针，就会报错。所以访问前最好检查一下：if (root->left != nullptr)。

完整可运行的示例

下面是一个完整的程序，创建一棵稍微大一点的树（4个节点），并用递归计算节点数和打印每个节点的值（前序遍历）。

#include <iostream>
using namespace std;

// 二叉树节点结构体
struct TreeNode {
    int val;                // 数据值
    TreeNode* left;         // 左子节点指针
    TreeNode* right;        // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历：先访问根，再左子树，再右子树
void preorder(TreeNode* root) {
    if (root == nullptr) return;          // 空节点直接返回
    cout << root->val << " ";             // 访问当前节点
    preorder(root->left);                 // 递归遍历左子树
    preorder(root->right);                // 递归遍历右子树
}

// 计算节点总数
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    // 创建一棵树：
    //         1
    //        / \
    //       2   3
    //      /
    //     4
    TreeNode* root = new TreeNode(1);
    TreeNode* node2 = new TreeNode(2);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(4);

    root->left = node2;    // 1的左孩子是2
    root->right = node3;   // 1的右孩子是3
    node2->left = node4;   // 2的左孩子是4

    // 前序遍历输出
    cout << "前序遍历结果: ";
    preorder(root);
    cout << endl;

    // 计算节点数
    int total = countNodes(root);
    cout << "节点总数: " << total << endl;

    // 释放内存（递归释放，简单起见这里只演示了直接delete）
    // 实际应写一个递归释放函数，或者使用智能指针
    delete root;
    delete node2;
    delete node3;
    delete node4;
    return 0;
}

运行结果：

前序遍历结果: 1 2 4 3
节点总数: 4

小总结

  • 树是有层次的数据结构，每个节点只有一个父节点（根除外）。
  • 常用概念：根、叶子、父子兄弟、度、深度、高度、层。
  • 在C++中，常用指针把节点串起来，像搭积木一样构造树。
  • 遍历和递归是处理树的“瑞士军刀”，非常常用。

学完了树的基础，下一步可以学习二叉树的特殊形式（满二叉树、完全二叉树）、二叉搜索树（BST）以及树的遍历（前序、中序、后序、层次）。如果对更复杂的关系感兴趣，还可以研究图——树其实就是一种特殊的图（没有环的连通图）。掌握好树，你就能轻松理解文件系统、编译器语法树、游戏场景管理等许多实际问题啦！

例题精讲

1单选题

下列关于树的说法中，正确的是？

A树是一种线性数据结构，所有节点之间都是顺序关系
B树中可以有多个根节点，只要它们之间没有连接
C树是一种非线性数据结构，有且只有一个根节点
D树中每个节点都必须有至少一个子节点
2单选题

在一棵树中，节点的度是指？

A该节点的子节点个数
B该节点的父节点个数
C该节点的兄弟节点个数
D该节点到根节点的路径长度
3判断题

在树中，叶子节点没有子节点，但可以有父节点。

4判断题

一棵树的深度是指从根节点到最远叶子节点的路径上的节点个数（包含根节点和叶子节点）。

5填空题
给定以下树节点结构，实现计算树中节点总数的函数。请在空白处填写正确的代码。

struct TreeNode {
    int val;
    vector<TreeNode*> children;
};

int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return ___;
    }
    int sum = 1;
    for (auto child : root->children) {
        sum += countNodes(child);
    }
    return sum;
}