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 = right2. 二叉树的存储结构与特殊类型
2.1 存储方式对比
二叉树的存储主要有两种方式：
- 链式存储：通过节点对象和指针连接
- 每个节点存储数据和左右子节点指针
- 适合非完全二叉树，空间利用率高
- 顺序存储：使用数组按特定规则存储
- 对于下标为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 result4.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 root5. 遍历算法的性能优化
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.right5.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.val6. 常见问题与解决方案
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%。理解这些基础算法后，你会发现它们能解决许多看似复杂的问题。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
