CC++ & Algorithm

树的基本概念——像家族族谱一样的数据结构

困难5
语言版本：C++Python
概述：用家族族谱和文件夹的例子，帮你理解什么是树结构，以及节点、根、叶子这些基本术语。

像搭积木一样理解树——从族谱到Python代码

你是不是见过这样的东西：家里的族谱，往上能查到爷爷、太爷爷，往下能查到爸爸、你和弟弟妹妹；电脑里的文件夹，打开“我的文档”能看到“图片”“作业”“游戏”，每个文件夹里面还有子文件夹。这些一层套一层的结构，就好像一棵倒着长的树——最上面有一个“根”，根上长出树枝，树枝再长出更细的枝，最后是叶子。在编程里，这种用来表示“一对多”层次关系的数据结构，就叫做树。

树在计算机里可太常见了：用手机时的菜单、学校的组织架构、游戏的技能树、网站的导航栏……学会树，你就掌握了一种能描述现实中各种分层关系的工具。

1. 树的基本术语——先认识“家族成员”

树由许多节点组成，节点之间通过连线（叫边）连接。我们先来认识几个重要的“家庭成员”：

  • 根节点：最顶上的那个节点，没有父亲（父节点）。就像家族的始祖，或者学校里的校长。
  • 父节点和子节点：如果一个节点连着下面的另一个节点，上面的叫父节点，下面的叫子节点。比如“校长”是“副校长”的父节点，“副校长”是“校长”的子节点。一个父节点可以有很多子节点。
  • 叶子节点：没有子节点的节点。就像家族里辈分最小的人，或者文件夹里没有子文件夹的文件。
  • 兄弟节点：同一个父节点下的子节点之间互称兄弟。比如“一年级组长”和“二年级组长”是兄弟。
  • 深度与高度：从根到某个节点的层数叫深度（根深度为0）；某个节点到最远叶子节点的层数叫高度。可以想象成你坐在教室第几排（深度），或者从你的座位到最后一排的距离（高度）。

生活中的例子：学校的组织结构——校长是根，下面有副校长、教务主任、年级组长，再下面是班级和老师，最底下的学生就是叶子。再比如你家的零食柜：最顶层是“零食”，下面分“甜食”“咸味”“饮料”，甜食里又有“巧克力”“糖”……每个放了零食的抽屉就是叶子节点（不能再细分了）。

常见错误：初学者容易把“根”和“叶子”搞混。记住：根在最上面，叶子在最下面。树是从上往下生长的（画图时通常根在顶部）。

2. 在Python中搭建一棵树

建一棵树，就像搭积木一样。我们需要决定每个节点放什么数据，以及节点之间怎么连接。常用的方法有两种。

方法一：嵌套列表（适合固定的小树）

用列表来表示树，列表的第一个元素是根节点数据，后面的元素是子树（也是列表）。这种办法非常直接，适合树的结构固定、节点较少的情况。

比如，用一个嵌套列表描述你家的零食树：

# 用嵌套列表表示零食树
tree = ["零食",                        # 根节点
          ["甜食",                     # 第一个子树
              ["巧克力", "棒棒糖"]     # 甜食的子节点（叶子）
          ],
          ["咸味",                     # 第二个子树
              ["薯片", "瓜子"]
          ],
          ["饮料",                     # 第三个子树
              ["可乐", "牛奶"]
          ]
       ]

# 访问根节点的第一个孩子（甜食）里的第一个孩子（巧克力）
print(tree[1][1][0])  # 输出: 巧克力

优点：代码短，不需要定义类。缺点：修改起来麻烦，比如想往“甜食”里加一个新零食“棉花糖”，需要找到列表位置插入。

方法二：节点对象（灵活，适合动态变化）

就像我们之前用TreeNode类一样，每个节点用一个对象表示，内部用children列表装子节点。这种方法更接近真实编程中的做法，适合树经常增删改的情况。

我们再来一个例子，建一个班级的座位表：教室第一排是一个组长，他后面坐了几个组员，每个组员后面又可以带小组成员（不过教室通常只分两层，我们为了练习可以多层）。

class TreeNode:
    def __init__(self, name):
        self.name = name          # 节点名称（比如学生姓名）
        self.children = []        # 子节点列表

# 构造一个小树：第一排组长 -> 组员
root = TreeNode("第一排组长")
member1 = TreeNode("小红")
member2 = TreeNode("小明")
member3 = TreeNode("小刚")
root.children.append(member1)
root.children.append(member2)
root.children.append(member3)

# 给小红再带两个“徒弟”
child_a = TreeNode("小李")
child_b = TreeNode("小张")
member1.children.append(child_a)
member1.children.append(child_b)

# 打印第一排的所有组员
print("第一排组员:", end=" ")
for child in root.children:
    print(child.name, end=" ")
# 输出：第一排组员: 小红 小明 小刚

优点：每个节点可以有自己的数据，添加子节点就像调用append一样简单。缺点：需要写类，稍复杂一点。

常见错误：用节点对象时，忘记给新节点赋值children = []，或者错误地把一个节点同时加入两个父节点的子列表中（一个节点只能有一个父节点，否则会形成环，就不是树了）。

3. 遍历一棵树——像走迷宫一样访问每个节点

我们经常需要把树里所有节点都“走”一遍，这个操作叫遍历。对于二叉树（每个节点最多有两个子节点，通常叫左孩子和右孩子），有三种经典的遍历顺序：前序、中序、后序。名字里的“前中后”指的是访问根节点的时机。

遍历方式顺序生活类比
前序遍历先访问根，再访问左子树，最后访问右子树你在超市里从入口（根）开始，先看第一个货架（左子树）的所有商品，再去第二个货架（右子树）。
中序遍历先访问左子树，再访问根，最后访问右子树你在图书馆找书：先看左边书架，再拿起中间的书（根），最后看右边书架。
后序遍历先访问左子树，再访问右子树，最后访问根你打扫教室：先把左边书桌擦干净（左），再把右边书桌擦干净（右），最后擦讲台（根）。

我们用递归来实现遍历。递归就像“遇到一个节点，就按规则处理它和它的孩子”。写递归时，一定要有一个结束条件（遇到None就返回），否则会无限递归下去。

先定义一个二叉树节点类：

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value        # 节点存储的数据
        self.left = None          # 左子节点，初始为空
        self.right = None          # 右子节点，初始为空

然后构建一棵二叉树（比如用考试成绩的分段举例）：

# 构建一棵树，模拟考试分数段：
#       60（及格线）
#      /        \
#     30        80
#    /  \      /
#   20  45   70
root = BinaryTreeNode(60)
root.left = BinaryTreeNode(30)
root.right = BinaryTreeNode(80)
root.left.left = BinaryTreeNode(20)
root.left.right = BinaryTreeNode(45)
root.right.left = BinaryTreeNode(70)

现在写三个遍历函数，每个都用递归：

# 前序遍历：根 -> 左 -> 右
def preorder(node):
    if node is None:
        return
    print(node.value, end=" ")   # 访问根
    preorder(node.left)           # 遍历左子树
    preorder(node.right)          # 遍历右子树

print("前序遍历:", end=" ")
preorder(root)  # 输出: 60 30 20 45 80 70

# 中序遍历：左 -> 根 -> 右
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value, end=" ")
    inorder(node.right)

print("\n中序遍历:", end=" ")
inorder(root)  # 输出: 20 30 45 60 70 80

# 后序遍历：左 -> 右 -> 根
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value, end=" ")

print("\n后序遍历:", end=" ")
postorder(root)  # 输出: 20 45 30 70 80 60

你能看出什么规律吗？ 前序遍历先看到根（60），然后左子树，最后右子树；中序遍历的结果有点像从小到大排序（20 30 45 60 70 80），因为这是一棵二叉搜索树（左子节点比根小，右子节点比根大）；后序遍历最后才看到根（60），就像你先打扫完所有座位再擦讲台一样。

常见错误：

  • 递归函数里忘记写if node is None: return，导致无限递归（程序崩溃）。
  • 把preorder和inorder的参数顺序搞混，比如写成preorder(node.right, node.left)（其实每个函数只接受一个参数）。
  • 在遍历过程中试图修改树的结构（比如删除节点），这会导致遍历混乱。

4. 完整可运行的示例——建一棵“家谱树”并遍历

现在我们综合运用上面的知识，写一段完整的代码：用节点对象建一个简单的家谱（三代人），然后用三种顺序遍历它。

class TreeNode:
    """树节点类，表示一个人"""
    def __init__(self, name):
        self.name = name          # 人物姓名
        self.children = []        # 子女列表

# ---------- 构造家谱 ----------
# 祖宗（根节点）
grandpa = TreeNode("爷爷")

# 第二代
father = TreeNode("爸爸")
uncle = TreeNode("叔叔")
grandpa.children.append(father)
grandpa.children.append(uncle)

# 第三代（爸爸的孩子）
me = TreeNode("小明")
sister = TreeNode("小红")
father.children.append(me)
father.children.append(sister)

# 第三代（叔叔的孩子）
cousin = TreeNode("小刚")
uncle.children.append(cousin)

# ---------- 遍历函数（适用于多叉树） ----------
def preorder_tree(node):
    """前序遍历多叉树：先访问自己，再依次访问每个孩子"""
    if node is None:
        return
    print(node.name, end=" ")        # 访问当前节点
    for child in node.children:      # 遍历所有子节点
        preorder_tree(child)

def postorder_tree(node):
    """后序遍历多叉树：先访问所有孩子，最后访问自己"""
    if node is None:
        return
    for child in node.children:
        postorder_tree(child)
    print(node.name, end=" ")

# ---------- 输出结果 ----------
print("家谱前序遍历（先长辈后晚辈）:")
preorder_tree(grandpa)   # 输出: 爷爷 爸爸 小明 小红 叔叔 小刚

print("\n家谱后序遍历（先晚辈后长辈）:")
postorder_tree(grandpa)  # 输出: 小明 小红 爸爸 小刚 叔叔 爷爷

看到没有？前序遍历像长辈先点名，然后从上往下报名字；后序遍历像从小辈开始，最后才报到爷爷。不同遍历顺序适合不同场景，比如显示文件夹目录时通常用前序（先显示根目录，再显示子目录）。

5. 新手最容易犯的3个错误

  1. 忘记处理None：在递归遍历时，如果没有检查节点是否为None，当访问到叶子节点的孩子时就会报错。解决：递归函数第一行总是写if node is None: return。
  2. 混淆树类型：二叉树只有左右两个孩子，而多叉树用列表装任意多个孩子。初学者容易把二叉树的left/right和多叉树的children混用。解决：先想清楚你要构建的是二叉树还是多叉树，然后统一使用对应的属性名。
  3. 在遍历中修改树：比如在遍历过程中删除当前节点，会导致后面找不到孩子。解决：如果需要修改树，可以先用遍历收集要处理的信息，然后再修改，不要边遍历边改。

6. 接下来可以学什么？

树的世界很广阔，你现在已经掌握了基本概念、构造方法和递归遍历。接下来可以了解：

  • 二叉搜索树：左孩子比根小，右孩子比根大，插入、查找很快。
  • 堆：一种特殊的树，用来实现优先队列（比如游戏里先处理最紧急的任务）。
  • 图：比树更复杂，节点之间可以有任意多条边（树是图的一种特例）。
  • 递归算法：树遍历是递归的经典应用，学好递归对你理解其他算法很有帮助。

你可以试着把生活中的其他分层关系（比如网站菜单、文件系统、游戏技能树）用树来表示，然后用遍历函数打印出来。多动手练习，树就会变成你的好朋友！

例题精讲

1单选题

在树的数据结构中，以下哪个节点被称为“根节点”？

A没有子节点的节点
B没有父节点的节点
C有且只有一个父节点的节点
D有多个子节点的节点
2单选题

一棵树中，节点的“度”是指什么？

A节点的深度
B节点的高度
C节点拥有的子节点个数
D从根到节点的路径长度
3判断题

一棵树中，每个节点可以有多个父节点。

4判断题

一棵树中所有叶子节点的深度都相同。

5填空题
以下Python代码定义一个树的节点类，请在横线处补全代码，使得每个节点可以存储数据并维护子节点列表。
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = ___