上篇

資料結構系列：樹？二叉樹？有一說一，這倆貨你不會真的不行

，我們簡單的分享了樹結構的一般特點和二叉樹結構相關的特性和實現，本篇將基於二叉樹分享相關的遍歷方法（前序，中序，後序，層序），以及部分應用的演算法。

01

瞭解二叉樹的遍歷

我們知道，線性表的遍歷，我們可以透過for迴圈或者迭代器。而樹的遍歷，明顯不太可能以相同的方式進行，畢竟

樹結構抽象的是層級結構。

二叉樹的遍歷從宏觀的大角度看，分為

深度優先遍歷

（前序，中序，後序），

廣度優先遍歷(

層級），如圖

概括地說：

深度優先遍歷主要包括前序遍歷，中序遍歷，以及後序遍歷，廣度優先遍歷主要是指層級遍歷

（每遍歷完整層再遍歷下一層，這裡都是以從左往右的順序進行元素的遍歷）。

對於3種深度優先遍歷來講，最簡單的理解方法就是：

將當前節點，當前節點的父節點，當前節點的子節點當作一個整體看

，分別判斷左中右的順序，

這樣其實就很好理解。

比如說：中序遍歷（左中右的順序），

也就是先從最左邊的最左節點開始，然後此子樹的中間節點（當前樹的根節點），然後此子樹的右節點，此時這棵左子樹已經遍歷完成，把當前遍歷完成的左子樹看作一個整體，找到這棵樹是哪個結點的左子節點，然後遍歷此左子節點的中間節點

，以此類推。

下面分享這幾種不同的遍歷方法及實現

02

前序遍歷（根->左->右）

前序理解

若二叉樹為空，則直接返回；否則按照根節點，然後左子樹，右子樹的順序依次訪問（解釋：每訪問一個節點，就把當前節點當作根節點，然後找左右子節點，如果有左節點，則把左節點當作當前樹的根結點，繼續找左右子節點……）

前序實現

03

中序遍歷（左->根->右）

中序理解

樹為空，直接返回；否則就從根節點開始（但並不是以根節點開始訪問），找到最最最左子節點開始，然後當前左子節點的父節點，然後右節點，結果如下

中序實現(基於遞迴)

04

後序遍歷

後序理解

若樹為空，則直接返回；否則先遍歷左子樹，然後右子樹，最後訪問根節點，結果如下

後序實現(基於遞迴)

05

層序遍歷

層序理解

這個最簡單：從每一層開始，按照從左往右的順序遍歷結點

層序實現

說到這，二叉樹的幾種遍歷就差不多結束了，接下來我們分享幾個重要的基於二叉樹的應用

06

堆（heap）

概念

堆排序是高效排序演算法的一個解決方案，它的主要優點是，無論輸入資料如何，它的最壞情況執行時間都是O（n*logn）。

堆排序是優先佇列最主要的實現方法

特點

有這樣一個特點（堆次序）：任何一條路徑都是已經排好序的有序數列

最小堆

每個節點的資料項都小於或等於其兩個子節點資料，最小的項位於根節點

最大堆

每個節點的資料項都大於等於其兩個子節點的資料，最大的項位於根節點

堆結構一般有如下幾個介面

heap。is_empty（） - 堆是否為空堆，返回布林值

heap。heappush（item） - 增加資料到堆結構

heap。heappop（） - 返回heap最頂部的資料，並刪除

heap。peek（） - 返回heap最頂端的項

我們這裡都基於陣列實現堆結構，因為對於陣列（這裡引申為python的列表）來講，在一個列表中，父節點和子節點的索引存在著一定的關係（如果專門儲存一個空元素給列表的第一個位置，那麼子節點的索引永遠等於父節點地板除2的值）

實現

07

表示式樹

表示式樹是包含了表示式的運算數和運算子的二叉樹。這裡主要是

將中綴表示式轉換為解析樹結構

大概的思路

將中綴轉換為全括號表示式來進行操作 ，exp： 3+5*3-2 -> （ （ 3 + （ 5 * 3 ） ） - 2 ）

將所有資料存入列表，準備利用棧結構

從左到右掃描全括號表示式的每個單詞

建立一個空樹，當前結點就為根結點

如果是“（”：為當前結點新增一個新的左結點，當前結點下降為這個新結點

如果是“±*/”，將當前結點的值賦值為此符號，同時為當前結點新增一個新結點作為其右子結點，當前結點下降為這個新結點

如果當前是運算元，將當前結點的值設為此數，當前結點上升到父結點

如果當前結點是“）”，則當前結點上升到父結點

具體實現

我是一名奮戰在程式設計界的pythoner，工作中既要和資料打交道，也要和erp系統，web網站保持友好的溝通……時不時的會分享一些提高效率的程式設計小技巧，在實際應用中遇到的問題以及解決方案，或者原始碼的閱讀等等，歡迎大家一起來討論！如果覺得寫得還不錯，歡迎關注點贊，謝謝。