主要內容：

二叉樹遍歷（先序、中序、后序、寬度優(yōu)先遍歷）的迭代實現(xiàn)和遞歸實現(xiàn)；

二叉樹的深度，二叉樹到葉子節(jié)點的所有路徑。

首先，先定義二叉樹類（python3），代碼如下：

class

內容1：二叉樹的遍歷

二叉樹的遍歷分深度優(yōu)先遍歷（DFS）和寬度優(yōu)先遍歷（BFS）。其中深度優(yōu)先遍歷又分為先序遍歷，中序遍歷，后序遍歷。因為二叉樹是遞歸類數(shù)據(jù)結構，因此大部分關于二叉樹的操作都可以通過遞歸實現(xiàn)。下面將介紹二叉樹幾種遍歷的實現(xiàn)代碼以及思路。

1.1 先序遍歷：

遍歷順序：根節(jié)點——左子節(jié)點——右子節(jié)點（A-B-D-E-C-F）。

遞歸實現(xiàn)：

def

迭代實現(xiàn)：

def

1.2 中序遍歷

遍歷順序：左子節(jié)點——根節(jié)點——右子節(jié)點（D-B-E-A-C-F）

遞歸實現(xiàn)：

def

迭代實現(xiàn)：

def

1.3 后序遍歷

遍歷順序：左子節(jié)點——右子節(jié)點——根節(jié)點（D-E-B-F-C-A）

遞歸實現(xiàn)：

def

迭代實現(xiàn)：

def

1.4 層次遍歷

遍歷順序：一層一層的遍歷（A-B-C-D-E-F）

迭代實現(xiàn)：

def

內容2：基本操作

2.1 二叉樹的最大深度

基本思路就是遞歸，當前樹的最大深度等于（1+max(左子樹最大深度，右子樹最大深度)）。代碼如下：

def

2.2 二叉樹的最小深度

最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量?？梢酝ㄟ^遞歸求左右節(jié)點的最小深度的較小值，也可以層序遍歷找到第一個葉子節(jié)點所在的層數(shù)。

遞歸方法：

class

迭代方法：

class

2.3 二叉樹的所有路徑

根節(jié)點到葉子節(jié)點的所有路徑。

def

總結

以上是生活随笔為你收集整理的c++ stack 遍历_python实现二叉树的遍历以及其他基本操作的全部內容，希望文章能夠幫你解決所遇到的問題。

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