-
第6章 树的基本概念
第6章 树的基本概念
6.1 引言
在前面的章节中，我们讨论的数组、链表、栈、队列均为线性数据结构——数据元素按线性序列排列，每个元素（除首尾外）仅有一个直接前驱和一个直接后继。但现实世界中，许多数据关系并非线性：例如，公司的组织架构中，一个部门经理下辖多个员工；家谱中，一个父母有多个子女；文件系统中，一个文件夹包含多个子文件夹。这些“一对多”的层级关系，需要用树（Tree） 这种非线性数据结构来描述。
树结构的核心特征是层级嵌套：数据元素（称为“节点”）按层级组织，最顶层有一个根节点，每个节点可以有多个子节点，子节点又可以有自己的子节点，形成“树状”结构。这种结构突破了线性结构的序列限制，能更自然地表达具有层级和分支关系的数据，是数据库索引、搜索引擎、人工智能等领域的基础数据结构。
本章将从树的定义出发，系统讲解树的核心术语、基本性质、常见分类（重点是二叉树）及Python实现，为后续学习树的遍历、平衡树、堆等高级应用奠定基础。
6.2 树的定义与基本术语
6.2.1 树的定义
定义6.1 树（Tree）：由节点（Node） 和边（Edge） 组成的非线性数据结构，满足以下条件：
1.存在唯一一个根节点（Root Node），它没有前驱节点；
2.除根节点外，其余节点均有且仅有一个父节点（Parent Node）；
3.节点间通过边连接，形成一个无环连通图（任意两节点间有且仅有一条路径，且不存在回路）。
生活类比：一棵真实的树，根节点对应树根，边对应树干和树枝，叶子节点对应树叶——所有树枝从树根延伸，树叶长在树枝末端，且树枝间不会交叉（无环）。
6.2.2 核心术语
为准确描述树的结构，需掌握以下基本术语（结合图6-1示例理解）：
节点（Node）：树的基本单元，包含数据（数据域）和指向子节点的引用（指针域）。
o数据域：存储节点的值（如整数、字符串等）；
o指针域：存储指向子节点的引用（多叉树用列表，二叉树用left/right指针）。
根节点（Root）：树中唯一没有父节点的节点，是树的入口（如图6-1中的A）。
叶子节点（Leaf Node）：没有子节点的节点（如图6-1中的D、E、G、H），也称为“终端节点”。
非叶子节点（Non-Leaf Node）：至少有一个子节点的节点（如图6-1中的A、B、C、F），也称为“分支节点”。
父节点与子节点（Parent & Child）：若节点X直接通过一条边连接到节点Y，则X是Y的父节点，Y是X的子节点（如图6-1中，B是E和F的父节点，E和F是B的子节点）。
兄弟节点（Sibling）：具有相同父节点的节点互称为兄弟节点（如图6-1中，B、C、D是兄弟节点，E和F是兄弟节点）。
祖先与后代（Ancestor & Descendant）：从根节点到某节点路径上的所有节点都是该节点的祖先（包括父节点）；某节点的所有子节点、子节点的子节点等都是该节点的后代（如图6-1中，A是所有节点的祖先，F的后代是G）。
路径（Path）：从节点X到节点Y的唯一序列（由边连接），路径长度为边的数量（如图6-1中，A→B→F→G的路径长度为3）。
深度（Depth）：节点X的深度是从根节点到X的路径长度（根节点深度为0或1，视定义而定，本书采用根节点深度为0）。
o示例：图6-1中，A深度为0，B/C/D深度为1，E/F/H深度为2，G深度为3。
高度（Height）：节点X的高度是从X到其最深叶子节点的路径长度（叶子节点高度为0）；树的高度是根节点的高度。
o示例：图6-1中，G高度为0，F高度为1（G是其最深叶子），B高度为2（F→G路径长度2），树的高度为3（A→B→F→G路径长度3）。
度（Degree）：节点的度是其直接子节点的数量（叶子节点度为0）；树的度是所有节点度的最大值。
o示例：图6-1中，A的度为3（子节点B、C、D），B的度为2（E、F），树的度为3。
子树（Subtree）：以节点X为根的子树是由X及其所有后代组成的树（X称为子树的根）。
o示例：图6-1中，B及其后代E、F、G组成一棵子树，C及其后代H组成另一棵子树。
6.2.3 树与非树结构的区分
判断一个结构是否为树，需满足以下条件：
1.有且仅有一个根节点（无环且连通，避免多根或无根）；
2.所有非根节点有且仅有一个父节点（避免一个节点多个父节点，如“图”结构）；
3.无环（任意节点到根节点的路径唯一，不存在回路）。
反例：
两个独立的树组成的结构（称为“森林”）不是树（多根）；
节点B的父节点是A，节点C的父节点是A和B（C有两个父节点）不是树；
节点A→B→C→A（存在环）不是树。
6.3 树的基本性质
树的性质是理解树结构的关键，以下为常用性质（基于“根节点深度为0，高度为树的最大深度”定义）：
性质1：节点数与边数关系
一棵有n个节点的树有n-1条边。
证明：除根节点外，每个节点有且仅有一个父节点，对应一条入边，因此边数=节点数-1（根节点无入边）。
性质2：度与节点数关系
设树中节点的度分别为d₁, d₂, ..., dₙ（n为节点数），则所有节点的度之和=2×边数=2(n-1)。
证明：每条边对应一个父节点到子节点的连接，即每条边贡献一个“子节点计数”，而节点的度是其“子节点计数”，因此总度数=边数（每个边被一个父节点的度计数）。由性质1，边数=n-1，故总度数=2(n-1)？？？
（修正：实际应为“总度数=边数”，因为每条边对应一个父节点的度。例如，节点A有3个子节点，贡献3度，对应3条边。因此总度数=边数=n-1。原表述有误，正确性质为：所有节点的度之和 = n-1。）
正确证明：每个节点的度是其直接子节点数量，所有节点的度之和即树中所有子节点的总数。由于除根节点外，每个节点都是一个子节点，因此子节点总数=n-1（根节点不是子节点）。故总度数=n-1。
性质3：层级与节点数关系（针对二叉树）
非空二叉树的第i层（i≥0）最多有2ⁱ个节点。
证明（数学归纳法）：
o基础：i=0（根节点层），最多1个节点（2⁰=1），成立；
o假设：第i层最多2ⁱ个节点；
o推导：第i+1层节点是第i层节点的子节点，二叉树每个节点最多2个子节点，因此第i+1层最多2×2ⁱ=2ⁱ⁺¹个节点。
性质4：高度与节点数关系（针对满二叉树）
高度为h的满二叉树（所有叶子在同一层，非叶子节点度为2）有2ʰ⁺¹ - 1个节点。
证明：满二叉树第0层（根）1个节点，第1层2个，...，第h层2ʰ个，总节点数=1+2+4+...+2ʰ=2ʰ⁺¹ - 1（等比数列求和）。
6.4 树的分类
树的分类方式多样，按节点的子节点数量可分为“普通树（多叉树）”和“二叉树”；按结构是否平衡可分为“平衡树”和“非平衡树”；按是否有序可分为“有序树”和“无序树”。本节重点介绍最常用的二叉树及其特殊类型。
6.4.1 普通树（多叉树）
普通树（也称“多叉树”）是指节点的子节点数量不受限制（度可为任意非负整数）的树。现实中最常见的多叉树是文件系统：根目录是根节点，子目录和文件是子节点（目录是分支节点，文件是叶子节点）。
特点：
结构灵活，可表达任意层级关系；
实现复杂（子节点数量不固定，需用列表等动态结构存储子节点引用）。
6.4.2 二叉树
定义6.2 二叉树（Binary Tree）：每个节点的度≤2的树（即每个节点最多有2个子节点，分别称为左子节点（Left Child） 和右子节点（Right Child））。
二叉树是树结构中最重要的类型，因其结构简单（仅需两个指针）、实现高效，且许多复杂树（如多叉树）可通过“左孩子右兄弟”等方法转化为二叉树处理。
二叉树的5种基本形态：
1.空二叉树（无节点）；
2.仅含根节点；
3.根节点+左子树；
4.根节点+右子树；
5.根节点+左子树+右子树。
特殊二叉树类型
-
斜树（Skewed Binary Tree）
所有节点都只有左子节点（左斜树）或只有右子节点（右斜树），本质是“退化的二叉树”，结构与链表相同（时间复杂度退化为O(n)）。
示例：左斜树（1→2→3→4，每个节点只有左子节点）。 -
满二叉树（Full Binary Tree）
定义：所有非叶子节点的度均为2，且所有叶子节点在同一层（即不存在度为1的节点）。
特点：
叶子节点只能在最深层；
第i层节点数=2ⁱ（满足性质3的最大值）；
高度为h时，节点总数=2ʰ⁺¹ - 1（性质4）。
示例：高度为2的满二叉树（根节点有2个子节点，每个子节点有2个叶子节点，共1+2+4=7个节点）。 -
完全二叉树（Complete Binary Tree）
定义：除最后一层外，其余层都是满的（第i层节点数=2ⁱ），且最后一层的节点从左到右连续排列（不能有空缺）。
特点：
满二叉树是完全二叉树的特例（最后一层也满）；
最后一层的叶子节点可不满，但必须从左到右排列，不能有“右边节点存在而左边空缺”的情况；
适合用数组顺序存储（见6.6.1节），空间效率高。
示例：
高度为2的完全二叉树，最后一层有3个叶子节点（从左到右排列）；
高度为3的完全二叉树，前3层满（1+2+4=7个节点），第4层有5个叶子节点（从左到右连续）。
满二叉树与完全二叉树的区别：
满二叉树要求所有非叶子节点度为2且叶子在同一层；
完全二叉树允许最后一层叶子不满，但必须从左到右连续，且非最后一层必须满。 -
平衡二叉树（Balanced Binary Tree）
定义：任意节点的左子树和右子树高度差≤1的二叉树（避免斜树的退化结构）。
作用：保证树的高度为O(log n)，从而使插入、删除、查找等操作效率提升（后续章节详细讨论）。
示例：AVL树（最早的平衡二叉树）、红黑树（工业界常用）。
6.5 树的Python实现
树的实现需解决“如何表示节点间的父子关系”，核心是节点类的设计（存储数据和子节点引用）。本节实现两种最常用的树结构：多叉树（普通树）和二叉树。
6.5.1 多叉树的实现
多叉树节点的子节点数量不固定，因此用列表存储子节点引用（动态增减）。 -
多叉树节点类
python
class TreeNode:
"""多叉树节点类"""
def __init__(self, data):
self.data = data # 节点数据
self.children = [] # 子节点列表（存储TreeNode实例）
def add_child(self, child_node):
"""添加子节点"""
self.children.append(child_node)
def __str__(self, level=0):
"""递归打印树结构（缩进表示层级）"""
# 根节点缩进0，子节点缩进level+1（每一层缩进4个空格）
ret = " " * level + f"└── {self.data}
"
for child in self.children:
ret += child.__str__(level + 1) # 递归打印子节点
return ret
-
多叉树构建与使用示例
以“公司组织架构”为例构建多叉树：
python
if __name__ == "__main__":
# 构建根节点（CEO）
ceo = TreeNode("CEO")
# 添加一级子节点（部门经理）
tech_manager = TreeNode("技术部经理")
hr_manager = TreeNode("人事部经理")
ceo.add_child(tech_manager)
ceo.add_child(hr_manager)
# 为技术部经理添加子节点（员工）
tech_manager.add_child(TreeNode("后端开发工程师"))
tech_manager.add_child(TreeNode("前端开发工程师"))
tech_manager.add_child(TreeNode("测试工程师"))
# 为人事部经理添加子节点（员工）
hr_manager.add_child(TreeNode("招聘专员"))
# 打印树结构
print("公司组织架构:")
print(ceo)
输出（缩进表示层级）：
公司组织架构:
└── CEO
└── 技术部经理
└── 后端开发工程师
└── 前端开发工程师
└── 测试工程师
└── 人事部经理
└── 招聘专员
3. 多叉树的遍历
遍历是树的核心操作，多叉树常用深度优先遍历（先访问节点，再递归访问子节点）：
python
def traverse_tree(node):
"""深度优先遍历多叉树（先序遍历）"""
if not node:
return
print(node.data, end=" → ") # 访问当前节点
for child in node.children:
traverse_tree(child) # 递归遍历子节点
# 调用遍历函数
print("组织架构遍历:")
traverse_tree(ceo) # 输出：CEO → 技术部经理 → 后端开发工程师 → 前端开发工程师 → 测试工程师 → 人事部经理 →
招聘专员 →
6.5.2 二叉树的实现
二叉树每个节点最多有两个子节点（左子节点和右子节点），因此节点类用left和right两个指针分别指向左、右子树。
-
二叉树节点类
python
class BinaryTreeNode:
"""二叉树节点类"""
def __init__(self, data):
self.data = data # 节点数据
self.left = None # 左子节点引用
self.right = None # 右子节点引用
def __str__(self):
return str(self.data)
-
二叉树的构建
二叉树的构建方式有多种，最直接的是手动创建节点并连接（适合小规模二叉树）：
python
# 构建一棵简单的二叉树：
# 1
# /
# 2 3
# /
# 4 5
if __name__ == "__main__":
# 创建节点
root = BinaryTreeNode(1)
node2 = BinaryTreeNode(2)
node3 = BinaryTreeNode(3)
node4 = BinaryTreeNode(4)
node5 = BinaryTreeNode(5)
# 连接节点（构建父子关系）
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
# 验证结构
print(f"根节点: {root.data}")
print(f"根节点左子节点: {root.left.data}, 右子节点: {root.right.data}") # 输出：2, 3
print(f"节点2的左子节点: {node2.left.data}, 右子节点: {node2.right.data}") # 输出：4, 5
-
二叉树的基本操作
二叉树的操作包括插入、删除、遍历等，本节实现基础的插入（按层次顺序插入，即“广度优先插入”）和判空：
python
class BinaryTree:
"""二叉树类（基础实现）"""
def __init__(self, root_data=None):
self.root = BinaryTreeNode(root_data) if root_data is not None else None
def is_empty(self):
"""判断二叉树是否为空"""
return self.root is None
def insert(self, data):
"""按层次顺序（广度优先）插入节点（适合完全二叉树构建）"""
if self.is_empty():
self.root = BinaryTreeNode(data)
return
# 用队列存储待插入节点的父节点（广度优先遍历）
from collections import deque
queue = deque([self.root])
while queue:
current = queue.popleft()
# 左子节点为空，插入左子节点
if not current.left:
current.left = BinaryTreeNode(data)
return
# 右子节点为空，插入右子节点
if not current.right:
current.right = BinaryTreeNode(data)
return
# 左右子节点均非空，将其加入队列等待
queue.append(current.left)
queue.append(current.right)
def __str__(self):
"""按层次顺序打印二叉树（广度优先遍历）"""
if self.is_empty():
return "Empty Binary Tree"
result = []
from collections import deque
queue = deque([self.root])
while queue:
current = queue.popleft()
result.append(str(current.data))
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return "Binary Tree (Level Order): " + " → ".join(result)
# 使用示例
if __name__ == "__main__":
bt = BinaryTree(1) # 根节点1
bt.insert(2) # 根节点左子节点2
bt.insert(3) # 根节点右子节点3
bt.insert(4) # 节点2左子节点4
bt.insert(5) # 节点2右子节点5
bt.insert(6) # 节点3左子节点6
print(bt) # 输出：Binary Tree (Level Order): 1 → 2 → 3 → 4 → 5 → 6
说明：insert方法通过队列实现层次顺序插入，确保插入的节点按“从左到右、从上到下”的顺序填充，适合构建完全二叉树。
6.6 树的存储方式
树的存储需将“离散的节点”和“父子关系”映射到内存中，常用两种方式：顺序存储（数组）和链式存储（指针）。
6.6.1 顺序存储（数组）
原理：用数组下标表示节点的层级和位置，通过公式计算父子节点的下标关系（适合完全二叉树）。
完全二叉树的顺序存储
完全二叉树的节点按层次顺序存储在数组中，若节点下标为i（从0开始），则：
左子节点下标：2i + 1
右子节点下标：2i + 2
父节点下标：(i - 1) // 2
示例：完全二叉树[1, 2, 3, 4, 5, 6]（数组下标0~5）：
节点1（i=0）的左子节点2（i=1=2×0+1），右子节点3（i=2=2×0+2）；
节点2（i=1）的左子节点4（i=3=2×1+1），右子节点5（i=4=2×1+2）；
节点3（i=2）的左子节点6（i=5=2×2+1），右子节点为空（数组无下标6）。
优点：
随机访问效率高（O(1)通过下标访问节点）；
无需存储指针，空间效率高。
缺点：
仅适合完全二叉树（非完全二叉树会浪费大量空间，如斜树）；
插入/删除非末尾节点需移动大量元素（类似数组）。
6.6.2 链式存储（指针/引用）
原理：每个节点用对象/结构体存储，通过指针/引用指向子节点（适合任意树结构）。
多叉树的链式存储
节点包含数据域和子节点列表（如6.5.1节的TreeNode类，children列表存储子节点引用）。
二叉树的链式存储
节点包含数据域、左子节点指针、右子节点指针（如6.5.2节的BinaryTreeNode类，left和right属性）。
优点：
适合任意树结构，灵活度高；
插入/删除节点只需修改指针，无需移动大量元素。
缺点：
需额外存储空间存储指针（每个节点的指针域）；
随机访问效率低（需从根节点遍历，O(n)）。
6.6.3 存储方式选择
顺序存储：优先用于完全二叉树（如堆结构），需高效随机访问的场景；
链式存储：优先用于普通树、二叉树（非完全），需频繁插入删除的场景。
6.7 树的应用场景
树结构因层级表达能力强，在计算机领域有广泛应用：
-
文件系统
操作系统的文件系统是典型的多叉树结构：
根目录（根节点）包含子目录和文件；
子目录（分支节点）包含更低级子目录和文件；
文件（叶子节点）无下级节点。 -
数据库索引
关系型数据库常用B树/B+树（平衡多路查找树）作为索引结构：
树的高度低（通常3~4层），支持高效的范围查询和随机查询；
每个节点存储多个关键字，减少磁盘I/O次数（适合大数据量存储）。 -
表达式树
编译器用二叉树解析数学表达式（如(3+4)*5-6）：
运算符作为内部节点（度为2）；
操作数作为叶子节点（度为0）；
通过后序遍历计算表达式值（先算子表达式，再算父节点运算符）。 -
决策树
机器学习中的决策树模型是一种二叉树（或多叉树）：
内部节点表示特征判断（如“年龄>30？”）；
分支表示判断结果（“是”/“否”）；
叶子节点表示分类结果（如“购买”/“不购买”）。 -
家谱/组织结构
生活中的层级关系（如家谱、公司组织架构）可直接用树结构表达，直观且易于理解。
6.8 本章总结
树的本质：非线性层级结构，由节点和边组成，满足“唯一根节点、无环、连通”特征，突破线性结构的序列限制。
核心术语：节点、根、叶子、深度、高度、度、子树等，是描述树结构的基础语言。
基本性质：节点数=边数+1，总度数=节点数-1，二叉树第i层最多2ⁱ个节点。
重要分类：
o二叉树：每个节点最多2个子节点，是最常用的树结构；
o满二叉树：所有非叶子节点度为2，叶子在同一层；
o完全二叉树：最后一层叶子从左到右连续，适合顺序存储。
Python实现：
o多叉树：节点类用列表存储子节点，适合子节点数量不固定的场景；
o二叉树：节点类用left/right指针，实现简单且应用广泛。
存储方式：顺序存储（数组，适合完全二叉树）和链式存储（指针，适合任意树），需根据场景选择。
树是后续学习高级数据结构（如堆、红黑树、图）的基础，掌握树的定义、性质和实现，对理解复杂算法和系统设计至关重要。
思考题
推导高度为h的完全二叉树的节点数范围（提示：最小节点数=高度为h-1的满二叉树节点数+1，最大节点数=高度为h的满二叉树节点数）。
设计一个函数，计算二叉树的高度（提示：递归计算左子树和右子树高度，取最大值+1）。
如何将一棵多叉树转化为二叉树？（提示：“左孩子右兄弟”法——第一个子节点作为左子节点，其余子节点依次作为前一个子节点的右子节点）。
实现二叉树的三种深度优先遍历（前序：根→左→右；中序：左→根→右；后序：左→右→根），并验证遍历结果。
用顺序存储（数组）实现一个完全二叉树，支持获取节点的父节点、左子节点、右子节点。
本站原创，转载请注明出处：https://www.xin3721.com/python3/python49292.html
