二叉樹的深度優先遍歷和廣度優先遍歷
** 深度優先搜索:深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中,當一個超鏈被選擇後,被鏈接的HTML文件將執行深度優先搜索,即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止,然後返回到某一個HTML文件,再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時,說明搜索已經結束。**
**寬度優先搜索:寬度優先搜索演算法(又稱廣度優先搜索)是最簡便的圖的搜索演算法之一,這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS,屬於一種盲目搜尋法,目的是系統地展開並檢查圖中的所有節點,以找尋結果。換句話說,它並不考慮結果的可能位置,徹底地搜索整張圖,直到找到結果為止。**
兩者分別結合棧、隊列實現
一、生成二叉樹
二、編寫一個Node類
package com.lzp.util.tree;
/**
* @Author LZP
* @Date 2021/2/22 12:53
* @Version 1.0
*/
public class Node {
/**
* 左孩子
*/
public Node left;
/**
* 右孩子
*/
public Node right;
/**
* 當前節點的值
*/
public char data;
public Node(Node left, Node right, char data) {
this.left = left;
this.right = right;
this.data = data;
}
}
三、編寫一個BTreeUtil工具類
package com.lzp.util.tree;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;
/**
* @Author LZP
* @Date 2021/2/22 8:34
* @Version 1.0
*
* 二叉樹
*/
public class BTreeUtil {
/**
* 創建二叉樹
* @param arr 用於存儲待創建二叉樹中所有值的字元數組
* @return 返回根節點
*/
public static Node createBinaryTree(char[] arr) {
Node root = null;
for (int i = 0; i < arr.length; i++) {
Node newNode = null;
if (root == null) {
root = new Node(null, null, arr[i]);
continue;
}
if (!contains(root, arr[i])) {
newNode = new Node(null, null, arr[i]);
insertBinaryTreeNode(root, newNode);
}
}
return root;
}
/**
* 判斷二叉樹中是否包含指定字元
* @param root 根節點
* @param c 待判斷字元
* @return
*/
public static boolean contains(Node root, char c) {
Queue<Node> queue = new ArrayBlockingQueue<Node>(10);
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node != null) {
if (node.data == c) {
return true;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return false;
}
/**
* 通過BFS方式向二叉樹中插入節點
* @param root 根節點
* @param c 待插入節點的值
*/
public static boolean insertBinaryTreeNode(Node root, char c) {
if (!contains(root, c)) {
Node newNode = new Node(null, null, c);
return insertBinaryTreeNode(root, newNode);
}
return false;
}
/**
* 通過BFS方式向二叉樹中插入節點
* @param root 根節點
* @param node 待插入節點
*/
public static boolean insertBinaryTreeNode(Node root, Node node) {
Queue<Node> queue = new ArrayBlockingQueue<Node>(10);
queue.offer(root);
while (!queue.isEmpty()) {
Node temp = queue.poll();
if (temp != null) {
if (temp.left == null) {
temp.left = node;
// 記住,這裡是插入節點,一旦插入成功就直接返回,不用再循環
return true;
} else {
if (temp.right == null) {
temp.right = node;
// 記住,這裡是插入節點,一旦插入成功就直接返回,不用再循環
return true;
} else {
// 將左右孩子都入隊
queue.offer(temp.left);
queue.offer(temp.right);
}
}
}
}
return false;
}
/**
* 深度優先遍歷
* 遞歸實現
* @param root 根節點
*/
public static void dfsDivision(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + "\t");
dfsDivision(root.left);
dfsDivision(root.right);
}
/**
* 深度優先遍歷
* 迭代實現
* @param root
*/
public static void dfsIterator(Node root) {
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
if (root != null) {
System.out.print(root.data + "\t");
// 先將右孩子入棧,這裡是跟廣度優先遍歷中的隊列入隊剛好相反
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
}
}
/**
* 廣度優先遍歷:廣度優先遍歷,也可以稱為層次優先遍歷,從上到下,先把每一層遍歷完之後再遍歷一下一層
* @param root 根節點
*/
public static void bfs(Node root) {
Queue<Node> queue = new ArrayBlockingQueue<Node>(10);
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node != null) {
System.out.print(node.data + "\t");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
}
四、測試類
public class Test {
public static void main(String[] args) {
char[] cArr = new char[]{
'B',
'F',
'A',
'C',
'E',
'G',
'D'};
Node root = BTreeUtil.createBinaryTree(cArr);
System.out.println("深度優先遍歷");
BTreeUtil.dfsIterator(root);
System.out.println();
System.out.println("廣度優先遍歷");
BTreeUtil.bfs(root);
}
}
五、運行結果