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

目录

1. 广度优先遍历

1.1 原理

1.2 代码示例

2. 深度优先遍历

2.1 原理

1.2 代码示例


【写在前面】

今天对广度优先遍历和深度优先遍历做了一些了解和汇总,这里做个学习笔记,便于后续深入学习。知识点和思路,参考文章如链接,可直接看原博文:树的广度优先遍历和深度优先遍历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
上一篇:Java Case Study 3


下一篇:五子棋html游戏代码与算法介绍