6.1 树的基本术语：度、深度、高度、路径
树是一种非线性的数据结构，由节点（Node）和边（Edge）组成，具有层次关系。在开始深入学习二叉树之前，我们先来搞清楚几个基本术语，这些概念就像地图上的坐标，能帮你在树的世界里不迷路。
度（Degree）：一个节点的子节点数量称为该节点的度。比如，如果某个节点有3个孩子，那它的度就是3。整棵树的度是所有节点中最大的那个度数。
深度（Depth）：从根节点到当前节点的路径长度（边的数量）。根节点的深度为0，它的直接子节点深度为1，以此类推。
高度（Height）：从当前节点到最远叶子节点的最长路径长度。叶子节点的高度为0，根节点的高度就是整棵树的高度。
路径（Path）：从一个节点到另一个节点所经过的节点序列。路径长度就是边的数量。
这些概念听起来有点绕？别担心，用代码来演示一下就清晰多了！
python
class TreeNode:
"""定义树节点"""
def __init__(self, val=0, children=None):
self.val = val # 节点值
self.children = children if children is not None else [] # 子节点列表
def get_degree(node):
"""获取节点的度"""
if node is None:
return 0
return len(node.children)
def get_depth(root, target_val, current_depth=0):
"""获取目标节点的深度"""
if root is None:
return -1
if root.val == target_val:
return current_depth
# 在子节点中递归查找
for child in root.children:
depth = get_depth(child, target_val, current_depth + 1)
if depth != -1:
return depth
return -1
def get_height(node):
"""获取节点的高度"""
if node is None:
return -1
if not node.children: # 叶子节点
return 0
# 返回所有子节点高度的最大值加1
max_child_height = max(get_height(child) for child in node.children)
return max_child_height + 1
# 示例使用
if __name__ == "__main__":
try:
# 构建示例树: 1
# / | \
# 2 3 4
# /| |
# 5 6 7
node5 = TreeNode(5)
node6 = TreeNode(6)
node7 = TreeNode(7)
node2 = TreeNode(2, [node5, node6])
node3 = TreeNode(3, [node7])
node4 = TreeNode(4)
root = TreeNode(1, [node2, node3, node4])
print(f"节点2的度: {get_degree(node2)}") # 输出: 2
print(f"节点5的深度: {get_depth(root, 5)}") # 输出: 2
print(f"整棵树的高度: {get_height(root)}") # 输出: 2
except Exception as e:
print(f"发生错误: {e}")这节讲了树的基本术语：度表示节点的孩子数量，深度是从根到节点的距离，高度是从节点到最远叶子的距离，路径是节点间的连接序列。理解这些概念是学习更复杂树操作的基础。
6.2 二叉树的链式存储与数组存储
二叉树是每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。存储二叉树有两种主流方式：链式存储和数组存储。选择哪种方式取决于你的具体需求。
链式存储是最直观的方式，每个节点包含数据和两个指针（分别指向左子节点和右子节点）。这种方式灵活，适合动态变化的树结构。
数组存储利用数组的索引来隐式表示父子关系。对于完全二叉树特别高效，因为不会浪费空间。在数组中，如果父节点在索引i处，那么左子节点在2i+1，右子节点在2i+2（假设索引从0开始）。
让我们看看这两种实现方式：
python
# 链式存储实现
class BinaryTreeNode:
"""二叉树节点的链式存储"""
def __init__(self, val=0, left=None, right=None):
self.val = val # 节点值
self.left = left # 左子节点指针
self.right = right # 右子节点指针
# 数组存储实现
class ArrayBinaryTree:
"""二叉树的数组存储"""
def __init__(self, capacity=100):
self.tree = [None] * capacity # 初始化数组
self.size = 0 # 当前元素数量
def insert(self, index, val):
"""在指定索引插入值"""
if index >= len(self.tree):
raise IndexError("索引超出数组容量")
self.tree[index] = val
self.size = max(self.size, index + 1)
def get_left_child(self, index):
"""获取左子节点"""
left_index = 2 * index + 1
if left_index >= self.size or self.tree[left_index] is None:
return None
return self.tree[left_index]
def get_right_child(self, index):
"""获取右子节点"""
right_index = 2 * index + 2
if right_index >= self.size or self.tree[right_index] is None:
return None
return self.tree[right_index]
# 示例使用
if __name__ == "__main__":
try:
# 链式存储示例
root_linked = BinaryTreeNode(1)
root_linked.left = BinaryTreeNode(2)
root_linked.right = BinaryTreeNode(3)
root_linked.left.left = BinaryTreeNode(4)
# 数组存储示例: [1, 2, 3, 4, None, None, None]
array_tree = ArrayBinaryTree()
array_tree.insert(0, 1) # 根节点
array_tree.insert(1, 2) # 左子节点
array_tree.insert(2, 3) # 右子节点
array_tree.insert(3, 4) # 左子节点的左子节点
print(f"链式存储根节点值: {root_linked.val}")
print(f"数组存储根节点左子节点: {array_tree.get_left_child(0)}")
print(f"数组存储索引1的右子节点: {array_tree.get_right_child(1)}")
except Exception as e:
print(f"发生错误: {e}")这节介绍了二叉树的两种存储方式：链式存储通过指针连接节点，灵活但占用额外内存；数组存储利用索引关系，对完全二叉树空间效率高。根据应用场景选择合适的存储方式很重要。
6.3 四种遍历方式：前序、中序、后序、层序
遍历二叉树就像游览一个家族族谱，有不同的参观顺序。四种主要遍历方式各有用途：前序遍历适合复制树结构，中序遍历对二叉搜索树能输出有序序列，后序遍历常用于释放内存，层序遍历则按层级处理节点。
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 前序遍历 | preorder_traversal(root) | 根→左→右，适合树的复制，必需参数：根节点 |
| 中序遍历 | inorder_traversal(root) | 左→根→右，BST中序输出有序序列，必需参数：根节点 |
| 后序遍历 | postorder_traversal(root) | 左→右→根，适合释放内存，必需参数：根节点 |
| 层序遍历 | level_order_traversal(root) | 按层级从左到右，需要队列辅助，必需参数：根节点 |
下面用代码实现这四种遍历：
python
from collections import deque
class TreeNode:
"""二叉树节点定义"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root):
"""前序遍历：根→左→右"""
result = []
if root:
result.append(root.val) # 访问根节点
result.extend(preorder_traversal(root.left)) # 遍历左子树
result.extend(preorder_traversal(root.right)) # 遍历右子树
return result
def inorder_traversal(root):
"""中序遍历：左→根→右"""
result = []
if root:
result.extend(inorder_traversal(root.left)) # 遍历左子树
result.append(root.val) # 访问根节点
result.extend(inorder_traversal(root.right)) # 遍历右子树
return result
def postorder_traversal(root):
"""后序遍历：左→右→根"""
result = []
if root:
result.extend(postorder_traversal(root.left)) # 遍历左子树
result.extend(postorder_traversal(root.right)) # 遍历右子树
result.append(root.val) # 访问根节点
return result
def level_order_traversal(root):
"""层序遍历：按层级从左到右"""
if not root:
return []
result = []
queue = deque([root]) # 使用双端队列作为BFS队列
while queue:
node = queue.popleft() # 取出队首节点
result.append(node.val) # 访问节点
# 将子节点加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 示例使用
if __name__ == "__main__":
try:
# 构建二叉树: 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(f"前序遍历: {preorder_traversal(root)}") # [1, 2, 4, 5, 3]
print(f"中序遍历: {inorder_traversal(root)}") # [4, 2, 5, 1, 3]
print(f"后序遍历: {postorder_traversal(root)}") # [4, 5, 2, 3, 1]
print(f"层序遍历: {level_order_traversal(root)}") # [1, 2, 3, 4, 5]
except Exception as e:
print(f"发生错误: {e}")这节详细介绍了二叉树的四种遍历方式：前序、中序、后序和层序。每种遍历都有特定的应用场景，掌握它们是解决树相关问题的关键基础。
6.4 递归与迭代遍历的等价转换
虽然递归遍历代码简洁易懂，但在处理深度很大的树时可能遇到栈溢出问题。这时候就需要将递归转换为迭代实现。本质上，递归隐式使用了系统调用栈，而迭代则显式使用栈或队列来模拟相同的过程。
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 迭代前序 | iterative_preorder(root) | 使用栈模拟递归，注意入栈顺序 |
| 迭代中序 | iterative_inorder(root) | 先访问最左路径，再回溯 |
| 迭代后序 | iterative_postorder(root) | 最复杂，可用前序变形或双栈法 |
| 迭代层序 | level_order_traversal(root) | 使用队列，已在6.3节实现 |
让我们看看如何将递归遍历转换为迭代：
python
class TreeNode:
"""二叉树节点定义"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def iterative_preorder(root):
"""迭代前序遍历：使用栈"""
if not root:
return []
result = []
stack = [root] # 初始化栈，根节点入栈
while stack:
node = stack.pop() # 弹出栈顶节点
result.append(node.val) # 访问节点
# 注意：先压入右子节点，再压入左子节点
# 因为栈是LIFO，这样左子节点会先被处理
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
def iterative_inorder(root):
"""迭代中序遍历：使用栈"""
result = []
stack = []
current = root
while stack or current:
# 一直向左走到底，将路径上所有节点入栈
while current:
stack.append(current)
current = current.left
# 处理栈顶节点
current = stack.pop()
result.append(current.val)
# 转向右子树
current = current.right
return result
def iterative_postorder(root):
"""迭代后序遍历：使用两个栈"""
if not root:
return []
# 方法：使用两个栈，第一个栈用于遍历，第二个栈用于存储结果
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node) # 将节点压入结果栈
# 先压左子节点，再压右子节点
# 这样在stack2中会是根→右→左，反转后就是左→右→根
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
# 从stack2弹出得到后序遍历结果
result = []
while stack2:
result.append(stack2.pop().val)
return result
# 示例使用
if __name__ == "__main__":
try:
# 构建相同的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(f"迭代前序: {iterative_preorder(root)}") # [1, 2, 4, 5, 3]
print(f"迭代中序: {iterative_inorder(root)}") # [4, 2, 5, 1, 3]
print(f"迭代后序: {iterative_postorder(root)}") # [4, 5, 2, 3, 1]
except Exception as e:
print(f"发生错误: {e}")这节展示了如何将递归遍历转换为迭代实现，避免了深度递归可能导致的栈溢出问题。迭代方法虽然代码稍复杂，但在处理大型树结构时更加稳健可靠。