1. 树与二叉树的基本概念树是一种非线性的数据结构由节点和边组成。想象一下家族族谱最顶上是祖先向下分支是后代这种层次结构就是树的典型例子。树中每个节点可以有多个子节点但只能有一个父节点除了根节点。常见的术语包括根节点没有父节点的顶层节点叶子节点没有子节点的末端节点度一个节点拥有的子节点数量深度从根到该节点的路径长度高度从该节点到最深叶子节点的路径长度二叉树是每个节点最多有两个子节点的特殊树结构这两个子节点分别称为左子节点和右子节点。二叉树有以下重要特性第i层最多有2^(i-1)个节点深度为k的二叉树最多有2^k -1个节点在任意二叉树中叶子节点数n0 度为2的节点数n2 1class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right2. 二叉树的存储结构与特殊类型2.1 存储方式对比二叉树的存储主要有两种方式链式存储通过节点对象和指针连接每个节点存储数据和左右子节点指针适合非完全二叉树空间利用率高顺序存储使用数组按特定规则存储对于下标为i的节点左子节点在2i右子节点在2i1适合完全二叉树可以节省指针空间# 顺序存储示例 tree_array [None, A, B, C, D, E, F, G] # 下标0不使用2.2 特殊二叉树类型满二叉树所有非叶子节点都有两个子节点且所有叶子节点在同一层完全二叉树除最后一层外完全填充且最后一层节点靠左排列二叉搜索树左子树所有节点值小于根节点右子树所有节点值大于根节点平衡二叉树任意节点的左右子树高度差不超过13. 二叉树遍历的核心算法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:idx1], inorder[:idx]) root.right build_tree(preorder[idx1:], inorder[idx1:]) 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%。理解这些基础算法后你会发现它们能解决许多看似复杂的问题。