当前位置：首页 > news >正文

HoRain云--二叉树遍历全解析：数据结构核心指南

news 2026/3/27 1:55:49

🎬 HoRain 云小助手：个人主页

⛺️生活的理想，就是为了理想的生活!

⛳️ 推荐

前些天发现了一个超棒的服务器购买网站，性价比超高，大内存超划算！忍不住分享一下给大家。点击跳转到网站。

⛳️ 推荐

二叉树与二叉树遍历：数据结构核心概念全解析

1. 前序遍历（Preorder Traversal）

2. 中序遍历（Inorder Traversal）

3. 后序遍历（Postorder Traversal）

4. 层序遍历（Level Order Traversal）

二叉树与二叉树遍历：数据结构核心概念全解析

二叉树是计算机科学中最基础且重要的非线性数据结构之一，广泛应用于搜索、排序、表达式求值、文件系统等领域。掌握二叉树及其遍历方法是算法学习的基石。

一、二叉树基础概念

4. 二叉树的存储表示

顺序存储（数组表示）

# 对于完全二叉树，可以用数组高效存储 # 节点i的父节点：floor((i-1)/2) # 节点i的左子节点：2*i + 1 # 节点i的右子节点：2*i + 2 tree_array = [1, 2, 3, 4, 5, 6, 7] # 表示一个完全二叉树

链式存储（节点表示）

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

二、二叉树遍历详解

二叉树遍历是指按照某种顺序访问树中所有节点，且每个节点仅访问一次的过程。主要有四种遍历方式：

1. 前序遍历（Preorder Traversal）

访问顺序：根节点 → 左子树 → 右子树

递归实现：

def preorder_traversal(root): if root is None: return [] result = [] result.append(root.val) # 访问根节点 result.extend(preorder_traversal(root.left)) # 遍历左子树 result.extend(preorder_traversal(root.right)) # 遍历右子树 return result

迭代实现（使用栈）：

def preorder_iterative(root): if not root: return [] result = [] stack = [root] while stack: node = stack.pop() result.append(node.val) # 先右后左，保证左子树先被访问 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result

应用场景：

复制二叉树结构
获取前缀表达式（波兰表达式）
目录树显示

2. 中序遍历（Inorder Traversal）

访问顺序：左子树 → 根节点 → 右子树

递归实现：

def inorder_traversal(root): if root is None: return [] result = [] result.extend(inorder_traversal(root.left)) # 遍历左子树 result.append(root.val) # 访问根节点 result.extend(inorder_traversal(root.right)) # 遍历右子树 return result

迭代实现：

def inorder_iterative(root): result = [] stack = [] current = root while current or stack: # 遍历到最左节点 while current: stack.append(current) current = current.left # 访问节点 current = stack.pop() result.append(current.val) # 转向右子树 current = current.right return result

应用场景：

二叉搜索树得到有序序列
表达式树求值（中缀表达式）
文件系统按名称排序

3. 后序遍历（Postorder Traversal）

访问顺序：左子树 → 右子树 → 根节点

递归实现：

def postorder_traversal(root): if root is None: return [] result = [] result.extend(postorder_traversal(root.left)) # 遍历左子树 result.extend(postorder_traversal(root.right)) # 遍历右子树 result.append(root.val) # 访问根节点 return result

迭代实现（双栈法）：

def postorder_iterative(root): if not root: return [] result = [] stack1 = [root] stack2 = [] while stack1: node = stack1.pop() stack2.append(node) if node.left: stack1.append(node.left) if node.right: stack1.append(node.right) while stack2: result.append(stack2.pop().val) return result

应用场景：

删除二叉树（先删除子节点再删除父节点）
计算目录大小
获取后缀表达式（逆波兰表达式）

4. 层序遍历（Level Order Traversal）

访问顺序：从上到下，从左到右，逐层访问

实现（使用队列）：

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

应用场景：

查找二叉树的最大/最小宽度
判断完全二叉树
按层次处理节点（如打印树形结构）

三、遍历算法对比与选择

遍历方式	时间复杂度	空间复杂度	核心思想	典型应用
前序遍历	O(n)	O(h)	深度优先，根优先	复制树、前缀表达式
中序遍历	O(n)	O(h)	深度优先，中间访问根	二叉搜索树排序
后序遍历	O(n)	O(h)	深度优先，根最后	删除树、后缀表达式
层序遍历	O(n)	O(w)	广度优先，逐层访问	找最短路径、宽度

说明：

n：节点总数
h：树的高度（递归深度）
w：树的最大宽度

四、遍历的扩展应用

1. 根据遍历序列重建二叉树

# 根据前序和中序遍历重建二叉树 def build_tree(preorder, inorder): if not preorder or not inorder: return None # 前序遍历第一个元素是根节点 root_val = preorder[0] root = TreeNode(root_val) # 在中序遍历中找到根节点的位置 root_index = inorder.index(root_val) # 递归构建左右子树 root.left = build_tree( preorder[1:1+root_index], inorder[:root_index] ) root.right = build_tree( preorder[1+root_index:], inorder[root_index+1:] ) return root

2. 遍历的变体：Morris遍历

特点：O(1)空间复杂度，通过修改树结构实现遍历

def morris_inorder_traversal(root): result = [] current = root while current: if not current.left: result.append(current.val) current = current.right else: # 找到前驱节点 predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right if not predecessor.right: predecessor.right = current # 建立临时链接 current = current.left else: predecessor.right = None # 恢复树结构 result.append(current.val) current = current.right return result

3. 遍历可视化理解

1 / \ 2 3 / \ \ 4 5 6 前序遍历：1 → 2 → 4 → 5 → 3 → 6 中序遍历：4 → 2 → 5 → 1 → 3 → 6 后序遍历：4 → 5 → 2 → 6 → 3 → 1 层序遍历：[[1], [2, 3], [4, 5, 6]]

五、实战应用示例

1. 二叉树深度计算

def max_depth(root): """使用后序遍历计算二叉树最大深度""" if not root: return 0 left_depth = max_depth(root.left) right_depth = max_depth(root.right) return max(left_depth, right_depth) + 1

2. 判断对称二叉树

def is_symmetric(root): """使用层序遍历判断是否对称""" if not root: return True def is_mirror(left, right): if not left and not right: return True if not left or not right: return False return (left.val == right.val and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)) return is_mirror(root.left, root.right)

3. 二叉树的右视图

def right_side_view(root): """层序遍历的变体，获取每层最右侧节点""" if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) for i in range(level_size): node = queue.popleft() # 如果是当前层最后一个节点，加入结果 if i == level_size - 1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result