怎么分析python二叉樹

這篇文章給大家介紹怎么分析python二叉樹，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

很多新手可能剛接觸到數據結構，下面先給出一張關于樹的一些基本概念。

二叉樹的定義

二叉樹是n(n>=0)個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹組成。下圖展示了一棵普通二叉樹：

 二叉樹的特點

由二叉樹定義以及圖示分析得出二叉樹有以下特點：
1）每個結點最多有兩顆子樹，所以二叉樹中不存在度大于2的結點。
2）左子樹和右子樹是有順序的，次序不能任意顛倒。
3）即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。

二叉樹的性質

1）在二叉樹的第i層上最多有2^i-1 個節點 。（i>=1）
2）二叉樹中如果深度為k,那么最多有2^k-1個節點。(k>=1）
3）n₀=n₂+1  n₀表示度數為0的節點數，n₂表示度數為2的節點數。
4）在完全二叉樹中，具有n個節點的完全二叉樹的深度為[log₂n]+1，其中[log₂n]是向下取整。

二叉樹遍歷

所謂遍歷是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴于具體的應用問 題。 遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。

二叉樹的遍歷分為深度優先和廣度優先兩種，其中深度優先又包括前序遍歷、中序遍歷、后序遍歷三種，所謂前、中、后是根據根節點與左右子樹的遍歷順序決定的。

前序遍歷是先訪問根節點再訪問左子樹最后訪問右子樹；中序遍歷是先訪問左子樹再訪問根節點最后訪問右子樹；后序遍歷是先訪問左子樹再訪問右子樹最后訪問根節點。

廣度優先遍歷則是從根節點開始由上到下按層訪問，每一層從左到右依次訪問。

下面分別介紹這幾種遍歷方式以及它們的代碼實現。

二叉樹結點定義

python代碼定義二叉樹結點如下：

圖 a(二叉樹)

前（先）序遍歷

遞歸思想實現先序遍歷較易理解，從二叉樹的根結點出發，當第一次到達結點時就輸出結點數據，按照先向左在向右的方向訪問 。二叉樹的前序遍歷輸出為：ABDHIEJCFG

python代碼實現如下：

非遞歸遍歷思路如下：
1）定義一個棧
2）將根節點壓入棧中
3）每次從棧中彈出結點記為cur并打印，如果右孩子不為空，將右孩子壓入棧中，如果左孩子不為空，將左孩子壓入棧中
4）不斷重復步驟3，直到棧空結束

python代碼實現如下：

中序遍歷

遞歸思想實現中序遍歷順序，先遍歷左子樹；再訪問根結點；最后遍歷右子樹。二叉樹的中序遍歷輸出為：HDIBJEAFCG

python代碼實現如下：

非遞歸遍歷思路如下：

1）申請一個棧stack，申請一個變量cur指向頭結點

2）先把頭結點壓入棧中，對于以cur為頭結點的整顆子樹來說，依次把整顆樹的左邊界壓入棧中，即不斷令cur=cur.left

3）不斷重復步驟2，直到cur為空，此時從棧中彈出結點node并打印，然cur=node.right,然后重復步驟2

4）當stack為空并且cur為空時，結束。

python代碼實現如下：

后序遍歷

遞歸思想實現后序遍歷順序，先遍歷左子樹；再遍歷右子樹；最后訪問根結點。二叉樹的后序遍歷輸出為：HIDJEBFGCA

python代碼實現如下：

非遞歸遍歷思路如下：
1）申請兩個棧s1，s2，然后將頭結點壓入s1
2）從s1中彈出的結點記為cur,并加入到棧s2中，然后把cur的左孩子壓入s1中，然后把cur的右孩子壓入s1中
3）不斷重復2，直到s1為空
4）從s2彈出結點并打印

python代碼實現如下：

廣度優先（層序）遍歷

廣度優先(層序遍歷)是用隊列來實現的，從二叉樹的第一層（根結點）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序對結點逐一訪問。

按照從根結點至葉結點、從左子樹至右子樹的次序訪問二叉樹的結點。

算法：

1、初始化一個隊列，并把根結點入列隊；

2、當隊列為非空時，循環執行步驟3到步驟5，否則執行6；

3、出隊列取得一個結點，訪問該結點；

4、若該結點的左子樹為非空，則將該結點的左子樹入隊列；

5、若該結點的右子樹為非空，則將該結點的右子樹入隊列；

6、結束。

python代碼實現如下：

關于怎么分析python二叉樹就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。