二叉树的层次遍历（Level Order Traversal）是以层为单位，从根节点开始逐层访问节点的遍历方法。在很多树的算法中，层次遍历是基础。本文将详细解析层次遍历的原理，提供Java和Python的实现，以及常见扩展应用。
一、层次遍历的定义与特点
1.1 什么是层次遍历？
层次遍历是指按照二叉树的层级，从上到下、从左到右依次访问每个节点。例如，对于如下二叉树：
1
/ \
2 3
/ \ \
4 5 6
层次遍历的访问顺序为：1 -> 2 -> 3 -> 4 -> 5 -> 6。
1.2 层次遍历的特点
- 遍历结果以层为单位。
- 借助队列（Queue）实现，先进先出（FIFO）保证节点按层顺序访问。
- 可扩展为分层输出或锯齿形遍历。
二、层次遍历的实现
2.1 基本步骤
- 初始化一个队列，将根节点加入队列。
- 循环执行以下操作，直到队列为空：
- 从队列中取出一个节点，访问它。
- 如果该节点有左子节点，将其加入队列。
- 如果该节点有右子节点，将其加入队列。
2.2 Java实现
树节点定义
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
层次遍历方法
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeLevelOrder {
public static void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll(); // 取出队首节点
System.out.print(current.val + " "); // 访问节点
if (current.left != null) {
queue.add(current.left); // 加入左子节点
}
if (current.right != null) {
queue.add(current.right); // 加入右子节点
}
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
System.out.println("层次遍历结果：");
levelOrder(root);
}
}
输出结果：
层次遍历结果：
1 2 3 4 5 6
2.3 Python实现
树节点定义
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
层次遍历方法
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
current = queue.popleft() # 取出队首节点
print(current.val, end=" ") # 访问节点
if current.left:
queue.append(current.left) # 加入左子节点
if current.right:
queue.append(current.right) # 加入右子节点
# 构建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print("层次遍历结果：")
level_order(root)
输出结果：
层次遍历结果：
1 2 3 4 5 6
三、按层分组输出的层次遍历
在某些场景下，我们需要按层将节点分组，例如：
层次分组遍历结果：
[[1], [2, 3], [4, 5, 6]]
3.1 Java实现
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class LevelOrderByLayer {
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 当前层节点数量
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode current = queue.poll();
currentLevel.add(current.val);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
result.add(currentLevel);
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
System.out.println("层次分组遍历结果：");
System.out.println(levelOrder(root));
}
}
3.2 Python实现
from collections import deque
def level_order_by_layer(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
current = queue.popleft()
current_level.append(current.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
result.append(current_level)
return result
# 构建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print("层次分组遍历结果：")
print(level_order_by_layer(root))
输出结果：
层次分组遍历结果：
[[1], [2, 3], [4, 5, 6]]
四、扩展应用
- 寻找二叉树的最大宽度：
- 在层次遍历中记录每层节点数量，取最大值。
- 锯齿形层次遍历（Z字形遍历）：
- 奇数层从左到右，偶数层从右到左访问节点。
- 判断完全二叉树：
- 使用层次遍历，确保某层出现空节点后不再有非空节点。
五、总结
层次遍历是二叉树遍历的重要方法，其实现简单且应用广泛。通过本文的学习，你掌握了：
- 层次遍历的基本实现。
- 按层分组输出的扩展。
- 常见的扩展应用场景。
层次遍历是树形结构问题的基础，建议在实际问题中多加练习，以便深入理解和灵活应用。
标签：遍历,TreeNode,current,right,二叉树,解析,root,left From： https://blog.csdn.net/zhaoshanshan168/article/details/144206599