樹深度優先遍歷演算法

『壹』 JS樹結構數據的遍歷

title: JS樹結構數據的遍歷
date: 2022-04-14
description: 針對項目中出現樹形結構數據的時候，我們怎樣去操作他

項目中我們會經常出現對樹形結構的遍歷、查找和轉換的場景，比如說DOM樹、族譜、社會機構、組織架構、許可權、菜單、省市區、路由、標簽等等。那針對這些場景和數據，我們又如何去遍歷和操作，有什麼方式或者技巧可以簡化我們的實現思路。下面我們將針對常規出現的場景去總結一下我們的遍歷方式

樹的特點
1、每個節點都只有有限個子節點或無子節點；
2、沒有父節點的節點稱為根節點；
3、每一個非根節點有且只有一個父節點；
4、除了根節點外，每個子節點可以分為多個不相交的子樹；
5、樹裡面沒有環路

下面的圖片表示一顆樹

在下面的JS中我們由多棵樹組成我們的數據

在這數據中我們如何評判數據是否為葉節點（也就是最後一級），我們每個節點都會存在children屬性，如果不存在children屬性或者children不是一個數組或者children為數組且長度為0我們則認為他是一個葉節點

我們針對樹結構的操作離不開遍歷，遍歷的話又分為廣度優先遍歷、深度優先遍歷。其中深度優先遍歷可以通過遞歸和循環的方式實現，而廣度優先遍歷的話是非遞歸的

從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。即訪問樹結構的第n+1層前必須先訪問完第n層。

簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。

所以我們的實現思路是，維護一個隊列，隊列的初始值為樹結構根節點組成的列表，重復執行以下步驟直到隊列為空：
取出隊列中的第一個元素，進行訪問相關操作，然後將其後代元素（如果有）全部追加到隊列最後。

深度優先搜索演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜索樹或圖的演算法。這個演算法會盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止

1、先序遍歷
訪問子樹的時候，先訪問根再訪問根的子樹

2、後序遍歷
訪問子樹的時候，先訪問子樹再訪問根

1、先序遍歷
先序遍歷與廣度優先循環實現類似，要維護一個隊列，不同的是子節點不追加到隊列最後，而是加到隊列最前面

2、後序遍歷
後序遍歷就略微復雜一點，我們需要不斷將子樹擴展到根節點前面去，執行列表遍歷，並且通過一個臨時對象維護一個id列表，當遍歷到某個節點如果它沒有子節點或者它本身已經存在於我們的臨時id列表，則執行訪問操作，否則繼續擴展子節點到當前節點前面

對於樹結構的遍歷操作，其實遞歸是最基礎，也是最容易理解的。遞歸本身就是循環的思想，所以可以用循環來改寫遞歸,以上的方式在項目中已經廊括了大部分的場景了，我們在日常開發中可以根據場景或者需要去選擇我們的遍歷方式，或者基於此對他進行調整和優化，至於每種方式的空間復雜度和時間復雜度我們在這個地方就不去嘗試了，各位感興趣可以自己去驗證。

廣度優先搜索

樹的遍歷

深度優先搜索

圖文詳解兩種演算法：深度優先遍歷（DFS）和廣度優先遍歷（BFS）

二叉樹遍歷（前序，後序，中序，層次）遞歸與迭代實現JavaScript

JS樹結構操作:查找、遍歷、篩選、樹和列表相互轉換

『貳』 深度優先演算法的定義

深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬於盲目搜索。
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明「深度優先搜索演算法」，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎.

『叄』 用鄰接表表示圖進行深度優先遍歷時，通常採用（）來實現演算法

使用棧來實現演算法。

用鄰接表表示圖進行深度優先遍歷時，通常採用棧來實現演算法，廣度遍歷使用隊列。

擴展材料：

深度優先遍歷：類似與樹的前序遍歷。從圖中的某個頂點v出發，訪問此頂點，然後從v的未被訪問到的鄰接點進行遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到

註：優先訪問外層節點，訪問到無新頂點時，會進行回退，訪問未被訪問過的分支頂點。

廣度優先遍歷：類似於樹的層序遍歷。從圖中的某個頂點w出發，讓頂點w入隊，然後頂點w再出隊，並讓所有和頂點w相連的頂點入隊，然後再出隊一個頂點t，並讓所有和t相連但未被訪問過的頂點入隊……由此循環，指定圖中所有元素都出隊。

參考資料來源：

知網論文-數據結構中圖的遍歷演算法研究

『肆』 簡述深度優先搜索遍歷的方法。

簡述深度優先搜索遍歷的方法？深度優先搜索演算法(Depth-First-Search, DFS)，最初是一種用於遍歷或搜索樹和圖的演算法，在LeetCode中很常見，雖然感覺不難，但是理解起來還是有點難度的。

簡要概括，深度優先的主要思想就是「不撞南牆不回頭」，「一條路走到黑」，如果遇到「牆」或者「無路可走」時再去走下一條路。

思路
假如對樹進行遍歷，沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支，當達到邊際時回溯上一個節點再進行搜索。如下圖的一個二叉樹。


首先給出這個二叉樹的深度優先遍歷的結果(假定先走左子樹)：1->2->4->5->3->6->7

那是怎樣得到這樣的結果呢？
根據深度優先遍歷的概念：沿著這樹的某一分支向下遍歷到不能再深入為止，之後進行回溯再褲罩搭選定新的分支。

定義節點

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
遞歸的方式

分別對左右子樹進行遞歸，一直到底才進行回溯。如果不了解遞歸可以參考我的博客你真胡拿的懂悶褲遞歸嗎？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面實現了遞歸方式的深度優先遍歷，也可以利用棧把遞歸轉換為迭代的方式。

但是為了保證出棧的順序，需要先壓入右節點，再壓左節點。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接著再列舉個利用深度優先遍歷的方式的題目

掃雷
給定一個表示游戲板的二維字元矩陣，'M'表示一個未挖出的地雷，'E'表示一個未挖出的空方塊，'B' 代表沒有相鄰（上，下，左，右，和所有4個對角線）地雷的已挖出的空白方塊，數字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰，'X' 則表示一個已挖出的地雷。

根據以下規則，返回相應位置被點擊後對應的面板：

如果一個地雷（'M'）被挖出，游戲就結束了- 把它改為'X'。
如果一個沒有相鄰地雷的空方塊（'E'）被挖出，修改它為（'B'），並且所有和其相鄰的方塊都應該被遞歸地揭露。
如果一個至少與一個地雷相鄰的空方塊（'E'）被挖出，修改它為數字（'1'到'8'），表示相鄰地雷的數量。
如果在此次點擊中，若無更多方塊可被揭露，則返回面板。
示例

輸入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

輸出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根據給定的規則，當給定一個Click坐標，當不為雷的時候以此坐標為基點向四周8個方向進行深度遍歷，把空格E填充為B，並且把與地雷M相連的空方塊標記相鄰地雷的數量。

注意 ：



在這個題中可以沿著8個方向遞歸遍歷，所有要注意程序中，採用了兩個for循環可以實現向8個方向遞歸。

『伍』 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。

『陸』 二叉樹的深度怎麼算

二叉樹的深度計算，首先要判斷節點，以下是計算二叉樹的詳細步驟：

1、一顆樹只有一個節點，它的深度是1；

2、二叉樹的根節點只有左子樹而沒有右子樹，那麼可以判斷，二叉樹的深度應該是其左子樹的深度加1；

3、二叉樹的根節點只有右子樹而沒有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其右樹的深度加1；

4、二叉樹的根節點既有右子樹又有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其左右子樹的深度較大值加1。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。

具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節點，至多有2k-1個節點。

5、有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編號則 如果I>1，則其父結點的編號為I/2；

如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左孩子；