层次遍历

admin管理员组

文章数量:1441117

层次遍历

定义

层次遍历（Level Order Traversal）：也称为广度优先遍历（Breadth-First Traversal）。它按照层次顺序（从根节点开始，然后是所有子节点，然后是子节点的子节点，依此类推）访问树的节点。

示例

我们可以使用一个二叉树作为例子，因为二叉树是树结构中最简单且最常见的一种。但请注意，层次遍历同样适用于其他类型的树，如N叉树。 假设我们有以下二叉树作为图例： 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 层次遍历的步骤是： 创建一个队列（Queue），并将根节点入队。 当队列不为空时，执行以下步骤： 出队一个节点，并访问它（打印其值或进行其他操作）。 如果该节点有左子节点，将左子节点入队。 如果该节点有右子节点，将右子节点入队。 重复步骤2，直到队列为空。 现在，我们根据这个二叉树进行层次遍历： 初始化队列，并将根节点1入队：Queue = [1] 队列不为空，执行以下操作： 出队节点1并访问它：访问 1 将节点1的左子节点2和右子节点3入队：Queue = [2, 3] 队列不为空，执行以下操作： 出队节点2并访问它：访问 2 将节点2的左子节点4和右子节点5入队：Queue = [3, 4, 5] 出队节点3并访问它：访问 3 将节点3的左子节点6和右子节点7入队：Queue = [4, 5, 6, 7] 队列不为空，继续执行... 出队节点4并访问它：访问 4 将节点4的左子节点8和右子节点9入队（如果它们存在）：Queue = [5, 6, 7, 8, 9]（注意：在这个例子中，节点8和9是节点4的子节点） ...（继续这个过程，直到队列为空） 最终，层次遍历的结果将是：1, 2, 3, 4, 5, 6, 7, 8, 9 这个遍历顺序是按照树的层次顺序进行的，首先访问根节点，然后访问所有子节点（从左到右），接着是子节点的子节点，依此类推。这种方法在图形算法、网络搜索、文件系统等许多领域都有广泛的应用。

Java代码实现

在Java中，我们可以使用队列（如LinkedList）来实现二叉树的层次遍历（广度优先遍历）。首先，我们需要一个基本的二叉树节点类（TreeNode），然后实现层次遍历的算法。

以下是实现这一功能的Java代码：

代码语言：javascript代码运行次数：0运行复制

import java.util.LinkedList;
import java.util.Queue;

// 二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeLevelOrderTraversal {
    
    // 层次遍历（广度优先遍历）方法
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 将根节点入队

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 当前层的节点数
            List<Integer> level = new ArrayList<>(); // 存储当前层的节点值

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll(); // 出队并访问节点
                level.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left); // 左子节点入队
                }
                if (node.right != null) {
                    queue.offer(node.right); // 右子节点入队
                }
            }

            result.add(level); // 将当前层的节点值列表添加到结果中
        }

        return result;
    }

    // 辅助方法，用于打印结果
    public static void printLevelOrder(List<List<Integer>> result) {
        for (List<Integer> level : result) {
            System.out.print("Level: ");
            for (int val : level) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }

    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.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);

        BinaryTreeLevelOrderTraversal traversal = new BinaryTreeLevelOrderTraversal();
        List<List<Integer>> result = traversal.levelOrder(root);

        // 打印层次遍历结果
        printLevelOrder(result);
    }
}

注意，上述代码中我使用了List<List<Integer>>来存储每一层的节点值，这样可以方便地返回所有层次的结果。在main方法中，我创建了一个与示例中相同的二叉树，并调用了levelOrder方法来获取层次遍历的结果，然后使用printLevelOrder方法将结果打印出来。

打印结果将是该二叉树的每一层的节点值。打印结果如下：

代码语言：javascript代码运行次数：0运行复制

Level: 1 
Level: 2 3 
Level: 4 5 6 7 
Level: 8 9

解释： 第一层只有一个节点，值为1。 第二层有两个节点，分别为2和3。 第三层有四个节点，分别为4、5、6和7。 第四层有两个节点，分别为8和9。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-05-24，如有侵权请联系 cloudcommunity@tencent 删除前往查看存储二叉树traversal遍历队列

本文标签： 层次遍历