数据结构与算法 / 系统课时
树的基本概念
树的基本概念
树用父子关系组织具有层级的数据。本课统一根、父子、兄弟、叶子、深度、高度和子树等术语,并通过一个可运行示例观察树的递归结构,为后续二叉树遍历与统计打好基础。
学习目标
- 准确区分根节点、父子节点、兄弟节点和叶子节点
- 理解节点深度、节点高度、节点的度与子树
- 使用递归打印树并统计节点数量
基础术语与约定
树由节点和连接节点的边组成。没有父节点的节点称为根节点;一个节点直接连接的下级节点是它的子节点,具有同一父节点的节点互为兄弟节点;没有子节点的节点称为叶子节点。节点的度等于它的直接子节点数量。
本课用“边数”定义深度和节点高度:根节点深度为 0,叶子节点高度为 0。节点深度从根向下计算,节点高度从该节点向最远叶子向下计算。若按层数表示整棵树的高度,则等于根节点高度加 1。

树为什么适合递归
任意节点及其全部后代都构成一棵子树,因此“处理整棵树”可以拆成“处理当前节点,再处理每棵子树”。递归函数必须先处理空节点或叶子节点等终止条件,否则会无限向下调用。
统计节点数时,当前子树的节点数等于当前节点 1 个,加上所有子树的节点数之和。打印层级结构时,可以把深度作为参数,用缩进直观表示父子关系。
主示例:打印组织树并统计节点
下面用多叉树表示一个简化的团队结构。children 保存当前节点的直接子节点,两个递归函数分别负责打印层级和统计节点。
python
class TreeNode:
def __init__(self, name):
self.name = name
self.children = []
def add_child(self, child):
self.children.append(child)
def print_tree(node, depth=0):
# depth 决定缩进,也表示当前节点深度
print(" " * depth + node.name)
for child in node.children:
print_tree(child, depth + 1)
def count_nodes(node):
# 当前节点计 1,再累加每棵子树的节点数
return 1 + sum(count_nodes(child) for child in node.children)
root = TreeNode("研发中心")
backend = TreeNode("后端组")
frontend = TreeNode("前端组")
backend.add_child(TreeNode("支付服务"))
backend.add_child(TreeNode("订单服务"))
frontend.add_child(TreeNode("管理后台"))
root.add_child(backend)
root.add_child(frontend)
root.add_child(TreeNode("测试组"))
print_tree(root)
print("节点总数:", count_nodes(root))预期输出
text
研发中心
后端组
支付服务
订单服务
前端组
管理后台
测试组
节点总数: 7复杂度与易错点
打印和计数都会访问每个节点一次,时间复杂度为 。递归调用栈最多保存一条根到叶子的路径,额外空间复杂度为 ,其中 是树的层数。
不要把“节点值”和“节点身份”混为一谈:普通树允许多个节点保存相同值。深度从根向下,高度从节点向叶子向下;两者都必须先约定按边数还是层数计算。
按自己的节奏,确认真正理解。