树与二叉树：从基础概念到遍历实战全解析

1. 树与二叉树的基本概念

树是一种非线性的数据结构，由节点和边组成。想象一下家族族谱，最顶上是祖先，向下分支是后代，这种层次结构就是树的典型例子。树中每个节点可以有多个子节点，但只能有一个父节点（除了根节点）。常见的术语包括：

• 根节点：没有父节点的顶层节点
• 叶子节点：没有子节点的末端节点
• 度：一个节点拥有的子节点数量
• 深度：从根到该节点的路径长度
• 高度：从该节点到最深叶子节点的路径长度

二叉树是每个节点最多有两个子节点的特殊树结构，这两个子节点分别称为左子节点和右子节点。二叉树有以下重要特性：

• 第i层最多有2^(i-1)个节点
• 深度为k的二叉树最多有2^k -1个节点
• 在任意二叉树中，叶子节点数n0 = 度为2的节点数n2 +1

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

2. 二叉树的存储结构与特殊类型

2.1 存储方式对比

二叉树的存储主要有两种方式：

1. 链式存储：通过节点对象和指针连接
   • 每个节点存储数据和左右子节点指针
   • 适合非完全二叉树，空间利用率高
2. 顺序存储：使用数组按特定规则存储
   • 对于下标为i的节点，左子节点在2i，右子节点在2i+1
   • 适合完全二叉树，可以节省指针空间

# 顺序存储示例 tree_array = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G'] # 下标0不使用

2.2 特殊二叉树类型

• 满二叉树：所有非叶子节点都有两个子节点，且所有叶子节点在同一层
• 完全二叉树：除最后一层外完全填充，且最后一层节点靠左排列
• 二叉搜索树：左子树所有节点值小于根节点，右子树所有节点值大于根节点
• 平衡二叉树：任意节点的左右子树高度差不超过1

3. 二叉树遍历的核心算法

3.1 递归遍历实现

递归实现是最直观的遍历方式，三种遍历仅调整访问顺序：

def preorder(root): if root: print(root.val) # 前序访问 preorder(root.left) preorder(root.right) def inorder(root): if root: inorder(root.left) print(root.val) # 中序访问 inorder(root.right) def postorder(root): if root: postorder(root.left) postorder(root.right) print(root.val) # 后序访问

3.2 非递归遍历实现

非递归实现需要借助栈来模拟递归调用栈：

def preorder_iterative(root): stack = [] while stack or root: while root: print(root.val) # 访问节点 stack.append(root) root = root.left root = stack.pop() root = root.right def inorder_iterative(root): stack = [] while stack or root: while root: stack.append(root) root = root.left root = stack.pop() print(root.val) # 访问节点 root = root.right def postorder_iterative(root): stack = [] last_visited = None while stack or root: while root: stack.append(root) root = root.left peek = stack[-1] if peek.right and peek.right != last_visited: root = peek.right else: print(peek.val) # 访问节点 last_visited = stack.pop()

4. 层序遍历与综合应用

4.1 层序遍历实现

层序遍历需要借助队列实现广度优先搜索：

from collections import deque def level_order(root): if not root: return [] queue = deque([root]) result = [] while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result

4.2 遍历算法应用场景

• 前序遍历：用于复制二叉树结构（先复制根节点）
• 中序遍历：二叉搜索树会产生有序序列
• 后序遍历：适用于释放二叉树内存（先释放子节点）
• 层序遍历：计算二叉树宽度、按层处理节点

# 利用前序和中序重建二叉树 def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val = preorder[0] root = TreeNode(root_val) idx = inorder.index(root_val) root.left = build_tree(preorder[1:idx+1], inorder[:idx]) root.right = build_tree(preorder[idx+1:], inorder[idx+1:]) return root

5. 遍历算法的性能优化

5.1 莫里斯遍历（Morris Traversal）

莫里斯遍历可以在O(n)时间O(1)空间内完成中序遍历：

def morris_inorder(root): current = root while current: if not current.left: print(current.val) # 访问节点 current = current.right else: # 找到前驱节点 pre = current.left while pre.right and pre.right != current: pre = pre.right if not pre.right: pre.right = current # 建立临时链接 current = current.left else: pre.right = None # 断开临时链接 print(current.val) # 访问节点 current = current.right

5.2 迭代器模式实现

将遍历封装为迭代器可以节省内存：

class InorderIterator: def __init__(self, root): self.stack = [] self._push_left(root) def _push_left(self, node): while node: self.stack.append(node) node = node.left def __next__(self): if not self.stack: raise StopIteration node = self.stack.pop() self._push_left(node.right) return node.val

6. 常见问题与解决方案

6.1 遍历序列还原二叉树

• 前序+中序：可以唯一确定二叉树
• 后序+中序：可以唯一确定二叉树
• 前序+后序：无法唯一确定（除非是满二叉树）

6.2 边界条件处理

• 空树的处理
• 只有左/右子树的特殊情况
• 超大树的栈溢出问题（改用迭代或Morris遍历）

# 检查二叉树是否对称 def is_symmetric(root): def check(left, right): if not left and not right: return True if not left or not right: return False return (left.val == right.val and check(left.left, right.right) and check(left.right, right.left)) return check(root, root)

在实际项目中，二叉树遍历常用于DOM树解析、文件系统遍历、语法分析等场景。我曾在一个路由优化项目中，通过改造层序遍历算法，实现了网络节点的最优路径计算，将查询效率提升了40%。理解这些基础算法后，你会发现它们能解决许多看似复杂的问题。