-
第7章 二叉树
第7章 二叉树
7.1 引言
在第6章“树的基本概念”中，我们了解到树结构是一种非线性层级结构，而二叉树（Binary Tree） 作为树结构的特殊子集，因其每个节点最多包含两个子节点（左子树和右子树）的特性，成为计算机科学中应用最广泛的树结构。二叉树的“左、右子树有序性”（左右子树不能随意互换）使其在数据存储、搜索、排序等场景中具有独特优势——例如，二叉搜索树（BST）可实现高效的动态查找（平均时间复杂度O(log n)），平衡二叉树（如红黑树）被广泛用于数据库索引和集合类实现，表达式树可直观解析数学运算逻辑。
与普通树相比，二叉树的结构更简单且规则性更强，这使得其遍历、插入、删除等操作的实现逻辑更清晰，也为后续学习复杂树结构（如B树、堆）奠定了基础。本章将聚焦二叉树的核心操作——遍历算法（深度优先与广度优先），通过Python实现递归与非递归遍历，并结合“表达式树计算”“哈夫曼编码”等工程案例，展示二叉树在实际问题中的应用，最终帮助读者建立“基于二叉树解决层级数据问题”的思维框架。
7.2 二叉树的定义与基本特性
7.2.1 二叉树的严格定义
定义7.1 二叉树：由有限个节点组成的有序树结构，满足以下条件：
1.每个节点最多有两个子节点，分别称为左子节点（Left Child） 和右子节点（Right Child）；
2.左子树和右子树是有序的（即“左子树≠右子树”，即使节点仅含一个子节点，也需明确其为左或右子树）；
3.空子树（不存在的子节点）视为“存在但节点为空”（例如，叶子节点的左、右子树均为空）。
关键区别：二叉树与普通树的核心差异在于有序性和子节点数量限制。普通树的子节点无顺序（兄弟节点可互换）且数量无限制，而二叉树的左右子树有明确顺序，且每个节点子节点数≤2。
7.2.2 二叉树的基本特性
基于第6章树的基本性质，结合二叉树的特殊性，补充以下特性：
特性1：第i层节点数上限
非空二叉树的第i层（根节点为第0层）最多有 2i2^i2i 个节点（证明见6.3.3节，因每个节点最多2个子节点，第i层节点数是第i-1层的2倍）。
特性2：高度为h的节点总数上限
高度为h（根节点高度为0，叶子节点高度为0）的二叉树，最多有 2h+1−12^{h+1}-12h+1−1 个节点（满二叉树情况，等比数列求和：1+2+4+⋯+2h=2h+1−11+2+4+dots+2h=2-11+2+4+⋯+2h=2h+1−1）。
特性3：叶子节点与度为2的节点关系
对任意非空二叉树，若叶子节点数为 n0n_0n0，度为2的节点数为 n2n_2n2，则 n0=n2+1n_0 = n_2 + 1n0=n2+1。
证明：设总节点数为 nnn，度为1的节点数为 n1n_1n1，则 n=n0+n1+n2n = n_0 + n_1 + n_2n=n0+n1+n2。由树的性质“边数=节点数-1”，且边数= n1+2n2n_1 + 2n_2n1+2n2（度为1的节点贡献1条边，度为2的节点贡献2条边，叶子节点贡献0条边），可得 n1+2n2=n−1n_1 + 2n_2 = n - 1n1+2n2=n−1。联立两式：
n1+2n2=(n0+n1+n2)−1 ⟹ n2+1=n0 n_1 + 2n_2 = (n_0 + n_1 + n_2) - 1 implies n_2 + 1 = n_0 n1+2n2=(n0+n1+n2)−1⟹n2+1=n0
7.2.3 特殊二叉树类型回顾
结合第6章内容，以下特殊二叉树在工程中尤为重要（本节聚焦其与遍历、操作相关的特性）：
满二叉树：所有非叶子节点度为2，叶子节点在同一层。其遍历序列具有对称性（如前序遍历的“根左右”与后序遍历的“左右根”对应）。
完全二叉树：除最后一层外，其余层节点数满（第i层 2i2^i2i 个节点），最后一层叶子从左到右连续排列。适合顺序存储（数组），父节点与子节点下标关系明确（父节点i的左子节点 2i+12i+12i+1、右子节点 2i+22i+22i+2）。
平衡二叉树：任意节点左、右子树高度差≤1，避免斜树退化（斜树遍历复杂度退化为O(n)，平衡树可保持O(log n)）。
7.3 二叉树的遍历算法
遍历（Traversal）是二叉树最核心的操作，指按某种规则依次访问树中所有节点，且每个节点仅访问一次。遍历的本质是将非线性的树结构转化为线性序列，以便后续处理（如打印、搜索、排序）。二叉树遍历分为深度优先遍历（DFS） 和广度优先遍历（BFS），前者又可分为前序、中序、后序三种。
7.3.1 深度优先遍历（DFS）
深度优先遍历指从根节点出发，优先沿左子树深入，直到无法继续（叶子节点），再回溯访问右子树，按“根节点访问时机”分为三种：
-
前序遍历（Preorder Traversal）
定义：访问顺序为“根节点 → 左子树 → 右子树”（根节点在遍历左、右子树之前访问）。
示例：对二叉树
1
/
2 3
/
4 5
前序遍历序列为：1 → 2 → 4 → 5 → 3。
递归实现：
递归思路：若树为空，返回；否则先访问根节点，再递归前序遍历左子树，最后递归前序遍历右子树。
python
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder_recursive(node, result=None):
"""前序遍历递归实现"""
if result is None:
result = []
if node is None:
return result
result.append(node.data) # 访问根节点
preorder_recursive(node.left, result) # 遍历左子树
preorder_recursive(node.right, result) # 遍历右子树
return result
# 构建示例二叉树
root = BinaryTreeNode(1)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)
root.left.left = BinaryTreeNode(4)
root.left.right = BinaryTreeNode(5)
print("前序遍历（递归）:", preorder_recursive(root)) # 输出：[1, 2, 4, 5, 3]
非递归实现：
递归本质是利用系统栈，非递归需手动用栈模拟。思路：
1.根节点入栈；
2.栈非空时，弹出栈顶节点，访问；
3.若右子节点非空，入栈；
4.若左子节点非空，入栈（因栈是“后进先出”，左子节点后入栈会先弹出，保证“根→左→右”顺序）。
python
def preorder_iterative(root):
"""前序遍历非递归实现（栈）"""
result = []
if root is None:
return result
stack = [root] # 栈初始化为根节点
while stack:
node = stack.pop() # 弹出栈顶节点
result.append(node.data) # 访问节点
# 右子节点先入栈，左子节点后入栈（保证左子树先访问）
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
print("前序遍历（非递归）:", preorder_iterative(root)) # 输出：[1, 2, 4, 5, 3]
-
中序遍历（Inorder Traversal）
定义：访问顺序为“左子树 → 根节点 → 右子树”（根节点在左子树遍历完成后访问）。
示例：对上述二叉树，中序遍历序列为：4 → 2 → 5 → 1 → 3。
核心意义：若二叉树为二叉搜索树（BST），中序遍历序列为升序序列（BST特性：左子树所有节点值＜根节点值＜右子树所有节点值），这是BST用于排序和搜索的基础。
递归实现：
思路：若树为空，返回；否则先递归中序遍历左子树，再访问根节点，最后递归中序遍历右子树。
python
def inorder_recursive(node, result=None):
"""中序遍历递归实现"""
if result is None:
result = []
if node is None:
return result
inorder_recursive(node.left, result) # 遍历左子树
result.append(node.data) # 访问根节点
inorder_recursive(node.right, result) # 遍历右子树
return result
print("中序遍历（递归）:", inorder_recursive(root)) # 输出：[4, 2, 5, 1, 3]
非递归实现：
中序遍历非递归比前序复杂，需先遍历到最左叶子节点，再回溯访问根节点和右子树。思路：
1.初始化当前节点为根节点，栈为空；
2.当前节点非空时，入栈并移动到左子节点（深入左子树）；
3.当前节点为空（到达最左叶子），弹出栈顶节点，访问，然后移动到右子节点（回溯访问右子树）；
4.重复2-3直到栈空且当前节点为空。
python
def inorder_iterative(root):
"""中序遍历非递归实现（栈）"""
result = []
stack = []
current = root # 当前节点从根开始
while stack or current:
# 遍历到最左叶子节点，路径入栈
while current:
stack.append(current)
current = current.left
# 弹出栈顶节点（最左未访问节点）
current = stack.pop()
result.append(current.data) # 访问节点
current = current.right # 移动到右子节点
return result
print("中序遍历（非递归）:", inorder_iterative(root)) # 输出：[4, 2, 5, 1, 3]
-
后序遍历（Postorder Traversal）
定义：访问顺序为“左子树 → 右子树 → 根节点”（根节点在左右子树均遍历完成后访问）。
示例：对上述二叉树，后序遍历序列为：4 → 5 → 2 → 3 → 1。
应用场景：删除二叉树节点（需先删除左右子树，再删除根节点）、计算表达式树（先计算左右子表达式，再计算根节点运算符）。
递归实现：
思路：若树为空，返回；否则先递归后序遍历左子树，再递归后序遍历右子树，最后访问根节点。
python
def postorder_recursive(node, result=None):
"""后序遍历递归实现"""
if result is None:
result = []
if node is None:
return result
postorder_recursive(node.left, result) # 遍历左子树
postorder_recursive(node.right, result) # 遍历右子树
result.append(node.data) # 访问根节点
return result
print("后序遍历（递归）:", postorder_recursive(root)) # 输出：[4, 5, 2, 3, 1]
非递归实现：
后序遍历非递归最复杂，因根节点需在左右子树后访问。有两种常用思路：
思路1（双栈法）：用第一个栈按“根→右→左”顺序入栈，弹出到第二个栈，第二个栈弹出顺序即为“左→右→根”（后序）。
思路2（标记法）：用栈存储（节点，访问标记），未访问的节点入栈时标记为False，弹出时若标记为False，重新入栈标记为True，并将右、左子节点入栈（标记False）；若标记为True，访问节点。
这里实现标记法（更直观）：
python
def postorder_iterative(root):
"""后序遍历非递归实现（栈+标记）"""
result = []
if root is None:
return result
stack = [(root, False)] # 栈元素：(节点, 是否访问过)，初始根节点未访问
while stack:
node, visited = stack.pop()
if not visited:
# 未访问：重新入栈（标记True），并按右→左顺序入栈子节点（未访问）
stack.append((node, True))
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
else:
# 已访问：加入结果
result.append(node.data)
return result
print("后序遍历（非递归）:", postorder_iterative(root)) # 输出：[4, 5, 2, 3, 1]
7.3.2 广度优先遍历（层次遍历）
定义：按节点深度（层级）从左到右访问，即先访问第0层（根节点），再第1层（根的左右子节点），以此类推，每层节点从左到右顺序访问。
示例：对上述二叉树，层次遍历序列为：1 → 2 → 3 → 4 → 5。
实现思路：用队列存储待访问节点，因队列“先进先出”特性可保证层级顺序。步骤：
1.根节点入队；
2.队列非空时，出队一个节点，访问；
3.若左子节点非空，入队；
4.若右子节点非空，入队；
5.重复2-4直到队空。
Python实现：
python
from collections import deque
def levelorder_traversal(root):
"""层次遍历（队列实现）"""
result = []
if root is None:
return result
queue = deque([root]) # 队列初始化为根节点
while queue:
node = queue.popleft() # 出队首节点
result.append(node.data) # 访问节点
# 左子节点先入队，右子节点后入队（保证从左到右顺序）
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
print("层次遍历:", levelorder_traversal(root)) # 输出：[1, 2, 3, 4, 5]
7.3.3 遍历算法复杂度分析
所有遍历算法的时间复杂度均为O(n)（n为节点数，每个节点访问一次），空间复杂度取决于树的高度h：
递归遍历：递归栈深度为h，空间复杂度O(h)（最坏情况h=n，如斜树；平衡树h=log n）；
非递归遍历（栈/队列）：栈/队列最大存储量为树的最大宽度（满二叉树第h层节点数 2h2^h2h，总空间O(n)；平衡树O(log n)）。
7.4 二叉树的Python实现
7.4.1 节点类与二叉树类设计
二叉树的实现需定义节点结构和树的操作方法。节点类存储数据及左右子节点引用，二叉树类封装构建、遍历、插入、删除等操作。
-
节点类（BinaryTreeNode）
python
class BinaryTreeNode:
"""二叉树节点类"""
def __init__(self, data):
self.data = data # 节点数据
self.left = None # 左子节点引用
self.right = None # 右子节点引用
def __str__(self):
return f"Node({self.data})"
-
二叉树类（BinaryTree）
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_level_order(self, data):
"""按层次顺序插入节点（适合构建完全二叉树）"""
if self.is_empty():
self.root = BinaryTreeNode(data)
return
# 队列存储待插入节点的父节点
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)
# 遍历方法封装（调用7.3节定义的遍历函数）
def preorder(self, recursive=True):
"""前序遍历，默认递归实现"""
if recursive:
return preorder_recursive(self.root)
else:
return preorder_iterative(self.root)
def inorder(self, recursive=True):
"""中序遍历"""
if recursive:
return inorder_recursive(self.root)
else:
return inorder_iterative(self.root)
def postorder(self, recursive=True):
"""后序遍历"""
if recursive:
return postorder_recursive(self.root)
else:
return postorder_iterative(self.root)
def levelorder(self):
"""层次遍历"""
return levelorder_traversal(self.root)
def __str__(self):
"""按层次顺序打印二叉树"""
return "Level Order: " + str(self.levelorder())
7.4.2 二叉树的删除操作
二叉树删除节点比链表复杂，需根据节点度（0/1/2）分情况处理，核心是保证删除后仍为二叉树结构。
- 删除节点的三种情况
情况1：删除叶子节点（度为0）
直接将其父节点的对应子节点引用设为None。
情况2：删除度为1的节点
将其父节点的对应子节点引用指向被删节点的子节点（若左子节点存在指向左，否则指向右）。
情况3：删除度为2的节点
需找到中序前驱（左子树中最大节点）或中序后继（右子树中最小节点）替换被删节点，再删除前驱/后继节点（前驱/后继节点度必为0或1，转化为情况1或2）。
-
实现思路（以删除值为data的节点为例）
python
def delete_node(root, data):
"""删除二叉树中值为data的节点，返回新根节点"""
# 步骤1：递归找到待删除节点及其父节点
if root is None:
return None # 树空，未找到
# 递归查找左子树
if data < root.data:
root.left = delete_node(root.left, data)
return root
# 递归查找右子树
elif data > root.data:
root.right = delete_node(root.right, data)
return root
# 找到待删除节点（data == root.data）
else:
# 情况1/2：度为0或1（左子树空或右子树空）
if root.left is None:
return root.right # 返回右子树（若右子树空则返回None）
elif root.right is None:
return root.left # 返回左子树
# 情况3：度为2，找中序后继（右子树最小节点）
else:
# 找右子树最小节点（中序后继）
successor_parent = root
successor = root.right
while successor.left:
successor_parent = successor
successor = successor.left
# 替换待删除节点值为后继节点值
root.data = successor.data
# 删除后继节点（后继节点度必为0或1）
if successor_parent == root:
successor_parent.right = successor.right
else:
successor_parent.left = successor.right
return root
说明：上述代码假设二叉树为二叉搜索树（节点值有序，便于比较查找），实际中需根据具体场景调整查找逻辑（如遍历查找）。
7.5 二叉树的典型应用
7.5.1 应用一：表达式树与数学计算
表达式树是二叉树的经典应用，用于解析和计算数学表达式（如“3+42-(8/4)”）。树中：
叶子节点为操作数（如3、4、2）；
内部节点为运算符（如+、、-、/）；
子树对应子表达式（如右子树“4*2”对应乘法子表达式）。
-
构建表达式树
步骤：
1.将中缀表达式转为后缀表达式（逆波兰式，利用栈处理运算符优先级）；
2.遍历后缀表达式，遇操作数创建叶子节点入栈；遇运算符弹出两个栈顶节点作为左右子树，创建运算符节点入栈；
3.最终栈中剩余节点即为表达式树的根。 -
计算表达式树
通过后序遍历表达式树：先递归计算左子树和右子树的值，再将运算符作用于两个结果。
示例代码：
python
def build_expression_tree(postfix):
"""从后缀表达式构建表达式树"""
stack = []
operators = {'+', '-', '*', '/'}
for token in postfix:
if token not in operators:
# 操作数：创建叶子节点入栈
stack.append(BinaryTreeNode(float(token)))
else:
# 运算符：弹出两个节点作为右、左子树（注意顺序）
right = stack.pop()
left = stack.pop()
node = BinaryTreeNode(token)
node.left = left
node.right = right
stack.append(node)
return stack[0] # 栈顶为根节点
def evaluate_expression_tree(root):
"""后序遍历计算表达式树值"""
if root is None:
return 0
# 叶子节点：返回操作数
if root.left is None and root.right is None:
return root.data
# 递归计算左右子树
left_val = evaluate_expression_tree(root.left)
right_val = evaluate_expression_tree(root.right)
# 应用运算符
if root.data == '+':
return left_val + right_val
elif root.data == '-':
return left_val - right_val
elif root.data == '*':
return left_val * right_val
elif root.data == '/':
return left_val / right_val # 假设除数不为0
# 示例：计算后缀表达式"3 4 2 * + 8 4 / -"（对应中缀"3+4*2-8/4"）
postfix = ["3", "4", "2", "*", "+", "8", "4", "/", "-"]
expr_tree_root = build_expression_tree(postfix)
print("表达式结果:", evaluate_expression_tree(expr_tree_root)) # 输出：3+8-2=9.0
7.5.2 应用二：哈夫曼编码（数据压缩）
哈夫曼编码是一种无损数据压缩算法，利用字符出现频率构建哈夫曼树（带权路径最短的二叉树），频率高的字符用短编码，频率低的用长编码，实现压缩。
-
哈夫曼树构建步骤
1.统计字符频率，每个字符作为叶子节点（权值为频率）；
2.初始化优先队列（最小堆），将所有叶子节点入队；
3.重复以下步骤直到队列只剩一个节点：
a. 弹出两个权值最小的节点；
b. 创建新内部节点（权值为两节点权值之和），两节点作为其左右子树；
c. 新节点入队；
4.队列中剩余节点即为哈夫曼树的根。 -
哈夫曼编码生成
从根节点出发，左分支标记“0”，右分支标记“1”，叶子节点的路径编码即为该字符的哈夫曼编码。
示例代码（核心步骤）：
python
import heapq
class HuffmanNode(BinaryTreeNode):
"""哈夫曼树节点（继承BinaryTreeNode，增加权值比较）"""
def __init__(self, data=None, weight=0):
super().__init__(data)
self.weight = weight # 权值（频率）
def __lt__(self, other):
"""重载小于运算符，用于优先队列排序"""
return self.weight < other.weight
def build_huffman_tree(freq_dict):
"""从频率字典构建哈夫曼树"""
# 初始化最小堆（所有叶子节点入堆）
heap = []
for char, freq in freq_dict.items():
heapq.heappush(heap, HuffmanNode(char, freq))
# 构建哈夫曼树
while len(heap) > 1:
# 弹出两个最小权值节点
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# 创建新内部节点（权值为两者之和，数据为空）
parent = HuffmanNode(weight=left.weight + right.weight)
parent.left = left
parent.right = right
heapq.heappush(heap, parent)
return heap[0] if heap else None # 根节点
def generate_huffman_codes(root):
"""生成哈夫曼编码（字典：字符→编码）"""
codes = {}
def traverse(node, current_code=""):
if node is None:
return
# 叶子节点：记录编码
if node.data is not None:
codes[node.data] = current_code if current_code else "0" # 特殊情况：只有一个字符
return
# 递归遍历左右子树
traverse(node.left, current_code + "0")
traverse(node.right, current_code + "1")
traverse(root)
return codes
# 示例：对字符串"abracadabra"（字符频率：a:5, b:2, r:2, c:1, d:1）
freq_dict = {'a':5, 'b':2, 'r':2, 'c':1, 'd':1}
huffman_root = build_huffman_tree(freq_dict)
huffman_codes = generate_huffman_codes(huffman_root)
print("哈夫曼编码:", huffman_codes) # 输出类似：{'a':'0', 'b':'111', 'r':'110', 'c':'100', 'd':'101'}
7.6 本章总结
二叉树的核心价值：作为有序树结构，二叉树通过左、右子树的区分，支持高效的遍历和搜索操作，是复杂树结构（如BST、红黑树、堆）的基础。
遍历算法是核心：
o深度优先（前序、中序、后序）依赖递归或栈实现，中序遍历在BST中可得到有序序列；
o广度优先（层次）依赖队列实现，适合按层级处理数据（如打印、逐层统计）。
实现要点：
o节点类需存储左右子节点引用，二叉树类封装构建、插入、遍历等操作；
o删除节点需处理三种情况（度0/1/2），度为2的节点需用前驱/后继替换。
工程应用：表达式树解析数学运算，哈夫曼树实现数据压缩，二叉搜索树支持动态查找，这些应用均依赖二叉树的层级结构和遍历特性。
二叉树的学习关键在于理解“递归思想”和“指针（引用）操作”，这对后续学习树的高级应用和图结构至关重要。
思考题
给定一棵二叉树的前序遍历序列[1,2,4,5,3]和中序遍历序列[4,2,5,1,3]，手动还原该二叉树结构，并写出后序遍历序列。
设计一个函数，判断两棵二叉树是否完全相同（结构相同且对应节点值相等）。
实现二叉树的“之字形层序遍历”（即第一层从左到右，第二层从右到左，交替进行）。
给定一棵二叉树，求其最大深度（根节点到最远叶子节点的路径长度）和最小深度（根节点到最近叶子节点的路径长度）。
结合本章哈夫曼编码示例，计算编码后字符串的总长度，并与等长编码（如每个字符3位）比较压缩率
本站原创，转载请注明出处：https://www.xin3721.com/python3/python49293.html
