在Java中，使用广度优先搜索（BFS）和深度优先搜索（DFS）来遍历二叉树

2 年 ago

科, 颖

3 minutes

广度优先搜索（Breadth-First Search）和深度优先搜索（Depth-First Search）是遍历图和树的两种技术。在本教程中，我们将主要关注树中的广度优先搜索（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()。

上面树的前序遍历为：

0 1 3 4 2

以下是Java代码：

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

        // Traverse root
        System.out.print(TreeNode.item + "->");
        // Traverse left
        preorder(TreeNode.left);
        // Traverse right
        preorder(TreeNode.right);
    }

2. 中序遍历

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

中序遍历的算法如下：

在右子树上调用中序遍历。

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

3 1 4 0 2

以下是Java代码示例：

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

        // Traverse left
        inorder(TreeNode.left);
        // Traverse root
        System.out.print(TreeNode.item + "->");
        // Traverse right
        inorder(TreeNode.right);
    }

3. 后序遍历 xù lì)

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

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

遍历根节点。

上述树的后序遍历是：

3 4 1 2 0

以下是Java代码：

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

        // Traverse left
        postorder(TreeNode.left);
        // Traverse right
        postorder(TreeNode.right);
        // Traverse root
        System.out.print(TreeNode.item + "->");
    }

4. 层次遍历

层次遍历使用队列来跟踪要访问的节点。在访问节点之后，将其子节点放入队列中。要获取要遍历的新节点，我们从队列中取出元素。

算法如下：

打印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 + " ");

           /*add left child to the queue */
           if (temp.left != null) {
               queue.add(temp.left);
           }

           /*add right right child to the queue */
           if (temp.right != null) {
               queue.add(temp.right);
           }
       }
   }

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

下面提供了完整的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;
        }
    }

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

        // Traverse root
        System.out.print(TreeNode.data + " ");
        // Traverse left
        preorder(TreeNode.left);
        // Traverse right
        preorder(TreeNode.right);
    }

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

        // Traverse left
        inorder(TreeNode.left);
        // Traverse root
        System.out.print(TreeNode.data + " ");
        // Traverse right
        inorder(TreeNode.right);
    }

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

        // Traverse left
        postorder(TreeNode.left);
        // Traverse right
        postorder(TreeNode.right);
        // Traverse root
        System.out.print(TreeNode.data + " ");
    }
   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 + " ");

           /*add left child to the queue */
           if (tempNode.left != null) {
               queue.add(tempNode.left);
           }

           /*add right right child to the queue */
           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 traversal");
        inorder(root);

        System.out.println("\nPreorder traversal ");
        preorder(root);

        System.out.println("\nPostorder traversal");
       postorder(root);

        System.out.println("\nLevelorder traversal");
        printLevelOrder(root);

    }

}

Output : 

Inorder traversal
3 1 4 0 2 
Preorder traversal 
0 1 3 4 2 
Postorder traversal
3 4 1 2 0 
Levelorder traversal
0 1 2 3 4

结论是

本教程介绍了二叉树中的广度优先搜索(BFS)和深度优先搜索(DFS)遍历。若需了解C++中DFS的实现，请参考此教程。若需了解C++中层次遍历的实现，请参考这篇教程。