python遍歷樹

① python數據結構-隊列與廣度優先搜索（Queue）

隊列（Queue） ：簡稱為隊，一種線性表數據結構，是一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。
我們把隊列中允許插入的一端稱為 「隊尾（rear）」 ；把允許刪除的另一端稱為 「隊頭（front）」 。當表中沒有任何數據元素時，稱之為 「空隊」 。

廣度優先搜索演算法（Breadth First Search） ：簡稱為 BFS，又譯作寬度優先搜索 / 橫向優先搜索。是一種用於遍歷或搜索樹或圖的演算法。該演算法從根節點開始，沿著樹的寬度遍歷樹或圖的節點。如果所有節點均被訪問，則演算法中止。

廣度優先遍歷 類似於樹的層次遍歷過程 。呈現出一層一層向外擴張的特點。先看到的節點先訪問，後看到的節點後訪問。遍歷到的節點順序符合「先進先出」的特點，所以廣度優先搜索可以通過「隊列」來實現。

力扣933

游戲時，隊首始終是持有土豆的人
模擬游戲開始，隊首的人出隊，之後再到隊尾（類似於循環隊列）
傳遞了num次之後，將隊首的人移除
如此反復，直到隊列中剩餘一人

多人共用一台列印機，採取「先到先服務」的隊列策略來執行列印任務
需要解決的問題：1 列印系統的容量是多少？2 在能夠接受的等待時間內，系統可容納多少用戶以多高的頻率提交列印任務？

輸入：abba
輸出：False
思路：1 先將需要判定的詞從隊尾加入 deque; 2從兩端同時移除字元並判斷是否相同，直到deque中剩餘0個（偶數）或1個字元（奇數）

內容參考： https://algo.itcharge.cn/04.%E9%98%9F%E5%88%97/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/

② Python演算法系列—深度優先遍歷演算法

一、什麼是深度優先遍歷
深度優先遍歷演算法是經典的圖論演算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷演算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。

二、二叉樹

2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。

空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.

註：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
術語 解釋
度 節點的度為節點的子樹個數
葉子節點 度為零的節點
分支節點 度不為零的節點
孩子節點 節點下的兩個子節點
雙親節點 節點上一層的源節點
兄弟節點 擁有同一雙親節點的節點
根 二叉樹的源頭節點
深度 二叉樹中節點的層的數量

DLR（先序）：
LDR（中序）：
LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根

6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題+勵志
企鵝運維面試題：
1.二叉樹遍歷順序：看上文
2.用你熟悉的語言說說怎麼創建二叉樹？ python看上文

③ Python 二叉樹的創建和遍歷、重建

幾個有限元素的集合，該集合為空或者由一個根（Root）的元素及兩不相交的（左子樹和右子樹）的二叉樹組成，是有序樹，當集合為空時，稱為空二叉樹，在二叉樹中，一個元素也稱為一個結點。

前序遍歷：若二叉樹為空，則空操作返回，否則先訪問根結點，然後前序遍歷左子樹，再前序遍歷右子樹

中序遍歷：若樹為空，則空操作返回，否則從根結點開始（不是先訪問根結點），中序遍歷根結點的左子樹，然後訪問根節點，最後中序遍歷右子樹。

後序遍歷：若樹為空，則空操作返回，否則從左到右先訪問葉子結點後結點的方式遍歷左右子樹，最後訪問根節點。

層序遍歷：若樹為空，則空操作返回，否則從樹的每一層，即從根節點開始訪問，從上到下逐層遍歷，在同一層中，按從左到右的順序對結點逐個訪問。

假設已知後序遍歷和中序遍歷結果，從後序遍歷的結果可以等到最後一個訪問的結點是根節點，對於最簡單的二叉樹，此時在中序遍歷中找到根節點之後，可以分辨出左右子樹，這樣就可以重建出這個最簡單的二叉樹了。而對於更為復雜的二叉樹，重建得到根結點和暫時混亂的左右結點，通過遞歸將左右結點依次重建為子二叉樹，即可完成整個二叉樹的重建。（在得到根結點之後，需要在中序遍歷序列中尋找根結點的位置，並將中序序列拆分為左右部分，所以要求序列中不能有相同的數字，這是序列重建為二叉樹的前提。）

Root =None

strs="abc##d##e##"   #前序遍歷擴展的二叉樹序列

vals =list(strs)

Roots=Create_Tree(Root,vals)#Roots就是我們要的二叉樹的根節點。

print(Roots)

inorderSearch = inOrderTraverse2(Roots)

print(inorderSearch)

④ 圖遍歷演算法之DFS/BFS

在計算機科學， 圖遍歷（Tree Traversal，也稱圖搜索）是一系列圖搜索的演算法， 是單次訪問樹結構類型數據（tree data structure)中每個節點以便檢查或更新的一系列機制。圖遍歷演算法可以按照節點訪問順序進行分類，根據訪問目的或使用場景的不同，演算法大致可分為28種：

圖遍歷即以特定方式訪問圖中所有節點，給定節點下有多種可能的搜索路徑。假定以順序方式進行（非並行），還未訪問的節點就需通過堆棧（LIFO）或隊列（FIFO）規則來確定訪問先後。由於樹結構是一種遞歸的數據結構，在清晰的定義下，未訪問節點可存儲在調用堆棧中。本文介紹了圖遍歷領域最流行的廣度優先搜索演算法BFS和深度優先搜索演算法DFS，對其原理、應用及實現進行了闡述。通常意義上而言，深度優先搜索（DFS）通過遞歸調用堆棧比較容易實現，廣義優先搜索通過隊列實現。

深度優先搜索（DFS）是用於遍歷或搜索圖數據結構的演算法，該演算法從根節點開始（圖搜索時可選擇任意節點作為根節點）沿著每個分支進行搜索，分支搜索結束後在進行回溯。在進入下一節點之前，樹的搜索盡可能的加深。
DFS的搜索演算法如下（以二叉樹為例）：假定根節點（圖的任意節點可作為根節點）標記為 ,
(L) : 遞歸遍歷左子樹，並在節點 結束。
(R): 遞歸遍歷右子樹，並在節點 結束。
(N): 訪問節點 。
這些步驟可以以任意次序排列。如果（L）在（R）之前，則該過程稱為從左到右的遍歷；反之，則稱為從右到左的遍歷。根據訪問次序的不同，深度優先搜索可分為 pre-order、in-order、out-order以及post-order遍歷方式。

（a）檢查當前節點是否為空；
（b）展示根節點或當前節點數據；
（c）遞歸調用pre-order函數遍歷左子樹；
（d）遞歸調用pre-order函數遍歷右子樹。
pre-order遍歷屬於拓撲排序後的遍歷，父節點總是在任何子節點之前被訪問。該遍歷方式的圖示如下：

遍歷次序依次為：F -B -A-D- C-E-G- I-H.

（a）檢查當前節點是否為空；
（b）遞歸調用in-order函數遍歷左子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用in-order函數遍歷右子樹。
在二叉樹搜索中，in-order遍歷以排序順序訪問節點數據。該遍歷方式的圖示如下：

遍歷次序依次為：A -B - C - D - E - F - G -H-I

（a）檢查當前節點是否為空；
（b）遞歸調用out-order函數遍歷右子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用out-order函數遍歷左子樹。
該遍歷方式與LNR類似，但先遍歷右子樹後遍歷左子樹。仍然以圖2為例，遍歷次序依次為：H- I-G- F- B- E- D- C- A.

（a）檢查當前節點是否為空；
（b）遞歸調用post-order函數遍歷左子樹；
（c）遞歸調用post-order函數遍歷右子樹；
（d）展示根節點或當前節點數據。
post-order遍歷圖示如下：

遍歷次序依次為：A-C-E-D-B-H-I-G-F.

pre-order遍歷方式使用場景：用於創建樹或圖的副本；
in-order遍歷使用場景：二叉樹遍歷；
post-order遍歷使用場景：刪除樹

遍歷追蹤也稱樹的序列化，是所訪問根節點列表。無論是pre-order，in-order或是post-order都無法完整的描述樹特性。給定含有不同元素的樹結構，pre-order或post-order與in-order遍歷方式結合起來使用才可以描述樹的獨特性。

樹或圖形的訪問也可以按照節點所處的級別進行遍歷。在每次訪問下一層級節點之前，遍歷所在高層級的所有節點。BFS從根節點（圖的任意節點可作為根節點）出發，在移動到下一節點之前訪問所有相同深度水平的相鄰節點。

BFS的遍歷方法圖示如下：

遍歷次序依次為： F-B-G-A-D-I-C-E-H.

圖演算法相關的R包為igraph，主要包括圖的生成、圖計算等一系列演算法的實現。

使用方法：

參數說明：

示例：

結果展示：

DFS R輸出節點排序：

使用方法：

參數含義同dfs
示例：

結果展示：

BFS R輸出節點排序：

以尋找兩點之間的路徑為例，分別展示BFS及DFS的實現。圖示例如下：

示例：

輸出結果：

示例：

輸出結果：

[1] 維基網路： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in Python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

⑤ python列印二叉樹所有路徑的主函數怎樣寫

基本演算法就是二叉樹的遍歷，首先想到的是深度優先遍歷。
難點在於，如何實現每個子路徑的記錄和append
binaryTreePaths函數只給了root變數，無法存儲每個子路徑，考慮寫輔助函數res，添加存儲路徑的變數
res(root,temp)
同時還需要一個全局變數result存儲最後的輸出結果，result.append(temp)