文章目錄

• 使用樹理解深度優(yōu)先和廣度優(yōu)先
• 層次遍歷分析
• Code

---

使用樹理解深度優(yōu)先和廣度優(yōu)先

我們上篇博文中 Algorithms_二叉樹的前序遍歷、中序遍歷、后續(xù)遍歷(深度優(yōu)先） ，本質(zhì)上是深度優(yōu)先。 為什么這么說呢？ 我們來看下

5 / \ 3 6 / \ \ 2 4 8

前序遍歷： 5 、3、2、4、6、8

中序遍歷： 2、3、4、5、6、8

后序遍歷 ： 2、4、3、8、6、5

不管是前序、中序還是后序都會(huì)先把左子樹遍歷到?jīng)]有元素，然后再遍歷右子樹到?jīng)]有元素， 都是先順著一個(gè)枝杈往最深的地方走。

而層次遍歷呢？ （廣度優(yōu)先）

5 先遍歷第0層的數(shù)據(jù)--------------------------------------- / \ 3 6 然后遍歷第1層的數(shù)據(jù)---------------------------------------/ \ \ 2 4 8 再遍歷第2層的數(shù)據(jù)---------------------------------------

層次遍歷的輸出如下： 5、3、6、2、4、8

我們遍歷的數(shù)據(jù)使用逐層遍歷的方式，本質(zhì)上是一種廣度優(yōu)先的遍歷。

---

層次遍歷分析

層次遍歷的方式，通常使用的不是遞歸的方式來實(shí)現(xiàn)的，一般都會(huì)借用隊(duì)列。 從根節(jié)點(diǎn)開始排著隊(duì)的進(jìn)入到隊(duì)列中

5 先遍歷第0層的數(shù)據(jù)--------------------------------------- / \ 3 6 然后遍歷第1層的數(shù)據(jù)---------------------------------------/ \ \ 2 4 8 再遍歷第2層的數(shù)據(jù)---------------------------------------

我們逐步來分析一下

根節(jié)點(diǎn)不為空的話，將根節(jié)點(diǎn)5入隊(duì)

訪問根節(jié)點(diǎn)5 ，然后將 5 的 左右孩子 3 和 6 入隊(duì) --------> 5

訪問左孩子3 ，這個(gè)時(shí)候判斷下 3是否有左右孩子，有的話將2和4 入隊(duì) ------>5 3

這個(gè)時(shí)候隊(duì)列中有 6 、2、4 ,訪問6 ------> 5 3 6

看下6的左右孩子，有的話入隊(duì)，這個(gè)時(shí)候隊(duì)列中有 2 、4 、8

訪問 2 ，看下2還有沒有左右孩子，沒有 ------> 5 3 6 2

訪問 4 看下4 還有沒有左右孩子，沒有 ------> 5 3 6 2 4

訪問 8 看下8 還有沒有左右孩子，沒有 ------> 5 3 6 2 4 8

整個(gè)隊(duì)列為空，廣度優(yōu)先遍歷結(jié)束。

---

Code

/*** * * @Title: levelScan* * @Description: 二分搜索樹的層序遍歷* * * @return: void*/public void levelScan() {Queue<Node> queue = new LinkedList<>();queue.offer(root);// 把root入隊(duì)while (!queue.isEmpty()) {Node currentNode = queue.remove();// 移除并返回System.out.println(currentNode.e);if (currentNode.left != null) {queue.add(currentNode.left);}if (currentNode.right != null) {queue.add(currentNode.right);}}}

測試下

public static void main(String[] args) {BinarySearchTree<Integer> bst = new BinarySearchTree<>();int[] nums = { 5, 3, 6, 8, 4, 2 };for (int num : nums) {bst.add(num);}// bst.preOrder();// System.out.println("============================");// bst.preOrderNR();// System.out.println("============================");bst.levelScan();}

總結(jié)

以上是生活随笔為你收集整理的Algorithms_二叉树的层次遍历(广度优先）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。