Java二叉树遍历详解：BFS与DFS算法实现及代码示例

2 年 ago

科, 颖

2 minutes

广度优先搜索（BFS）和深度优先搜索（DFS）是遍历图和树的两种技术。在本教程中，我们将主要关注树中的广度优先搜索（BFS）和深度优先搜索（DFS）遍历。

深度优先搜索（DFS）是什么？

算法从根节点开始，然后在回溯之前探索每个分支。它使用堆栈实现。在编写代码时，通常使用递归栈来进行回溯。通过使用递归，我们能够利用左右子树也是树且具有相同属性的事实。

对于二叉树，有三种类型的DFS遍历方式：

中序遍历
先序遍历
后序遍历

什么是广度优先搜索（BFS）？

这个算法也是从根节点开始，然后逐层遍历所有节点。这意味着在根节点之后，它依次遍历所有根节点的直接子节点。在遍历完所有直接子节点之后，它会继续遍历它们的子节点，以此类推。为了实现广度优先搜索，我们使用了一个队列。

对于二叉树，我们有广度优先遍历即层序遍历。

在Java中实现BFS和DFS

让我们考虑的是这棵树：

TreeNode类的结构如下所示：

 static class TreeNode {
        int data;
        TreeNode left, right;

        public TreeNode(int key) {
            data = key;
            left = right = null;
        }
    }

1. 先序遍历

在二叉树的先序遍历中，我们首先遍历根节点，然后遍历左子树，最后遍历右子树。我们通过递归实现这个过程，以便从左子树和右子树也是树的这个事实中获益。

先序遍历的算法如下：

遍历根节点。
在左子树上调用preorder()。
在右子树上调用preorder()。

上面树的先序遍历为：

0 1 3 4 2

以下是Java代码：

 static void preorder(TreeNode node) {
        if (node == null)
            return;

        // 遍历根节点
        System.out.print(node.data + "->");
        // 遍历左子树
        preorder(node.left);
        // 遍历右子树
        preorder(node.right);
    }

2. 中序遍历

二叉树的中序遍历首先遍历左子树，然后是根节点，最后是右子树。

中序遍历的算法如下：

在左子树上调用中序遍历。
遍历根节点。
在右子树上调用中序遍历。

以上树的中序遍历结果为：

3 1 4 0 2

以下是Java代码示例：

static void inorder(TreeNode node) {
    if (node == null)
        return;

    // 遍历左子树
    inorder(node.left);
    // 遍历根节点
    System.out.print(node.item + "->");
    // 遍历右子树
    inorder(node.right);
}

3. 后序遍历

二叉树的后序遍历首先遍历左子树，然后遍历右子树，最后遍历根节点。

后序遍历的算法如下所示：

在左子树上调用后序遍历。
在右子树上调用后序遍历。
遍历根节点。

上述树的后序遍历是：

3 4 1 2 0

以下是Java代码：

static void postorder(TreeNode node) {
    if (node == null)
        return;

    // 遍历左子树
    postorder(node.left);
    // 遍历右子树
    postorder(node.right);
    // 遍历根节点
    System.out.print(node.item + "->");
}

4. 层次遍历

二叉树的层次遍历（也称为广度优先遍历）按照从上到下、从左到右的顺序逐层访问节点。

层次遍历通常使用队列来实现，算法如下：

将根节点放入队列。
当队列不为空时，执行以下操作：
1. 从队列中取出一个节点并访问。
2. 将该节点的左子节点（如果存在）放入队列。
3. 将该节点的右子节点（如果存在）放入队列。

以下是Java代码示例：

static 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.print(node.item + "->");
        
        if (node.left != null)
            queue.add(node.left);
            
        if (node.right != null)
            queue.add(node.right);
    }
}

层次遍历使用队列来跟踪待访问的节点。访问当前节点后，将其子节点按顺序加入队列。为了获取下一个要遍历的节点，我们从队列前端取出元素。

算法如下：

初始化一个空队列
将根节点加入队列
循环直到队列为空：
- 从队列中取出一个节点，记为temp
- 打印temp的数据
- 按照左右顺序将temp的子节点加入队列

上述树的层次遍历结果是：

0 1 2 3 4

以下是Java代码实现：

 static void printLevelOrder(TreeNode root) {
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.add(root);
       while (!queue.isEmpty()) {
           TreeNode temp = queue.poll();
           System.out.print(temp.data + " ");

           /*将左子节点加入队列 */
           if (temp.left != null) {
               queue.add(temp.left);
           }

           /*将右子节点加入队列 */
           if (temp.right != null) {
               queue.add(temp.right);
           }
       }
   }

在Java中完整实现BFS和DFS的代码示例

Java二叉树遍历完整代码实现

下面提供了完整的Java代码实现：

package com.JournalDev;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static class TreeNode {
        int data;
        TreeNode left, right;

        public TreeNode(int key) {
            data = key;
            left = right = null;
        }
    }

    // 前序遍历（深度优先搜索DFS的一种）
    static void preorder(TreeNode TreeNode) {
        if (TreeNode == null)
            return;

        // 遍历根节点
        System.out.print(TreeNode.data + " ");
        // 遍历左子树
        preorder(TreeNode.left);
        // 遍历右子树
        preorder(TreeNode.right);
    }

    // 中序遍历（深度优先搜索DFS的一种）
    static void inorder(TreeNode TreeNode) {
        if (TreeNode == null)
            return;

        // 遍历左子树
        inorder(TreeNode.left);
        // 遍历根节点
        System.out.print(TreeNode.data + " ");
        // 遍历右子树
        inorder(TreeNode.right);
    }

    // 后序遍历（深度优先搜索DFS的一种）
    static void postorder(TreeNode TreeNode) {
        if (TreeNode == null)
            return;

        // 遍历左子树
        postorder(TreeNode.left);
        // 遍历右子树
        postorder(TreeNode.right);
        // 遍历根节点
        System.out.print(TreeNode.data + " ");
    }
   
   // 层序遍历（广度优先搜索BFS的实现）
   static void printLevelOrder(TreeNode root) {
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.add(root);
       while (!queue.isEmpty()) {
           TreeNode tempNode = queue.poll();
           System.out.print(tempNode.data + " ");

           /*将左子节点添加到队列中*/
           if (tempNode.left != null) {
               queue.add(tempNode.left);
           }

           /*将右子节点添加到队列中*/
           if (tempNode.right != null) {
               queue.add(tempNode.right);
           }
       }
   }

    public static void main(String args[])
            
    {
        // 创建二叉树
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        
        // 执行各种遍历并输出结果
        System.out.println("中序遍历结果");
        inorder(root);

        System.out.println("\n前序遍历结果");
        preorder(root);

        System.out.println("\n后序遍历结果");
       postorder(root);

        System.out.println("\n层序遍历结果");
        printLevelOrder(root);

    }

}

程序输出结果：

输出结果：

中序遍历结果
3 1 4 0 2 
前序遍历结果
0 1 3 4 2 
后序遍历结果
3 4 1 2 0 
层序遍历结果
0 1 2 3 4

二叉树遍历示意图

结论

本教程详细介绍了二叉树中的广度优先搜索（BFS）和深度优先搜索（DFS）遍历方法。若需了解C++中深度优先搜索的实现，请参考相关教程。若需了解C++中层次遍历的实现，请参考相关教程。

#Java #二叉树 #广度优先搜索 #深度优先搜索 #算法