下面我們將鏡頭切到袁記菜館。

小二：掌柜的，最近大家都在忙著種樹(shù)，說(shuō)是要保護(hù)環(huán)境。

老板娘：樹(shù) ？ 咱們店有呀，前幾年種的那棵葡萄樹(shù)，不是都結(jié)果子了嗎？就數(shù)你吃的最多。

小兒：這...

大家應(yīng)該猜到，咱們今天要嘮啥了。

之前給大家介紹了鏈表，棧，哈希表 等數(shù)據(jù)結(jié)構(gòu)

今天咱們來(lái)看一種新的數(shù)據(jù)結(jié)構(gòu)，樹(shù)。

PS：本篇文章內(nèi)容較基礎(chǔ)，對(duì)于沒(méi)有學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)會(huì)有一些幫助，如果你已經(jīng)學(xué)過(guò)的話，也可以復(fù)習(xí)一下，查缺補(bǔ)漏，后面會(huì)繼續(xù)更新這個(gè)系列。

樹(shù)

我們先來(lái)看下百度百科對(duì)樹(shù)的定義

樹(shù)是 n （n 》= 0） 個(gè)節(jié)點(diǎn)的有限集。n = 0 時(shí) 我們稱之為空樹(shù)， 空樹(shù)是樹(shù)的特例。

在任意一棵非空樹(shù)中：

有且僅有一個(gè)特定的節(jié)點(diǎn)稱為根（Root）的節(jié)點(diǎn)

當(dāng) n 》 1 時(shí)，其余節(jié)點(diǎn)可分為 m （m 》 0）個(gè)互不相交的有限集 T1、T2、....Tm，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)。

我們一起來(lái)拆解一下上面的兩句話，到底什么是子樹(shù)呢？見(jiàn)下圖

樹(shù)

例如在上面的圖中

有且僅有一個(gè)特定的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，也就是上圖中的橙色節(jié)點(diǎn)。

當(dāng)節(jié)點(diǎn)數(shù)目大于 1 時(shí)，除根節(jié)點(diǎn)以外的節(jié)點(diǎn)，可分為 m 個(gè)互不相交的有限集 T1，T2.。..。...Tm。

例如上圖中，我們將根節(jié)點(diǎn)以外的節(jié)點(diǎn)，分為了 T1 （2，3，4，5，6，7），T2（8，9）兩個(gè)有限集。

那么 T1 （綠色節(jié)點(diǎn)）和 T2（藍(lán)色節(jié)點(diǎn)）就是根節(jié)點(diǎn)（橙色節(jié)點(diǎn)）的子樹(shù)。

我們拆解之后發(fā)現(xiàn)，我們上圖中的例子符合樹(shù)的要求，另外不知道大家有沒(méi)有注意到這個(gè)地方。

除根節(jié)點(diǎn)以外的節(jié)點(diǎn)，可分為 m 個(gè)互不相交的有限集。

那么這個(gè)互不相交又是什么含義呢？見(jiàn)下圖。

我們將 （A） ， （B） ， （C） ， （D） 代入上方定義中發(fā)現(xiàn)，（A） ， （B） 符合樹(shù)的定義，（C）， （D） 不符合，這是因?yàn)?（C） ， （D） 它們都有相交的子樹(shù)。

好啦，到這里我們知道如何辨別樹(shù)啦，下面我們通過(guò)下面兩張圖再來(lái)深入了解一下樹(shù)。

主要從節(jié)點(diǎn)類型，節(jié)點(diǎn)間的關(guān)系下手。

這里節(jié)點(diǎn)的高度和深度可能容易記混，我們代入到現(xiàn)實(shí)即可。

我們求物體深度時(shí)，從上往下測(cè)量，求高度時(shí)，從下往上測(cè)量，節(jié)點(diǎn)的高度和深度也是如此。

二叉樹(shù)

我們刷題時(shí)遇到的就是二叉樹(shù)啦，下面我們一起來(lái)了解一下二叉樹(shù)

二叉樹(shù)前提是一棵樹(shù)，也就是需要滿足我們樹(shù)的定義的同時(shí)，還需要滿足以下要求

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

注意我們這里提到的是最多，所以二叉樹(shù)并不是必須要求每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，也可以有的僅有一個(gè)左子節(jié)點(diǎn)，有的節(jié)點(diǎn)僅有一個(gè)右子節(jié)點(diǎn)。

下面我們來(lái)總結(jié)一下二叉樹(shù)的特點(diǎn)

每個(gè)節(jié)點(diǎn)最多有兩棵子樹(shù)，也就是說(shuō)二叉樹(shù)中不存在度大于 2 的節(jié)點(diǎn)，節(jié)點(diǎn)的度可以為 0，1，2。

左子樹(shù)和右子樹(shù)是有順序的，有左右之分。

假如只有一棵子樹(shù) ，也要區(qū)分它是左子樹(shù)還是右子樹(shù)

好啦，我們已經(jīng)了解了二叉樹(shù)的特點(diǎn)，那我們分析一下，下圖中的樹(shù)是否滿足二叉樹(shù)定義，共有幾種二叉樹(shù)。

上圖共為 5 種不同的二叉樹(shù)，在二叉樹(shù)的定義中提到，二叉樹(shù)的左子樹(shù)和右子樹(shù)是有順序的，所以 B，C 是兩個(gè)不同的二叉樹(shù)，故上圖為 5 種不同的二叉樹(shù)。

特殊的二叉樹(shù)

下面我們來(lái)說(shuō)幾種比較特殊的二叉樹(shù)，可以幫助我們刷題時(shí)，考慮到特殊情況。

滿二叉樹(shù)

滿二叉樹(shù)：在一棵二叉樹(shù)中，所有分支節(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有的葉子都在同一層，這種樹(shù)我們稱之為滿二叉樹(shù)。見(jiàn)下圖

我們發(fā)現(xiàn)只有 （B） 符合滿二叉樹(shù)的定義，我們發(fā)現(xiàn)其實(shí)滿二叉樹(shù)也為完全二叉樹(shù)的一種。

完全二叉樹(shù)

完全二叉樹(shù)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹(shù)的左部。

哦！我們可以這樣理解，除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，而且最后一層的葉子節(jié)點(diǎn)必須靠左。

下面我們來(lái)看一下這幾個(gè)例子

上面的幾個(gè)例子中，（A）（B）為完全二叉樹(shù)，（C）（D）不是完全二叉樹(shù)

斜二叉樹(shù)

這個(gè)就很好理解啦，斜二叉樹(shù)也就是斜的二叉樹(shù)，所有的節(jié)點(diǎn)只有左子樹(shù)的稱為左斜樹(shù)，所有節(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)稱為右斜樹(shù)。

諾，下面這倆就是。

另外還有 一些二叉樹(shù)的性質(zhì)， 比如第 i 層至多有多少節(jié)點(diǎn)，通過(guò)葉子節(jié)點(diǎn)求度為 2 的節(jié)點(diǎn)， 通過(guò)節(jié)點(diǎn)樹(shù)求二叉樹(shù)的深度等， 這些是考研常考的知識(shí)， 就不在這里進(jìn)行贅述，需要的同學(xué)可以看一下王道或者天勤的數(shù)據(jù)結(jié)構(gòu)， 上面描述的很具體， 并附有證明過(guò)程。

好啦，我們已經(jīng)了解了二叉樹(shù)，那么二叉樹(shù)如何存儲(chǔ)呢？

如何存儲(chǔ)二叉樹(shù)

二叉樹(shù)多采用兩種方法進(jìn)行存儲(chǔ)，基于數(shù)組的順序存儲(chǔ)法和基于指針的二叉鏈?zhǔn)酱鎯?chǔ)法

我們?cè)谥罢f(shuō)過(guò)的堆排序中，其中對(duì)堆的存儲(chǔ)采用的則是順序存儲(chǔ)法，具體細(xì)節(jié)可以看這篇文章

一個(gè)破堆排我搞了 4 個(gè)動(dòng)畫(huà)？

這里我們?cè)賮?lái)回顧一下如何用數(shù)組存儲(chǔ)完全二叉樹(shù)。

我們首先看根節(jié)點(diǎn)，也就是值為 1 的節(jié)點(diǎn)，它在數(shù)組中的下標(biāo)為 1 ，它的左子節(jié)點(diǎn)，也就是值為 4 的節(jié)點(diǎn)，此時(shí)索引為 2，右子節(jié)點(diǎn)也就是值為 2 的節(jié)點(diǎn)，它的索引為 3。

我們發(fā)現(xiàn)其中的關(guān)系了嗎？

數(shù)組中，某節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）的下標(biāo)為 i ， 那么其左子節(jié)點(diǎn)下標(biāo)為 2*i（這里可以直接通過(guò)相乘得到左孩子， 也就是為什么空出第一個(gè)位置， 如果從 0 開(kāi)始存，則需要 2i+1 才行）， 右子節(jié)點(diǎn)為 2i+1，其父節(jié)點(diǎn)為 i/2 。既然我們完全可以根據(jù)索引找到某節(jié)點(diǎn)的 左子節(jié)點(diǎn) 和右子節(jié)點(diǎn)，那么我們用數(shù)組存儲(chǔ)是完全沒(méi)有問(wèn)題的。

但是，我們?cè)倏紤]一下這種情景，如果我們用數(shù)組存儲(chǔ)斜樹(shù)時(shí)會(huì)出現(xiàn)什么情況？

通過(guò) 2*i 進(jìn)行存儲(chǔ)左子節(jié)點(diǎn)的話，如果遇到斜樹(shù)時(shí)，則會(huì)浪費(fèi)很多的存儲(chǔ)空間，這樣顯然是不合適的，

所以說(shuō)當(dāng)存儲(chǔ)完全二叉樹(shù)時(shí)，我們用數(shù)組存儲(chǔ)，無(wú)疑是最省內(nèi)存的，但是存儲(chǔ)斜樹(shù)時(shí)，則就不太合適。

所以我們下面介紹一下另一種存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

因?yàn)槎鏄?shù)的每個(gè)節(jié)點(diǎn)， 最多有兩個(gè)孩子， 所以我們只需為每個(gè)節(jié)點(diǎn)定義一個(gè)數(shù)據(jù)域，兩個(gè)指針域即可

val 為節(jié)點(diǎn)的值， left 指向左子節(jié)點(diǎn)， right 指向右子節(jié)點(diǎn)。

下面我們對(duì)樹(shù) 1， 2， 3， 4， 5， 6， 7 使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，即為下面這種情況。

二叉鏈表的節(jié)點(diǎn)結(jié)構(gòu)定義代碼

public class BinaryTree {

int val;

BinaryTree left;

BinaryTree right;

BinaryTree（） {}

BinaryTree（int val） { this.val = val; }

BinaryTree（int val， BinaryTree left， BinaryTree right） {

this.val = val;

this.left = left;

this.right = right;

}

}

另外我們?cè)谒㈩}的時(shí)候， 可以自己實(shí)現(xiàn)一下數(shù)據(jù)結(jié)構(gòu)， 加深我們的理解， 提升基本功， 而且面試考的也越來(lái)越多。

好啦，下面我們說(shuō)一下樹(shù)的遍歷，

下面我會(huì)用動(dòng)圖的形式進(jìn)行描述，很容易理解， 我也會(huì)為大家總結(jié)對(duì)應(yīng)的題目，歡迎各位閱讀。

遍歷二叉樹(shù)

二叉樹(shù)的遍歷指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)的所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)都被訪問(wèn)且訪問(wèn)一次。

我們下面介紹二叉樹(shù)的幾種遍歷方法及其對(duì)應(yīng)的題目， 前序遍歷， 中序遍歷 ， 后序遍歷 ， 層序遍歷 。

前序遍歷

前序遍歷的順序是， 對(duì)于樹(shù)中的某節(jié)點(diǎn)，先遍歷該節(jié)點(diǎn)，然后再遍歷其左子樹(shù)，最后遍歷其右子樹(shù)。

只看文字有點(diǎn)生硬， 下面我們直接看動(dòng)畫(huà)吧

前序遍歷

測(cè)試題目： leetcode 144. 二叉樹(shù)的前序遍歷

代碼實(shí)現(xiàn)（遞歸版）

class Solution {

public List《Integer》 preorderTraversal（TreeNode root） {

List《Integer》 arr = new ArrayList《》（）;

preorder（root，arr）;

return arr;

}

public void preorder（TreeNode root，List《Integer》 arr） {

if （root == null） {

return;

}

arr.add（root.val）;

preorder（root.left，arr）;

preorder（root.right，arr）;

}

}

時(shí)間復(fù)雜度 ： O（n） 空間復(fù)雜度 ： O（n） 為遞歸過(guò)程中棧的開(kāi)銷，平均為 O（logn），但是當(dāng)二叉樹(shù)為斜樹(shù)時(shí)則為 O（n）

為了控制文章篇幅， 二叉樹(shù)的迭代遍歷形式， 會(huì)在下篇文章進(jìn)行介紹。

中序遍歷

中序遍歷的順序是， 對(duì)于樹(shù)中的某節(jié)點(diǎn)，先遍歷該節(jié)點(diǎn)的左子樹(shù)， 然后再遍歷該節(jié)點(diǎn)， 最后遍歷其右子樹(shù)

繼續(xù)看動(dòng)畫(huà)吧， 如果有些遺忘或者剛開(kāi)始學(xué)數(shù)據(jù)結(jié)構(gòu)的同學(xué)可以自己模擬一下執(zhí)行步驟。

中序遍歷

測(cè)試題目： leetcode 94 題 二叉樹(shù)的中序遍歷

代碼實(shí)現(xiàn)（遞歸版）

class Solution {

public List《Integer》 inorderTraversal（TreeNode root） {

List《Integer》 res = new ArrayList《》（）;

inorder（root， res）;

return res;

}

public void inorder （TreeNode root， List《Integer》 res） {

if （root == null） {

return;

}

inorder（root.left， res）;

res.add（root.val）;

inorder（root.right， res）;

}

}

時(shí)間復(fù)雜度 ： O（n） 空間復(fù)雜度 ： O（n）

后序遍歷

后序遍歷的順序是，對(duì)于樹(shù)中的某節(jié)點(diǎn)， 先遍歷該節(jié)點(diǎn)的左子樹(shù)， 再遍歷其右子樹(shù)， 最后遍歷該節(jié)點(diǎn)。

后序遍歷

測(cè)試題目： leetcode 145 題 二叉樹(shù)的后序遍歷

代碼實(shí)現(xiàn)（遞歸版）

class Solution {

public List《Integer》 postorderTraversal（TreeNode root） {

List《Integer》 res = new ArrayList《》（）;

postorder（root，res）;

return res;

}

public void postorder（TreeNode root， List《Integer》 res） {

if （root == null） {

return;

}

postorder（root.left， res）;

postorder（root.right， res）;

res.add（root.val）;

}

}

時(shí)間復(fù)雜度 ： O（n） 空間復(fù)雜度 ： O（n）

層序遍歷

顧名思義，一層一層的遍歷。

比如剛才那棵二叉樹(shù)的層序遍歷序列即為 1 ~ 9.

二叉樹(shù)的層序， 這里我們需要借助其他數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)， 我們思考一下， 我們需要對(duì)二叉樹(shù)進(jìn)行層次遍歷， 從上往下進(jìn)行遍歷， 我們可以借助什么數(shù)據(jù)結(jié)構(gòu)來(lái)幫我們呢 ？

我們可以利用隊(duì)列先進(jìn)先出的特性，使用隊(duì)列來(lái)幫助我們完成層序遍歷， 具體操作如下

讓二叉樹(shù)的每一層入隊(duì)， 然后再依次執(zhí)行出隊(duì)操作，

對(duì)該層節(jié)點(diǎn)執(zhí)行出隊(duì)操作時(shí)， 需要將該節(jié)點(diǎn)的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)進(jìn)行入隊(duì)操作，

這樣當(dāng)該層的所有節(jié)點(diǎn)出隊(duì)結(jié)束后， 下一層也就入隊(duì)完畢，

不過(guò)我們需要考慮的就是， 我們需要通過(guò)一個(gè)變量來(lái)保存每一層節(jié)點(diǎn)的數(shù)量。

這樣做是為了防止， 一直執(zhí)行出隊(duì)操作， 使輸出不能分層，

測(cè)試題目： leetcode 102 二叉樹(shù)的層序遍歷

題目代碼

class Solution {

public List《List《Integer》》 levelOrder（TreeNode root） {

List《List《Integer》》 res = new ArrayList《》（）;

if （root == null） {

return res;

}

//入隊(duì) root 節(jié)點(diǎn)，也就是第一層

Queue《TreeNode》 queue = new LinkedList《》（）;

queue.offer（root）;

while （！queue.isEmpty（）） {

List《Integer》 list = new ArrayList《》（）;

int size = queue.size（）;

for （int i = 0; i 《 size; ++i） {

TreeNode temp = queue.poll（）;

//孩子節(jié)點(diǎn)不為空，則入隊(duì)

if （temp.left ！= null） queue.offer（temp.left）;

if （temp.right ！= null） queue.offer（temp.right）;

list.add（temp.val）;

}

res.add（list）;

}

return res;

}

}

時(shí)間復(fù)雜度：O（n） 空間復(fù)雜度：O（n）

大家如果吃透了二叉樹(shù)的層序遍歷的話，可以順手把下面幾道題目解決掉，思路一致，甚至都不用拐彎

leetcode 107. 二叉樹(shù)的層序遍歷 II

leetcode 103. 二叉樹(shù)的鋸齒形層序遍歷上面兩道題僅僅是多了翻轉(zhuǎn)

leetcode 199. 二叉樹(shù)的右視圖

leetcode 515. 在每個(gè)樹(shù)行中找最大值

leetcode 637. 二叉樹(shù)的層平均值

這三道題，僅僅是加了一層的一些操作

leetcode 116 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)

leetcode 117 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)2

這兩個(gè)題對(duì)每一層的節(jié)點(diǎn)進(jìn)行鏈接即可，兩道題目代碼一致

大家可以去順手解決這些題目，但是也要注意一下其他解法，把題目吃透。不要為了數(shù)目而刷題，好啦，今天的節(jié)目就到這里啦，我們下期見(jiàn)！

原文標(biāo)題：把二叉樹(shù)揉碎（一）

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq