怎么分析python二叉樹(shù)

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

很多新手可能剛接觸到數(shù)據(jù)結(jié)構(gòu)，下面先給出一張關(guān)于樹(shù)的一些基本概念。

二叉樹(shù)的定義

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

 二叉樹(shù)的特點(diǎn)

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

二叉樹(shù)的性質(zhì)

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

二叉樹(shù)遍歷

所謂遍歷是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn) 題。 遍歷是二叉樹(shù)上最重要的運(yùn)算之一，是二叉樹(shù)上進(jìn)行其它運(yùn)算之基礎(chǔ)。

二叉樹(shù)的遍歷分為深度優(yōu)先和廣度優(yōu)先兩種，其中深度優(yōu)先又包括前序遍歷、中序遍歷、后序遍歷三種，所謂前、中、后是根據(jù)根節(jié)點(diǎn)與左右子樹(shù)的遍歷順序決定的。

前序遍歷是先訪問(wèn)根節(jié)點(diǎn)再訪問(wèn)左子樹(shù)最后訪問(wèn)右子樹(shù)；中序遍歷是先訪問(wèn)左子樹(shù)再訪問(wèn)根節(jié)點(diǎn)最后訪問(wèn)右子樹(shù)；后序遍歷是先訪問(wèn)左子樹(shù)再訪問(wèn)右子樹(shù)最后訪問(wèn)根節(jié)點(diǎn)。

廣度優(yōu)先遍歷則是從根節(jié)點(diǎn)開(kāi)始由上到下按層訪問(wèn)，每一層從左到右依次訪問(wèn)。

下面分別介紹這幾種遍歷方式以及它們的代碼實(shí)現(xiàn)。

二叉樹(shù)結(jié)點(diǎn)定義

python代碼定義二叉樹(shù)結(jié)點(diǎn)如下：

圖 a(二叉樹(shù))

前（先）序遍歷

遞歸思想實(shí)現(xiàn)先序遍歷較易理解，從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)谝淮蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)，按照先向左在向右的方向訪問(wèn) 。二叉樹(shù)的前序遍歷輸出為：ABDHIEJCFG

python代碼實(shí)現(xiàn)如下：

非遞歸遍歷思路如下：
1）定義一個(gè)棧
2）將根節(jié)點(diǎn)壓入棧中
3）每次從棧中彈出結(jié)點(diǎn)記為cur并打印，如果右孩子不為空，將右孩子壓入棧中，如果左孩子不為空，將左孩子壓入棧中
4）不斷重復(fù)步驟3，直到?？战Y(jié)束

python代碼實(shí)現(xiàn)如下：

中序遍歷

遞歸思想實(shí)現(xiàn)中序遍歷順序，先遍歷左子樹(shù)；再訪問(wèn)根結(jié)點(diǎn)；最后遍歷右子樹(shù)。二叉樹(shù)的中序遍歷輸出為：HDIBJEAFCG

python代碼實(shí)現(xiàn)如下：

非遞歸遍歷思路如下：

1）申請(qǐng)一個(gè)棧stack，申請(qǐng)一個(gè)變量cur指向頭結(jié)點(diǎn)

2）先把頭結(jié)點(diǎn)壓入棧中，對(duì)于以cur為頭結(jié)點(diǎn)的整顆子樹(shù)來(lái)說(shuō)，依次把整顆樹(shù)的左邊界壓入棧中，即不斷令cur=cur.left

3）不斷重復(fù)步驟2，直到cur為空，此時(shí)從棧中彈出結(jié)點(diǎn)node并打印，然cur=node.right,然后重復(fù)步驟2

4）當(dāng)stack為空并且cur為空時(shí)，結(jié)束。

python代碼實(shí)現(xiàn)如下：

后序遍歷

遞歸思想實(shí)現(xiàn)后序遍歷順序，先遍歷左子樹(shù)；再遍歷右子樹(shù)；最后訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)的后序遍歷輸出為：HIDJEBFGCA

python代碼實(shí)現(xiàn)如下：

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

python代碼實(shí)現(xiàn)如下：

廣度優(yōu)先（層序）遍歷

廣度優(yōu)先(層序遍歷)是用隊(duì)列來(lái)實(shí)現(xiàn)的，從二叉樹(shù)的第一層（根結(jié)點(diǎn)）開(kāi)始，自上至下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問(wèn)。

按照從根結(jié)點(diǎn)至葉結(jié)點(diǎn)、從左子樹(shù)至右子樹(shù)的次序訪問(wèn)二叉樹(shù)的結(jié)點(diǎn)。

算法：

1、初始化一個(gè)隊(duì)列，并把根結(jié)點(diǎn)入列隊(duì)；

2、當(dāng)隊(duì)列為非空時(shí)，循環(huán)執(zhí)行步驟3到步驟5，否則執(zhí)行6；

3、出隊(duì)列取得一個(gè)結(jié)點(diǎn)，訪問(wèn)該結(jié)點(diǎn)；

4、若該結(jié)點(diǎn)的左子樹(shù)為非空，則將該結(jié)點(diǎn)的左子樹(shù)入隊(duì)列；

5、若該結(jié)點(diǎn)的右子樹(shù)為非空，則將該結(jié)點(diǎn)的右子樹(shù)入隊(duì)列；

6、結(jié)束。

python代碼實(shí)現(xiàn)如下：

關(guān)于怎么分析python二叉樹(shù)就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。