Java的广度优先遍历和深度优先遍历

2023-07-29 23:38:16

1. 广度优先遍历

1.1 原理

【写在前面】

今天对广度优先遍历和深度优先遍历做了一些了解和汇总，这里做个学习笔记，便于后续深入学习。知识点和思路，参考文章如链接，可直接看原博文：树的广度优先遍历和深度优先遍历，Java实现二叉树的深度优先遍历和广度优先遍历算法示例

1. 广度优先遍历

1.1 原理

英文缩写为BFS，即Breadth FirstSearch。

是以广度为优先的，一层一层搜索下去的，就像病毒感染，扩散性的传播下去。其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。

广度优先遍历树，需要用到队列（Queue）来存储节点对象, 队列的特点就是先进先出。

先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。

1.2 代码示例

（1）树节点：TreeNode

//树节点
package MySearchMethod;

public class TreeNode{
    Integer val;
    TreeNode left;
    TreeNode right;

    public TreeNode(Integer val){
        this.val = val;
        left = null;
        right = null;
    }
}

（2）二叉树：BinaryTree

//构建二叉树
package MySearchMethod;

public class BinaryTree<T> {
    private TreeNode root;
    BinaryTree(){
        root = null;
    }

    public void insertTreeNode(Integer val){
        if(root == null){
            root = new TreeNode(val);
            return;
        }
        TreeNode currentNode = root;
        while(true){
            if(val.compareTo(currentNode.val) > 0){
                if(currentNode.right == null){
                    currentNode.right = new TreeNode(val);
                    break;
                }
                currentNode = currentNode.right;
            }else {
                if(currentNode.left == null){
                    currentNode.left = new TreeNode(val);
                    break;
                }
                currentNode = currentNode.left;
            }
        }
    }
    public TreeNode getRoot(){
        return root;
    }
}

（3）广度优先遍历：

注：下方遍历方法应该也适用于其他树，不只二叉树。待研究。

/**
 * 广度优先遍历，非递归
 */

package MySearchMethod;

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

public class BreadthFirstSearch {

    public static void main(String[] args){
        BinaryTree<Integer> tree = new BinaryTree<>();
        tree.insertTreeNode(35);
        tree.insertTreeNode(20);
        tree.insertTreeNode(15);
        tree.insertTreeNode(16);
        tree.insertTreeNode(29);
        tree.insertTreeNode(28);
        tree.insertTreeNode(30);
        tree.insertTreeNode(40);
        tree.insertTreeNode(50);
        tree.insertTreeNode(45);
        tree.insertTreeNode(55);

        System.out.println("深度优先算法（非递归）：");
        breadthSearch(tree.getRoot());

    }

   public static void breadthSearch(TreeNode root){
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.offer(root);
       TreeNode currentNode;
       while(!queue.isEmpty()){
           currentNode = queue.poll();
           System.out.print(currentNode.val + "  ");

           if(currentNode.left != null){
               queue.offer(currentNode.left);
           }
           if(currentNode.right != queue){
               queue.offer(currentNode.right);
           }
       }
   }
}

遍历结果：

有一个空指针异常的报错，还没找到原因。待补。

深度优先算法（非递归）：
35  20  40  15  29  50  16  28  30  45  55  Exception in thread "main" java.lang.NullPointerException
	at MySearchMethod.BreadthFirstSearch.breadthSearch(BreadthFirstSearch.java:37)
	at MySearchMethod.BreadthFirstSearch.main(BreadthFirstSearch.java:27)

Process finished with exit code 1

2. 深度优先遍历

2.1 原理

英文缩写为DFS，即Depth First Search。

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。stack的特点是是先进后出。整个遍历过程如下：先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。

对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。

这里先演示先序遍历的情况。

1.2 代码示例

（1）树节点：TreeNode。如上，略。

（2）二叉树：BinaryTree。如上，略。

（3）深度优先遍历：

注：这里先演示先序遍历的情况。其他情况待补。

/**
 * 深度优先遍历，非递归
 */
package MySearchMethod;

import java.util.Stack;

public class DepthFirstSearch {
    public static void main(String[] args){
        BinaryTree<Integer> tree = new BinaryTree<>();
        tree.insertTreeNode(35);
        tree.insertTreeNode(20);
        tree.insertTreeNode(15);
        tree.insertTreeNode(16);
        tree.insertTreeNode(29);
        tree.insertTreeNode(28);
        tree.insertTreeNode(30);
        tree.insertTreeNode(40);
        tree.insertTreeNode(50);
        tree.insertTreeNode(45);
        tree.insertTreeNode(55);

        System.out.println("深度优先算法之先序遍历（非递归）：");
        depthSearch(tree.getRoot());
    }

    public static void depthSearch(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode currentNode;
        while (!stack.isEmpty()){
            currentNode = stack.pop();
            System.out.print(currentNode.val + "  ");
            if(currentNode.right != null){
                stack.push(currentNode.right);
            }
            if(currentNode.left != null){
                stack.push(currentNode.left);
            }
        }
    }
}

遍历结果：

深度优先算法之先序遍历（非递归）：
35  20  15  16  29  28  30  40  50  45  55  
Process finished with exit code 0

码农公寓

1. 广度优先遍历

1.1 原理

1.2 代码示例

2. 深度优先遍历

2.1 原理

1.2 代码示例

相关文章