树的定义与相关概念 - CSP-J | C++ & Algorithm 编程研习社

树是什么？用来做什么？

想象一下你的家族族谱：最上面是曾祖父，他生了几个孩子，每个孩子又有自己的孩子……这种一层层分叉的结构就像一棵倒着长的树。在计算机里，这种结构就叫树。树非常适合表示“从根开始、层层分支”的关系，比如文件夹系统（根目录→子文件夹→文件）、学校组织（校长→年级主任→班主任→学生）、甚至游戏中的技能树（学会火球术才能学大火球术）。

树由节点和连接节点的边组成。每个节点存放一个数据（比如名字、数值），边表示节点之间的上下级关系。

拆解树的几个关键概念

1. 节点与边

节点（Node）：树中的每一个“小圆点”都是一个节点，它负责存放数据。
边（Edge）：连接两个节点的线。如果两个节点之间有边，说明它们有直接关系（比如父子关系）。

生活例子：学校组织里，每个“人”（校长、年级主任、班主任、学生）就是一个节点，上下级之间的“管理关系”就是边。

2. 根节点、父节点、子节点

根节点：最顶层的节点，整棵树唯一没有父节点的节点。就像族谱里的曾祖父。
父节点：如果一个节点A直接连到下面另一个节点B，A就是B的父节点。校长是年级主任的父节点。
子节点：反过来，B就是A的子节点。年级主任是校长的子节点。

代码演示（在原有代码基础上增加注释）：

class TreeNode:
    def __init__(self, data):
        self.data = data          # 节点存储的数据
        self.children = []        # 子节点列表（空列表）

# 创建根节点（校长）
root = TreeNode("校长")
# 创建子节点（年级主任）
child_b = TreeNode("年级主任")
child_c = TreeNode("另一个年级主任")
# 连接：校长有两个孩子
root.children.append(child_b)
root.children.append(child_c)

# 给年级主任加一个学生子节点
child_d = TreeNode("学生")
child_b.children.append(child_d)

print("根节点:", root.data)                    # 输出: 校长
print("根节点的子节点:", [c.data for c in root.children])  # 输出: ['年级主任', '另一个年级主任']

3. 叶子节点

没有子节点的节点叫叶子节点。就像家族里还没有孩子的婴儿，或者学校里的普通学生。叶子节点是树的“末端”。

例子：在上面的代码中，child_c（另一个年级主任）和child_d（学生）目前没有孩子，它们就是叶子节点。

4. 兄弟节点

同一个父节点下的所有子节点互为兄弟节点。比如校长有两个年级主任孩子，他俩就是兄弟。班主任的两个学生也是兄弟。

5. 深度与高度

深度：从根节点到某个节点经过的边数。根节点深度为0，它的一级孩子深度为1，二级孩子深度为2，以此类推。
高度：整棵树中所有节点深度的最大值。也可以说是“最深的深度”。高度用来描述树有多“高”。

生活比喻：在学校组织里，根节点（校长）深度0，年级主任深度1，班主任深度2，普通学生深度3。如果最深的节点深度是3，那这棵树的高度就是3。

小练习：想象一棵只有根节点的树，它的深度是多少？高度是多少？
答案：根节点深度0，整棵树高度也是0。

新手容易犯的5个错误

错误	正确做法
1. 忘记初始化`children`为空列表，直接`node.children.append(...)`会报错	在`__init__`里必须写`self.children = []`
2. 混淆深度和高度：深度是到某个节点的边数，高度是最大深度	深度是具体节点的属性，高度是树的全局属性
3. 认为每个节点只能有一个子节点（那是链表）	树的节点可以有0个、1个或多个子节点
4. 忘记给叶子节点添加子节点列表就调用`children`方法	叶子节点的`children`是空列表，调用`len(node.children)`没问题
5. 逻辑上搞反父子关系：把父节点加到子节点下面	一定要先创建父节点，再把子节点`append`到父节点的`children`里

完整示例：构建一棵“家族树”并打印所有节点

下面我们建立一个四代同堂的家族树：曾祖父（根）→ 爷爷、二爷爷 → 爸爸、叔叔 → 小明、小红。然后写一个函数遍历所有节点。

class TreeNode:
    def __init__(self, data):
        self.data = data          # 节点存储的数据（名字）
        self.children = []        # 子节点列表

# 创建根节点：曾祖父
great_grandpa = TreeNode("曾祖父")

# 创建第二层：爷爷、二爷爷
grandpa = TreeNode("爷爷")
uncle_grand = TreeNode("二爷爷")
great_grandpa.children.append(grandpa)
great_grandpa.children.append(uncle_grand)

# 创建第三层：爸爸、叔叔（从爷爷下生长）
dad = TreeNode("爸爸")
uncle = TreeNode("叔叔")
grandpa.children.append(dad)
grandpa.children.append(uncle)

# 创建第四层：小明、小红（从爸爸下生长）
ming = TreeNode("小明")
hong = TreeNode("小红")
dad.children.append(ming)
dad.children.append(hong)

# 写一个函数，遍历整棵树，打印每个节点名字和深度
def print_tree(node, depth=0):
    """打印节点及所有子节点，depth是当前深度"""
    print("  " * depth + node.data)        # 缩进表示深度
    for child in node.children:            # 对每个子节点递归调用
        print_tree(child, depth + 1)

print("家族树结构：")
print_tree(great_grandpa)

运行结果：

家族树结构：
曾祖父
  爷爷
    爸爸
      小明
      小红
    叔叔
  二爷爷

这个例子展示了如何用递归遍历整棵树——这也是未来学习树的遍历的基础。

拓展：相关知识点指引

树在CSP-J中非常重要，学好基础概念后可以继续学习：

树的遍历（先序遍历、中序遍历、后序遍历）——用于访问所有节点
二叉树——每个节点最多两个子节点，编程竞赛最常用
二叉搜索树——左小右大，快速查找
堆——一种特殊的完全二叉树，用于优先队列
并查集——用树形结构处理集合合并问题

如果你已经理解本文的节点、父子、叶子、深度等概念，下一步就可以动手实现一个二叉树类，并练习遍历代码。加油！

例题精讲