CC++ & Algorithm

树的基本概念

困难52
语言版本：C++Python
概述：树是一种像家族族谱一样的数据结构，有根、枝条和叶子，用来表示层次关系。

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

你有没有见过家族族谱？最上面是太爷爷，下面是爷爷、爸爸，再下面是你的兄弟姐妹。这种一层一层的“长辈-晚辈”关系，在计算机里就叫做树。树是一种非常重要的数据结构，专门用来表示有层次关系的数据——比如学校的年级班级、电脑里的文件夹、网站的菜单，甚至你玩的游戏里的技能树，都是树的样子。

树长什么样？

想象一棵倒过来的大树：树根在最上面，树干分叉出树枝，树枝再分叉，最后是叶子。在计算机里，树也是这样的结构，只不过我们把每个分叉点叫做节点，把连接节点的线叫做边。

  • 根节点：最顶端的那个节点，整棵树的起点。它没有“爸爸”（没有父节点）。比如你家族谱里最老的那位祖先。
  • 父节点与子节点：上下直接相连的两个节点。上面的叫父节点，下面的叫子节点。每个节点可以有多个子节点（就像爸爸可以有几个孩子），但每个节点只能有一个父节点（一个人只有一个亲爸爸）。
  • 叶子节点：最下面没有孩子的节点，就像大树上的叶子。在文件夹里，一个空文件夹或者一个文件就是叶子。
  • 子树：从树中任意一个节点往下看，它和它的所有子孙节点又构成一棵小树。比如从“爸爸”这个节点往下，就有一棵只有你、兄弟姐妹的“小家庭树”。

生活中的例子：

  • 学校组织：校长（根）→ 年级主任（子节点）→ 班主任（子节点）→ 学生（叶子）
  • 图书分类：图书馆（根）→ 文学类、科学类（子节点）→ 小说、诗歌（更小的子节点）
  • HTML网页：<html>（根）→ <head> 和 <body>（子节点）→ 里面的标签（叶子或继续分支）

树有什么用？

树能把一堆零散的数据组织成有层次的“大家庭”，方便我们查找、添加、删除。比如当你打开“我的电脑”，点开C盘，再点开Program Files文件夹——这个操作就是在遍历一棵树。如果你学过后面的二叉树（每个节点最多有两个孩子）和搜索树，就能快速找到数据，比在乱糟糟的列表里翻来翻去快多了。

用C++表示一棵树

在C++里，我们通常用结构体（struct）或类（class）来表示节点。每个节点存一个值，再存一个子节点列表（用向量或链表）。下面是一个基础版：

#include <iostream>
#include <vector>
using namespace std;

// 定义树节点结构体
struct TreeNode {
    int value;                      // 节点存的值
    vector<TreeNode*> children;     // 子节点列表（用指针数组）
};

int main() {
    // 创建根节点，值为1，子节点列表为空
    TreeNode* root = new TreeNode{1, {}};
    // 创建两个子节点
    TreeNode* child1 = new TreeNode{2, {}};
    TreeNode* child2 = new TreeNode{3, {}};
    // 把子节点加入根节点的孩子列表
    root->children.push_back(child1);
    root->children.push_back(child2);
    
    cout << "根节点值: " << root->value << endl;
    cout << "第一个子节点值: " << root->children[0]->value << endl;
    cout << "第二个子节点值: " << root->children[1]->value << endl;
    
    // 记得释放内存（这里简写，实际应用要delete所有节点）
    delete root;
    delete child1;
    delete child2;
    return 0;
}

这段代码手动创建了一棵只有3个节点的小树：根节点1，两个孩子2和3。注意每创建一个节点都要用 new 在堆上分配内存，用完要 delete 防止内存泄漏。

进阶：让树“动”起来——遍历整棵树

手动创建节点还行，要是树很大，我们就需要写一个函数来自动遍历所有节点。最常用的方法是递归：先访问当前节点，然后依次访问它的每个子节点（并让子节点重复这个动作）。就像你从爷爷开始，先喊一声“爷爷好”，然后让爸爸、叔叔、姑姑……每个人都接着喊自己的孩子们。

下面我们扩展上面的程序，加一个打印所有节点值的函数：

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int value;                      // 节点存的值
    vector<TreeNode*> children;     // 子节点列表
};

// 递归打印整棵树（前序遍历：先根，再孩子）
void printTree(TreeNode* node) {
    if (node == NULL) return;       // 如果节点是空指针，直接返回
    cout << node->value << " ";     // 先打印当前节点的值
    
    // 遍历每一个子节点，对每个子节点调用自己（递归）
    for (int i = 0; i < node->children.size(); i++) {
        printTree(node->children[i]);
    }
}

int main() {
    // 构造一棵稍微复杂的树：
    //        1
    //      / | \
    //     2  3  4
    //    / \     \
    //   5   6     7
    TreeNode* root = new TreeNode{1, {}};
    TreeNode* child2 = new TreeNode{2, {}};
    TreeNode* child3 = new TreeNode{3, {}};
    TreeNode* child4 = new TreeNode{4, {}};
    TreeNode* child5 = new TreeNode{5, {}};
    TreeNode* child6 = new TreeNode{6, {}};
    TreeNode* child7 = new TreeNode{7, {}};

    // 连接关系
    root->children.push_back(child2);
    root->children.push_back(child3);
    root->children.push_back(child4);
    child2->children.push_back(child5);
    child2->children.push_back(child6);
    child4->children.push_back(child7);

    cout << "树的遍历结果（前序）: ";
    printTree(root);
    cout << endl;

    // 释放内存（需要递归删除所有节点，这里简单只释放根，实际应遍历删除）
    // 为简便，这里略去完整释放代码（真实项目可用智能指针）
    delete root;
    return 0;
}

输出：

树的遍历结果（前序）: 1 2 5 6 3 4 7

解释：printTree 函数先打印根节点1，然后依次处理孩子2、3、4。处理孩子2时，又先打印2，然后打印它的孩子5、6……就像你从公司老板开始，每个部门经理报到自己的名字，然后让下属继续报。

新手容易犯的错误

  1. 忘记释放内存：用 new 创建节点后，如果不用 delete 删除，程序运行久了会内存泄漏。更好的做法是使用C++11的智能指针 std::shared_ptr 或 std::unique_ptr，它们会自动管理内存。
  2. 误以为节点可以有多个父节点：树里每个节点只能有一个父节点（根没有父节点）。如果你不小心让一个节点同时是两个节点的孩子，那就变成图（有环）了，不再是树。
  3. 空指针解引用：遍历时如果访问 node->children[i] 但 node 是空指针，程序会崩溃。一定要先判断 node != NULL 或 node != nullptr。
  4. 混淆了“子树”的概念：子树是从某个节点向下的一整块，不是随便切一个分支。例如，在本文的树中，节点2及其两个子节点5、6构成一个子树。
  5. 使用向量（vector）插入子节点时顺序搞混：向量按添加顺序存储，遍历时也会按这个顺序。如果在意顺序（比如家族排行），就要注意添加顺序。

完整可运行示例（带内存释放）

下面是一个完整程序，包含手动创建树、遍历、以及递归释放内存的函数，让你体验完整的树操作：

#include <iostream>
#include <vector>
using namespace std;

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

// 递归打印前序遍历
void printTree(TreeNode* node) {
    if (node == NULL) return;
    cout << node->value << " ";
    for (TreeNode* child : node->children) {
        printTree(child);
    }
}

// 递归释放所有节点内存
void deleteTree(TreeNode* node) {
    if (node == NULL) return;
    for (TreeNode* child : node->children) {
        deleteTree(child);    // 先删除子节点
    }
    delete node;              // 再删除当前节点
}

int main() {
    // 构建树：根为10，两个孩子20和30，20有一个孩子40
    //     10
    //    /  \
    //   20  30
    //   /
    //  40
    TreeNode* root = new TreeNode{10, {}};
    TreeNode* node20 = new TreeNode{20, {}};
    TreeNode* node30 = new TreeNode{30, {}};
    TreeNode* node40 = new TreeNode{40, {}};

    root->children.push_back(node20);
    root->children.push_back(node30);
    node20->children.push_back(node40);

    cout << "前序遍历结果: ";
    printTree(root);
    cout << endl;

    // 释放内存
    deleteTree(root);
    cout << "内存已释放，程序结束。" << endl;
    return 0;
}

运行输出：

前序遍历结果: 10 20 40 30 
内存已释放，程序结束。

下一步学什么？

树的知识非常丰富，学好基本概念后，你可以继续探索：

  • 二叉树：每个节点最多有两个子节点（左孩子、右孩子），是树的精简版，很多算法都基于它。
  • 二叉搜索树：左孩子值小于父节点，右孩子值大于父节点，查找数据非常快（就像翻字典）。
  • 堆（优先队列）：一种特殊的完全二叉树，用来快速找最大或最小值（比如游戏中的优先级队列）。
  • 图：树是图的一种特殊形式（无环连通图）。如果你理解了树，再学图就会容易很多。

树的概念就像一把钥匙，能帮你打开很多数据结构的大门。下次看到文件夹、族谱、成绩排名时，不妨想想：哦，原来这就是一棵树！

例题精讲

1单选题

在一棵有 n 个节点的树中，所有节点的度数之和与边数之间的关系是？

A度数之和 = 边数
B度数之和 = 2 × 边数
C度数之和 = 边数 - 1
D度数之和 = 边数 + 1
2单选题

以下关于二叉树和度为2的树的说法，正确的是？

A二叉树一定是度为2的树
B度为2的树一定是二叉树
C二叉树中每个节点的度数不超过2，且左右子树有序
D度为2的树中节点度数必须恰好为2
3判断题

在一棵树中，叶子节点的度数为0，根节点的度数一定大于0。

4判断题

树的深度是指从根节点到最远叶子节点经过的边数。

5填空题
以下函数通过递归计算树中某个节点的深度（根节点深度为0，根节点的父节点值为-1）。请补充完整。

int getDepth(int node, const vector<int>& parent) {
    if (parent[node] == -1) return 0;
    else return ___
}