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

什么是深度优先搜索(DFS)？

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

对于二叉树，有三种类型的DFS遍历。

• In-Order
• Pre-Order
• Post-Order

什么是广度优先搜索(BFS)？

该算法也从根节点开始，然后逐级访问所有节点。
这意味着在根之后，它将遍历根的所有直接子代。
遍历了根的所有直接子代后，它移到了他们的子代，依此类推。
为了实现BFS，我们使用队列。

对于二叉树，我们遵循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 TreeNode) {
      if (TreeNode == null)
          return;

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

2.有序遍历

按顺序遍历二叉树首先遍历左子树，然后遍历根，最后遍历右子树。

有序遍历的算法如下：

• 在左侧子树上调用inorder()。

• 遍历根。

• 在右侧子树上调用inorder()。

上面的树的有序遍历为：

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.订单遍历

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

后遍历的算法如下：

• 在左侧子树上调用postorder()。

• 在右侧子树上调用postorder()。

• 遍历根。

上面树的后遍历为：

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设置为root

• 运行循环，直到队列不为空从临时打印数据。

• 按从左到右的顺序排列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.theitroad;
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