本文參考河北小博的文章

https://blog.csdn.net/qq_32799165/article/details/88879239

漫畫由小猿編寫創(chuàng)作

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

二叉樹的定義

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

 二叉樹的特點(diǎn)

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

二叉樹的性質(zhì)

1）在二叉樹的第i層上最多有2^i-1 個(gè)節(jié)點(diǎn) 。（i>=1）
2）二叉樹中如果深度為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）在完全二叉樹中，具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[log₂n]+1，其中[log₂n]是向下取整。

二叉樹遍歷

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

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

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

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

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

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

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

圖 a(二叉樹)

前（先）序遍歷

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

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

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

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

中序遍歷

遞歸思想實(shí)現(xiàn)中序遍歷順序，先遍歷左子樹；再訪問根結(jié)點(diǎn)；最后遍歷右子樹。二叉樹的中序遍歷輸出為：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)的整顆子樹來說，依次把整顆樹的左邊界壓入棧中，即不斷令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)后序遍歷順序，先遍歷左子樹；再遍歷右子樹；最后訪問根結(jié)點(diǎn)。二叉樹的后序遍歷輸出為：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ì)列來實(shí)現(xiàn)的，從二叉樹的第一層（根結(jié)點(diǎn)）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問。

按照從根結(jié)點(diǎn)至葉結(jié)點(diǎn)、從左子樹至右子樹的次序訪問二叉樹的結(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)，訪問該結(jié)點(diǎn)；

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

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

6、結(jié)束。

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

以柯哀漫畫為載體的技術(shù)公眾號(hào)