数据结构与算法 / 系统课时

树的基本概念

树的基本概念

树用层级关系组织数据,但“深度”“高度”“子树”等术语容易因观察方向不同而混淆。本课将统一采用以边数计数的定义,并通过一棵具体的树和可运行程序验证各节点之间的关系。

学习目标

  • 能够准确识别根节点、父子节点、兄弟节点、叶节点和子树。
  • 能够按照统一约定计算节点的深度与高度。
  • 能够使用代码构建树并遍历、查询基本结构信息。

核心概念与关系

有根树从唯一根节点可达所有节点,且无环。树的节点值可以重复,结构由节点身份和边决定。除根节点外,每个节点恰好有一个父节点;一个节点可以有零个或多个子节点;没有子节点的节点称为叶节点。以某个节点为根并包含其全部后代的结构称为该节点的子树。

树结构中的根、父子、叶节点、深度与高度

本课采用“边数”作为计量单位:

术语 定义 示例
根节点 没有父节点的唯一节点 A
叶节点 没有子节点的节点 D、F、G
节点深度 从根节点到该节点经过的边数 G 的深度为 3
节点高度 从该节点到最深叶节点经过的最大边数 B 的高度为 2
子树 某节点及其全部后代构成的树 B、D、E、G

根节点深度为 0,叶节点高度为 0。整棵树的高度等于根节点的高度。部分教材以节点数量计数,使根深度或叶高度从 1 开始;两种约定都可使用,但同一道题和同一份代码中必须保持一致。

节点的度是其直接子节点数量,树的度是所有节点度数的最大值。兄弟节点拥有同一个父节点,例如 B 与 C 是兄弟节点,而 D 与 F 不是。

完整可运行示例

下面的 Python 程序为每个节点保存父节点和子节点。构建时通过 add_child 保持结构,先拒绝已有父节点与自环,再沿父链检查是否把祖先接成孩子。校验失败时不修改引用。父指针便于向上计算深度,子节点列表便于向下计算高度和执行先序遍历。

python
from __future__ import annotations

from dataclasses import dataclass, field

@dataclass(eq=False)
class TreeNode:
    value: str
    parent: TreeNode | None = field(default=None, init=False, repr=False)
    children: list[TreeNode] = field(default_factory=list, init=False, repr=False)

    def add_child(self, child: TreeNode) -> None:
        if child.parent is not None:
            raise ValueError("孩子已有父节点")
        current = self
        while current is not None:
            if current is child:
                raise ValueError("挂载会形成环")
            current = current.parent
        self.children.append(child)
        child.parent = self

def depth(node: TreeNode) -> int:
    result = 0
    current = node

    # 沿父指针回到根,每经过一条边深度加 1。
    while current.parent is not None:
        result += 1
        current = current.parent

    return result

def height(node: TreeNode) -> int:
    if not node.children:
        return 0

    # 节点高度取所有子树高度的最大值,再加当前边。
    return 1 + max(height(child) for child in node.children)

def preorder_nodes(node: TreeNode) -> list[TreeNode]:
    result = []

    def visit(current):
        result.append(current)
        for child in current.children:
            visit(child)

    visit(node)
    return result

def preorder(node: TreeNode) -> list[str]:
    return [entry.value for entry in preorder_nodes(node)]

def main() -> None:
    nodes = {value: TreeNode(value) for value in "ABCDEFG"}

    nodes["A"].add_child(nodes["B"])
    nodes["A"].add_child(nodes["C"])
    nodes["B"].add_child(nodes["D"])
    nodes["B"].add_child(nodes["E"])
    nodes["C"].add_child(nodes["F"])
    nodes["E"].add_child(nodes["G"])

    print("根节点:", nodes["A"].value)
    print("B 的父节点:", nodes["B"].parent.value)
    print("A 的子节点:", ", ".join(child.value for child in nodes["A"].children))
    print("叶节点:", ", ".join(node.value for node in preorder_nodes(nodes["A"]) if not node.children))
    print("E 的深度:", depth(nodes["E"]))
    print("G 的深度:", depth(nodes["G"]))
    print("B 的高度:", height(nodes["B"]))
    print("A 的高度:", height(nodes["A"]))
    print("B 子树先序遍历:", " -> ".join(preorder(nodes["B"])))

if __name__ == "__main__":
    main()

将代码保存为 tree_terms_demo.py,然后运行:

bash
python tree_terms_demo.py

预期输出

text
根节点: A
B 的父节点: A
A 的子节点: B, C
叶节点: D, G, F
E 的深度: 2
G 的深度: 3
B 的高度: 2
A 的高度: 3
B 子树先序遍历: B -> D -> E -> G

叶节点按给定的子节点顺序先序输出。深度计算沿父链,成本与深度成正比。先序与高度计算各访问子树节点一次,额外栈深度取决于子树高度。Python 的递归示例用于浅树,深树可改为显式栈。不要直接修改 parent 或 children 来绕过示例的结构检查。B 子树只包含 B 及其后代,不会包含兄弟节点 C,也不会包含祖先节点 A。

易混淆点与练习

深度从根向下观察,描述节点离根有多远;高度从节点向下观察,描述它离最深叶节点有多远。同一节点的深度和高度通常不同,二者也不能简单相加后代表整棵树高度,除非该节点恰好位于一条最深路径上。

“叶节点”与“度为 1 的节点”不是同一概念。叶节点的子节点数量必须为 0;在无根树的图论语境中,叶可能指只有一条相邻边的顶点,但本章讨论的是有根树,应以子节点数量判断。

练习一:在 F 下新增节点 H 和 I,输出新树的叶节点、C 的高度以及整棵树的高度。验收时应说明每个数值采用边数还是节点数计量。

练习二:实现 ancestors(node),按“父节点到根节点”的顺序返回祖先列表。对节点 G 的预期逻辑结果应为 E、B、A,但不要把当前节点自身加入列表。

本课总结

  • 根、父子、兄弟、叶和子树描述的是节点之间的结构关系。
  • 深度从根向下计数,高度从节点向最深叶节点计数,本课统一按边数计算。
  • 明确计数约定和遍历顺序,是后续学习二叉树、搜索树与树算法的基础。

下一课预告

下一课将进入二叉树结构,学习每个节点最多拥有两个子节点时的表示方式,并为先序、中序和后序遍历建立统一基础。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

树的基本概念

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通