数据结构与算法 / 系统课时
树的基本概念
树的基本概念
树用层级关系组织数据,但“深度”“高度”“子树”等术语容易因观察方向不同而混淆。本课将统一采用以边数计数的定义,并通过一棵具体的树和可运行程序验证各节点之间的关系。
学习目标
- 能够准确识别根节点、父子节点、兄弟节点、叶节点和子树。
- 能够按照统一约定计算节点的深度与高度。
- 能够使用代码构建树并遍历、查询基本结构信息。
核心概念与关系
有根树从唯一根节点可达所有节点,且无环。树的节点值可以重复,结构由节点身份和边决定。除根节点外,每个节点恰好有一个父节点;一个节点可以有零个或多个子节点;没有子节点的节点称为叶节点。以某个节点为根并包含其全部后代的结构称为该节点的子树。

本课采用“边数”作为计量单位:
| 术语 | 定义 | 示例 |
|---|---|---|
| 根节点 | 没有父节点的唯一节点 | A |
| 叶节点 | 没有子节点的节点 | D、F、G |
| 节点深度 | 从根节点到该节点经过的边数 | G 的深度为 3 |
| 节点高度 | 从该节点到最深叶节点经过的最大边数 | B 的高度为 2 |
| 子树 | 某节点及其全部后代构成的树 | B、D、E、G |
根节点深度为 0,叶节点高度为 0。整棵树的高度等于根节点的高度。部分教材以节点数量计数,使根深度或叶高度从 1 开始;两种约定都可使用,但同一道题和同一份代码中必须保持一致。
节点的度是其直接子节点数量,树的度是所有节点度数的最大值。兄弟节点拥有同一个父节点,例如 B 与 C 是兄弟节点,而 D 与 F 不是。
完整可运行示例
下面的 Python 程序为每个节点保存父节点和子节点。构建时通过 add_child 保持结构,先拒绝已有父节点与自环,再沿父链检查是否把祖先接成孩子。校验失败时不修改引用。父指针便于向上计算深度,子节点列表便于向下计算高度和执行先序遍历。
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,然后运行:
python tree_terms_demo.py预期输出
根节点: 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,但不要把当前节点自身加入列表。
本课总结
- 根、父子、兄弟、叶和子树描述的是节点之间的结构关系。
- 深度从根向下计数,高度从节点向最深叶节点计数,本课统一按边数计算。
- 明确计数约定和遍历顺序,是后续学习二叉树、搜索树与树算法的基础。
下一课预告
下一课将进入二叉树结构,学习每个节点最多拥有两个子节点时的表示方式,并为先序、中序和后序遍历建立统一基础。