属性数据结构遍历详解

概述

属性数据结构 是指具有特定属性或特征的数据结构，如有序性、层级性、连通性等。遍历是访问数据结构中所有元素的基本操作，不同的数据结构有不同的遍历策略。

💡 提示: 核心思想
遍历的本质是：按照数据结构的特性，用合适的方式访问每个元素一次，且仅一次。

一、数组遍历

1.1 基本特性

特性	说明
存储方式	连续内存，随机访问
访问复杂度	O(1)
遍历复杂度	O(n)
属性	有序、固定大小、可重复

1.2 遍历思路

数组遍历的核心思路是线性扫描：从第一个元素开始，依次访问每个元素，直到最后一个元素。

思路流程：
1. 初始化指针/索引 i = 0
2. 检查 i < 数组长度
3. 访问 array[i]
4. i++
5. 回到步骤2

1.3 实现方式

方式1：传统 for 循环（最直接）

// 场景：需要索引值，需要提前知道数组大小
int[] arr = {1, 2, 3, 4, 5};

for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);  // 访问元素
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

显式控制索引，可以随意访问任何位置
适合需要索引的场景（如修改元素、计算位置等）

方式2：增强 for 循环（简洁）

// 场景：只需要元素值，不需要索引
int[] arr = {1, 2, 3, 4, 5};

for (int num : arr) {
    System.out.println(num);  // 访问元素
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

隐藏索引细节，代码更简洁
本质上还是顺序访问
不能修改数组元素（对基本类型）

方式3：迭代器遍历（通用）

// 场景：需要在遍历中删除元素
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    Integer num = iterator.next();
    if (num == 3) {
        iterator.remove();  // 安全删除
    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

迭代器维护遍历状态
支持在遍历中安全删除
适合集合框架

方式4：流式遍历（函数式）

// 场景：需要函数式编程风格
int[] arr = {1, 2, 3, 4, 5};

Arrays.stream(arr)
    .forEach(System.out::println);

// 或者带索引
IntStream.range(0, arr.length)
    .forEach(i -> System.out.println(arr[i]));

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

声明式编程，表达意图清晰
支持链式操作和函数组合
可能有额外开销

1.4 二维数组遍历

按行遍历（最常用）

int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// 思路：外层循环遍历行，内层循环遍历列
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[i].length; j++) {
        System.out.println(matrix[i][j]);
    }
}

// 访问顺序：1 2 3 4 5 6 7 8 9
// 时间复杂度：O(m*n)

思路分析：

外层控制行，内层控制列
按行优先顺序访问（cache 友好）
适合大多数矩阵操作

按列遍历

// 思路：外层循环遍历列，内层循环遍历行
for (int j = 0; j < matrix[0].length; j++) {
    for (int i = 0; i < matrix.length; i++) {
        System.out.println(matrix[i][j]);
    }
}

// 访问顺序：1 4 7 2 5 8 3 6 9
// 时间复杂度：O(m*n)

思路分析：

适合需要按列处理的场景
可能导致 cache miss（不如按行遍历高效）

对角线遍历

// 思路：按对角线方向遍历
// 第一条对角线：(0,0)
// 第二条对角线：(0,1), (1,0)
// 第三条对角线：(0,2), (1,1), (2,0)

for (int diag = 0; diag < matrix.length + matrix[0].length - 1; diag++) {
    // 对于第 diag 条对角线
    int startRow = Math.max(0, diag - matrix[0].length + 1);
    int endRow = Math.min(diag, matrix.length - 1);
    
    for (int i = startRow; i <= endRow; i++) {
        int j = diag - i;
        System.out.println(matrix[i][j]);
    }
}

// 访问顺序：1 2 4 3 5 7 6 8 9
// 时间复杂度：O(m*n)

思路分析：

对角线编号：i + j = diag
需要计算每条对角线的起点和终点
适合特定的矩阵问题

1.5 遍历变种

反向遍历

// 从后往前遍历
for (int i = arr.length - 1; i >= 0; i--) {
    System.out.println(arr[i]);
}

// 适用场景：
// 1. 需要从后往前处理
// 2. 删除元素时避免索引混乱

跳跃遍历

// 每隔 k 个元素访问一个
int k = 2;
for (int i = 0; i < arr.length; i += k) {
    System.out.println(arr[i]);
}

// 适用场景：
// 1. 采样
// 2. 步长遍历

条件遍历

// 只遍历满足条件的元素
for (int i = 0; i < arr.length; i++) {
    if (arr[i] > 5) {
        System.out.println(arr[i]);
    }
}

// 或使用流
Arrays.stream(arr)
    .filter(x -> x > 5)
    .forEach(System.out::println);

二、链表遍历

2.1 基本特性

特性	说明
存储方式	离散内存，通过指针连接
访问复杂度	O(n)
遍历复杂度	O(n)
属性	有序、动态大小、可重复

2.2 链表节点定义

class ListNode {
    int val;           // 数据
    ListNode next;     // 指向下一个节点
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

2.3 遍历思路

链表遍历的核心思路是指针跟踪：从头节点开始，通过 next 指针逐个访问每个节点。

思路流程：
1. 初始化指针 current = head
2. 检查 current != null
3. 访问 current.val
4. current = current.next
5. 回到步骤2

2.4 实现方式

方式1：while 循环（最常用）

// 场景：需要逐个访问节点
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

ListNode current = head;
while (current != null) {
    System.out.println(current.val);  // 访问节点
    current = current.next;            // 移动指针
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

最直接的遍历方式
通过 null 检查确定遍历结束
不修改链表结构

方式2：递归遍历

// 场景：需要递归处理或反向遍历
void traverse(ListNode node) {
    if (node == null) {
        return;  // 递归终止条件
    }
    
    System.out.println(node.val);      // 前序处理
    traverse(node.next);               // 递归访问下一个
}

// 调用
traverse(head);

// 时间复杂度：O(n)
// 空间复杂度：O(n)（递归栈）

思路分析：

递归天然适合链表结构
空间复杂度较高（栈深度）
适合需要反向处理的场景

方式3：反向遍历（递归）

// 场景：需要从后往前访问
void reverseTraverse(ListNode node) {
    if (node == null) {
        return;
    }
    
    reverseTraverse(node.next);        // 先递归到末尾
    System.out.println(node.val);      // 后序处理（反向）
}

// 调用
reverseTraverse(head);

// 输出顺序：3 2 1（如果链表是 1->2->3）

思路分析：

利用递归栈实现反向遍历
不需要额外的反向链表
空间复杂度 O(n)

方式4：快慢指针遍历

// 场景：需要找到中点、检测环等
ListNode slow = head;
ListNode fast = head;

// 思路：slow 每次走一步，fast 每次走两步
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

// slow 现在指向中点
System.out.println("中点值：" + slow.val);

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

快指针速度是慢指针的两倍
当快指针到达末尾时，慢指针在中点
适合检测环、找中点等

方式5：迭代器遍历

// 场景：使用集合框架
List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

隐藏指针细节
支持在遍历中删除
更安全的遍历方式

2.5 双向链表遍历

class DoublyListNode {
    int val;
    DoublyListNode prev;  // 前驱指针
    DoublyListNode next;  // 后继指针
    
    DoublyListNode(int val) {
        this.val = val;
    }
}

// 正向遍历
DoublyListNode current = head;
while (current != null) {
    System.out.println(current.val);
    current = current.next;
}

// 反向遍历（利用 prev 指针）
current = tail;
while (current != null) {
    System.out.println(current.val);
    current = current.prev;
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

双向链表支持双向遍历
反向遍历不需要递归
适合需要双向访问的场景

三、树的遍历

3.1 基本特性

特性	说明
存储方式	层级结构，父子关系
访问复杂度	O(n)
遍历复杂度	O(n)
属性	有序、非线性、无环

3.2 树节点定义

二叉树节点

class TreeNode {
    int val;              // 数据
    TreeNode left;        // 左子树
    TreeNode right;       // 右子树
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

多叉树节点

class NaryTreeNode {
    int val;                          // 数据
    List<NaryTreeNode> children;      // 子节点列表
    
    NaryTreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

特点：

每个节点可以有任意数量的子节点
适合表示文件系统、组织结构等
遍历逻辑更通用

3.3 深度优先遍历（DFS）

前序遍历（Pre-order）

遍历顺序：根 → 左子树 → 右子树

思路流程：
1. 访问当前节点
2. 递归遍历左子树
3. 递归遍历右子树

// 递归实现
void preorder(TreeNode node) {
    if (node == null) return;
    
    System.out.println(node.val);      // 1. 访问根
    preorder(node.left);               // 2. 遍历左子树
    preorder(node.right);              // 3. 遍历右子树
}

// 示例树：
//       1
//      / \
//     2   3
// 输出：1 2 3

思路分析：

最先访问根节点
适合需要先处理父节点的场景
如：复制树、序列化树

迭代实现（使用栈）：

void preorderIterative(TreeNode root) {
    if (root == null) return;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.val);
        
        // 注意：先压右子树，后压左子树
        // 这样弹出时左子树先出
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(h)，h 是树的高度

思路分析：

栈模拟递归调用
压栈顺序很关键（右先压，左后压）
避免递归栈溢出

中序遍历（In-order）

遍历顺序：左子树 → 根 → 右子树

思路流程：
1. 递归遍历左子树
2. 访问当前节点
3. 递归遍历右子树

// 递归实现
void inorder(TreeNode node) {
    if (node == null) return;
    
    inorder(node.left);                // 1. 遍历左子树
    System.out.println(node.val);      // 2. 访问根
    inorder(node.right);               // 3. 遍历右子树
}

// 示例树：
//       2
//      / \
//     1   3
// 输出：1 2 3

思路分析：

对于二叉搜索树，中序遍历得到有序序列
适合需要有序处理的场景
最常用的遍历方式

迭代实现（使用栈）：

void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 1. 一直向左走，压栈所有左节点
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 2. 左子树遍历完，弹出栈顶（根）
        current = stack.pop();
        System.out.println(current.val);
        
        // 3. 遍历右子树
        current = current.right;
    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(h)

思路分析：

关键：先一直向左，直到 null
然后处理栈顶，再向右
比前序遍历更复杂

后序遍历（Post-order）

遍历顺序：左子树 → 右子树 → 根

思路流程：
1. 递归遍历左子树
2. 递归遍历右子树
3. 访问当前节点

// 递归实现
void postorder(TreeNode node) {
    if (node == null) return;
    
    postorder(node.left);              // 1. 遍历左子树
    postorder(node.right);             // 2. 遍历右子树
    System.out.println(node.val);      // 3. 访问根
}

// 示例树：
//       3
//      / \
//     1   2
// 输出：1 2 3

思路分析：

最后访问根节点
适合需要先处理子节点的场景
如：删除树、计算树的高度

迭代实现（使用两个栈）：

void postorderIterative(TreeNode root) {
    if (root == null) return;
    
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    
    stack1.push(root);
    
    // 第一次遍历：根 → 右 → 左（反向的后序）
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    
    // 第二次遍历：弹出 stack2（得到正确的后序）
    while (!stack2.isEmpty()) {
        System.out.println(stack2.pop().val);
    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(n)

思路分析：

使用两个栈实现
第一个栈生成反向后序
第二个栈反转得到正确顺序

3.4 多叉树遍历

多叉树前序遍历

遍历顺序：根 → 所有子节点

// 递归实现
void preorderNary(NaryTreeNode node) {
    if (node == null) return;
    
    System.out.println(node.val);      // 1. 访问根
    
    // 2. 遍历所有子节点
    for (NaryTreeNode child : node.children) {
        preorderNary(child);
    }
}

// 示例树：
//         1
//      /  |  \
//     2   3   4
//    / \
//   5   6
// 输出：1 2 5 6 3 4

思路分析：

与二叉树前序类似，先访问根
遍历所有子节点而不是只有左右
时间复杂度 O(n)，空间复杂度 O(h)

迭代实现（使用栈）：

void preorderNaryIterative(NaryTreeNode root) {
    if (root == null) return;
    
    Stack<NaryTreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        NaryTreeNode node = stack.pop();
        System.out.println(node.val);
        
        // 关键：反向压栈子节点，保证正确的访问顺序
        for (int i = node.children.size() - 1; i >= 0; i--) {
            stack.push(node.children.get(i));
        }
    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(h)

思路分析：

反向压栈是关键（从最后一个子节点开始）
这样弹出时，第一个子节点先出
保证了正确的前序遍历顺序

多叉树后序遍历

遍历顺序：所有子节点 → 根

// 递归实现
void postorderNary(NaryTreeNode node) {
    if (node == null) return;
    
    // 1. 遍历所有子节点
    for (NaryTreeNode child : node.children) {
        postorderNary(child);
    }
    
    System.out.println(node.val);      // 2. 访问根
}

// 示例树同上
// 输出：5 6 2 3 4 1

思路分析：

先处理所有子节点，最后处理根
适合需要先处理子树的场景（如删除树）
时间复杂度 O(n)，空间复杂度 O(h)

迭代实现（使用两个栈）：

void postorderNaryIterative(NaryTreeNode root) {
    if (root == null) return;
    
    Stack<NaryTreeNode> stack1 = new Stack<>();
    Stack<NaryTreeNode> stack2 = new Stack<>();
    
    stack1.push(root);
    
    // 第一次遍历：生成反向的后序
    while (!stack1.isEmpty()) {
        NaryTreeNode node = stack1.pop();
        stack2.push(node);
        
        // 正向压栈子节点
        for (NaryTreeNode child : node.children) {
            stack1.push(child);
        }
    }
    
    // 第二次遍历：弹出 stack2
    while (!stack2.isEmpty()) {
        System.out.println(stack2.pop().val);
    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(n)

思路分析：

与二叉树后序类似，使用两个栈
第一个栈生成反向后序
第二个栈反转得到正确顺序

多叉树层序遍历

遍历顺序：按层从上到下

void levelorderNary(NaryTreeNode root) {
    if (root == null) return;
    
    Queue<NaryTreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        NaryTreeNode node = queue.poll();
        System.out.println(node.val);
        
        // 将所有子节点加入队列
        for (NaryTreeNode child : node.children) {
            queue.add(child);
        }
    }
}

// 输出：1 2 3 4 5 6

思路分析：

队列保证层序访问
遍历所有子节点而不是只有左右
时间复杂度 O(n)，空间复杂度 O(w)

分层遍历（返回每层的列表）

List<List<Integer>> levelorderNaryList(NaryTreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<NaryTreeNode> 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++) {
            NaryTreeNode node = queue.poll();
            currentLevel.add(node.val);
            
            // 将所有子节点加入队列
            for (NaryTreeNode child : node.children) {
                queue.add(child);
            }
        }
        
        result.add(currentLevel);
    }
    
    return result;
}

// 输出：[[1], [2, 3, 4], [5, 6]]

思路分析：

关键：记录每层的节点数
在处理当前层时，只处理 levelSize 个节点
这样可以清晰地分离各层

3.5 多叉树 vs 二叉树对比

维度	二叉树	多叉树
子节点数	最多 2 个	任意个
前序遍历	根→左→右	根→所有子
后序遍历	左→右→根	所有子→根
中序遍历	左→根→右	不适用
适用场景	搜索树、堆	文件系统、组织结构
实现复杂度	简单	稍复杂（循环遍历子节点）

3.6 广度优先遍历（BFS）

层序遍历（Level-order）

遍历顺序：按层从上到下，同层从左到右

思路流程：
1. 初始化队列，放入根节点
2. 队列不为空时：
   a. 弹出队列前端节点
   b. 访问该节点
   c. 将其子节点加入队列

// 使用队列实现
void levelorder(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

// 示例树：
//       1
//      / \
//     2   3
//    / \
//   4   5
// 输出：1 2 3 4 5

思路分析：

队列保证了层序访问
先进先出的特性很关键
适合需要按层处理的场景

分层遍历（返回每层的列表）

List<List<Integer>> levelOrderList(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 node = queue.poll();
            currentLevel.add(node.val);
            
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        
        result.add(currentLevel);
    }
    
    return result;
}

// 输出：[[1], [2, 3], [4, 5]]

思路分析：

关键：记录每层的节点数
在处理当前层时，只处理 levelSize 个节点
这样可以清晰地分离各层

3.5 DFS vs BFS 对比

维度	DFS（递归/栈）	BFS（队列）
实现	递归或栈	队列
空间复杂度	O(h)（高度）	O(w)（最大宽度）
适用场景	路径问题、深度问题	最短路径、层级问题
遍历顺序	深度优先	广度优先

四、图的遍历

4.1 基本特性

特性	说明
存储方式	邻接表或邻接矩阵
访问复杂度	O(V+E)
遍历复杂度	O(V+E)
属性	可能有环、可能不连通

4.2 图的表示

// 邻接表表示
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(1, 4));
graph.put(3, Arrays.asList(1));
graph.put(4, Arrays.asList(2));

// 邻接矩阵表示
int[][] adjMatrix = {
    {0, 1, 1, 0},  // 节点 0 的邻接
    {1, 0, 0, 1},  // 节点 1 的邻接
    {1, 0, 0, 0},  // 节点 2 的邻接
    {0, 1, 0, 0}   // 节点 3 的邻接
};

4.3 深度优先遍历（DFS）

思路：从起点开始，沿着一条路径尽可能深地探索，直到无法继续，然后回溯。

// 递归实现
void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
    visited.add(node);
    System.out.println(node);
    
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, graph, visited);
        }
    }
}

// 调用
Set<Integer> visited = new HashSet<>();
dfs(1, graph, visited);

// 时间复杂度：O(V+E)
// 空间复杂度：O(V)

思路分析：

使用 visited 集合防止重复访问（处理环）
递归自然地实现了深度优先
适合检测环、拓扑排序等

迭代实现（使用栈）：

void dfsIterative(int start, Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int node = stack.pop();
        
        if (visited.contains(node)) {
            continue;
        }
        
        visited.add(node);
        System.out.println(node);
        
        // 压栈所有未访问的邻接节点
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

// 时间复杂度：O(V+E)
// 空间复杂度：O(V)

思路分析：

栈模拟递归
需要检查是否已访问
避免重复处理

4.4 广度优先遍历（BFS）

思路：从起点开始，逐层探索所有邻接节点，然后探索下一层。

void bfs(int start, Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    
    queue.add(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }
}

// 时间复杂度：O(V+E)
// 空间复杂度：O(V)

思路分析：

队列保证了广度优先
访问时就标记，避免重复加入队列
适合最短路径问题

4.5 DFS vs BFS 对比

维度	DFS	BFS
数据结构	栈	队列
空间复杂度	O(V)	O(V)
适用场景	连通性、环检测、拓扑排序	最短路径、分层
遍历顺序	深度优先	广度优先

五、特殊数据结构遍历

5.1 二叉搜索树（BST）遍历

特性：左子树 < 根 < 右子树

// 中序遍历得到有序序列
void inorderBST(TreeNode node) {
    if (node == null) return;
    
    inorderBST(node.left);
    System.out.println(node.val);  // 输出有序
    inorderBST(node.right);
}

// 示例：
//       5
//      / \
//     3   7
//    / \ / \
//   2  4 6  8
// 中序输出：2 3 4 5 6 7 8

思路分析：

中序遍历的特殊应用
利用 BST 的有序性
时间复杂度 O(n)

5.2 堆的遍历

// 堆通常用数组表示
int[] heap = {10, 8, 9, 4, 5, 6, 7};

// 按数组顺序遍历（层序）
for (int i = 0; i < heap.length; i++) {
    System.out.println(heap[i]);
}

// 节点关系：
// 节点 i 的左子节点：2*i + 1
// 节点 i 的右子节点：2*i + 2
// 节点 i 的父节点：(i-1)/2

思路分析：

堆用数组表示，按层序存储
遍历就是按数组顺序访问
时间复杂度 O(n)

5.3 哈希表遍历

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);

// 方式1：遍历 key
for (String key : map.keySet()) {
    System.out.println(key);
}

// 方式2：遍历 value
for (Integer value : map.values()) {
    System.out.println(value);
}

// 方式3：遍历 entry（最高效）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// 方式4：迭代器
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

思路分析：

遍历 entry 最高效（避免重复查询）
哈希表无序，遍历顺序不确定
遍历中删除需要用迭代器

六、遍历的通用思路总结

6.1 遍历的三个核心要素

要素	说明	示例
访问顺序	按什么顺序访问元素	前序、中序、后序、层序
状态管理	如何跟踪已访问的元素	visited 集合、指针位置
终止条件	何时停止遍历	null、队列为空、visited 完全

6.2 选择遍历方式的决策树

需要遍历数据结构
    ↓
是否需要特定顺序？
    ├─ 是 → 选择对应的遍历方式
    │       ├─ 前序：先处理父节点
    │       ├─ 中序：有序处理（BST）
    │       ├─ 后序：先处理子节点
    │       └─ 层序：按层处理
    │
    └─ 否 → 选择最简单的方式
            ├─ 线性结构 → for 循环
            ├─ 树 → DFS 或 BFS
            └─ 图 → DFS 或 BFS

6.3 递归 vs 迭代

维度	递归	迭代
代码简洁性	简洁	复杂
空间复杂度	O(h)（栈）	O(h)（栈）
栈溢出风险	高（深度大）	低
理解难度	容易	较难
性能	略低（函数调用）	略高

七、常见遍历问题

7.1 如何在遍历中删除元素？

// ❌ 错误方式：直接删除
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == 3) {
        list.remove(i);  // 会导致索引混乱
    }
}

// ✅ 正确方式1：使用迭代器
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    if (iterator.next() == 3) {
        iterator.remove();  // 安全删除
    }
}

// ✅ 正确方式2：反向遍历
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i) == 3) {
        list.remove(i);  // 不影响后续索引
    }
}

// ✅ 正确方式3：收集要删除的元素
List<Integer> toRemove = new ArrayList<>();
for (int num : list) {
    if (num == 3) {
        toRemove.add(num);
    }
}
list.removeAll(toRemove);

7.2 如何处理环形结构？

// 问题：链表中可能有环
// 解决：使用 visited 集合或快慢指针

// 方式1：visited 集合
Set<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
    if (visited.contains(current)) {
        System.out.println("检测到环");
        break;
    }
    visited.add(current);
    current = current.next;
}

// 方式2：快慢指针（Floyd 算法）
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
        System.out.println("检测到环");
        break;
    }
}

7.3 如何处理不连通的图？

// 问题：图可能有多个连通分量
// 解决：对每个未访问的节点进行 DFS/BFS

void traverseAllComponents(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    
    for (int node : graph.keySet()) {
        if (!visited.contains(node)) {
            System.out.println("--- 新的连通分量 ---");
            dfs(node, graph, visited);
        }
    }
}

八、性能对比总结

数据结构	遍历方式	时间复杂度	空间复杂度	适用场景
数组	for 循环	O(n)	O(1)	顺序访问
链表	while 循环	O(n)	O(1)	顺序访问
树	DFS（递归）	O(n)	O(h)	深度优先
树	BFS（队列）	O(n)	O(w)	广度优先
图	DFS	O(V+E)	O(V)	连通性检测
图	BFS	O(V+E)	O(V)	最短路径
哈希表	entry 遍历	O(n)	O(1)	键值对访问

属性数据结构遍历详解

属性数据结构遍历详解

概述

一、数组遍历

1.1 基本特性

1.2 遍历思路

1.3 实现方式

方式1：传统 for 循环（最直接）

方式2：增强 for 循环（简洁）

方式3：迭代器遍历（通用）

方式4：流式遍历（函数式）

1.4 二维数组遍历

按行遍历（最常用）

按列遍历

对角线遍历

1.5 遍历变种

反向遍历

跳跃遍历

条件遍历

二、链表遍历

2.1 基本特性

2.2 链表节点定义

2.3 遍历思路

2.4 实现方式

方式1：while 循环（最常用）

方式2：递归遍历

方式3：反向遍历（递归）

方式4：快慢指针遍历

方式5：迭代器遍历

2.5 双向链表遍历

三、树的遍历

3.1 基本特性

3.2 树节点定义

二叉树节点

多叉树节点

3.3 深度优先遍历（DFS）

前序遍历（Pre-order）

中序遍历（In-order）

后序遍历（Post-order）

3.4 多叉树遍历

多叉树前序遍历

多叉树后序遍历

多叉树层序遍历

分层遍历（返回每层的列表）

3.5 多叉树 vs 二叉树对比

3.6 广度优先遍历（BFS）

层序遍历（Level-order）

分层遍历（返回每层的列表）

3.5 DFS vs BFS 对比

四、图的遍历

4.1 基本特性

4.2 图的表示

4.3 深度优先遍历（DFS）

4.4 广度优先遍历（BFS）

4.5 DFS vs BFS 对比

五、特殊数据结构遍历

5.1 二叉搜索树（BST）遍历

5.2 堆的遍历

5.3 哈希表遍历

六、遍历的通用思路总结

6.1 遍历的三个核心要素

6.2 选择遍历方式的决策树

6.3 递归 vs 迭代

七、常见遍历问题

7.1 如何在遍历中删除元素？

7.2 如何处理环形结构？

7.3 如何处理不连通的图？

八、性能对比总结

相关笔记