Python版演算法專題 二叉樹的深度優先遍歷

二叉樹作為一種數據結構，其應用場景非常多，具體的有：用於數據的檢索，數據管理，在遊戲領域，可以用於場景的劃分等。

二叉樹的遍歷，分為深度優先遍歷，以及廣度優先遍歷。在深度優先遍歷中，具體分為如下三種：

先序遍歷：先訪問根節點，再遍歷左子樹，再遍歷右子樹；

中序遍歷：先遍歷左子樹，再訪問根節點，再遍歷右子樹；

後序遍歷：先遍歷左子樹，再遍歷右子樹，再訪問根節點

對於上圖的二叉樹，其先序遍歷結果是：50,20,15,30,60,70；其中序遍歷結果是：15,20,30,50,60,70；其後序遍歷結果是：15，30，20,70,60,50

下面，進入我們的代碼實現：

首先，定義二叉樹中的節點：

定義二叉樹類：

遞歸實現的先序遍歷演算法如下：

遞歸實現的中序遍歷演算法如下：

遞歸實現的後序遍歷演算法如下：

我們使用如下的二叉樹，做演算法的驗證：

測試結果如下：

想要系統學習python和免費學習資料的 可以加裙 四七四五三四九五一

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！