java怎么遍历二叉树-java教程-PHP中文网

java怎么遍历二叉树

下次还敢

发布： 2024-05-26 10:42:20

原创

1369人浏览过

Java 中遍历二叉树的方法：深度优先遍历 (DFS)：前序：访问根、左子树、右子树中序：访问左子树、根、右子树后序：访问左子树、右子树、根广度优先遍历 (BFS)：按层级访问所有节点

java怎么遍历二叉树

如何遍历二叉树

遍历二叉树是一种访问和处理树中所有节点的系统方法。Java 中有几种不同的遍历方法，每种方法都适用于不同的情况。

深度优先遍历

深度优先遍历（DFS）从树的根节点开始，并递归地访问每个节点的子节点。有三种常见的 DFS 遍历：

立即学习“Java免费学习笔记（深入）”；

前序遍历：访问根节点，然后访问左子树，最后访问右子树。
中序遍历：访问左子树，然后访问根节点，最后访问右子树。
后序遍历：访问左子树，然后访问右子树，最后访问根节点。

广度优先遍历 (BFS)

广度优先遍历 (BFS) 从树的根节点开始，并按层级水平访问节点。它首先访问根节点，然后访问所有第 1 级子节点，然后访问所有第 2 级子节点，以此类推。BFS 通常使用队列数据结构来实现。

遍历方法的实现

Java 中可以以递归或非递归的方式实现 DFS 和 BFS。递归方法使用函数来调用自身，而非递归方法使用栈或队列数据结构。以下是使用递归实现前序遍历的示例：

public static void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.println(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
}

登录后复制

以下是使用队列实现 BFS 的示例：

public static void bfsTraversal(TreeNode root) {
    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);
        }
    }
}

登录后复制

选择合适的遍历方法

选择适当的遍历方法取决于应用程序的需求：