提示：文章寫完后，目錄可以自動(dòng)生成，如何生成可參考右邊的幫助文檔

文章目錄

• 前言
• 一、你應(yīng)該具備的基礎(chǔ)知識(shí)
• 二、二叉樹的種類有哪些？
• • 1、滿二叉樹
  • 2、完全二叉樹
  • 3、二叉搜索樹(二叉排序樹)
  • 4、平衡二叉搜索樹
  • 小結(jié)
• 三、二叉樹的存儲(chǔ)方式
• • 1、鏈?zhǔn)酱鎯?chǔ)(最重要)
  • 2、順序存儲(chǔ)（了解）
• 四、二叉樹的遍歷方式
• • 小結(jié)
• 五、二叉樹的定義（要能手撕）
• 六、總結(jié)

---

前言

提示：二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，也是面試和筆試的重頭，接下來我們要系統(tǒng)性的總結(jié)二叉樹的知識(shí)點(diǎn)。

---

一、你應(yīng)該具備的基礎(chǔ)知識(shí)

1、結(jié)點(diǎn)的度：樹中結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。度為0的結(jié)點(diǎn)為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。

2、樹的度：樹中所有結(jié)點(diǎn)的度的最大值。（不是和）

3、樹中結(jié)點(diǎn)總數(shù)：所有結(jié)點(diǎn)的度數(shù)和加1

4、度為m的樹與m叉樹的區(qū)別

5、結(jié)點(diǎn)的層次(level )

6、邊: 一棵n個(gè)結(jié)點(diǎn)樹有n-1條邊

7、路徑:從結(jié)點(diǎn)n1到結(jié)點(diǎn)ni的結(jié)點(diǎn)序列,路徑的長(zhǎng)度為該路徑上邊的條數(shù)。從根到每個(gè)結(jié)點(diǎn)恰好存在一條路徑。

8、結(jié)點(diǎn)深度:從根到當(dāng)前結(jié)點(diǎn)的路徑的長(zhǎng)度。根結(jié)點(diǎn)的深度是0 ,右圖中B和C的深度是1 , E的深度是2。

9、結(jié)點(diǎn)高度:從當(dāng)前結(jié)點(diǎn)到葉結(jié)點(diǎn)(終端結(jié)點(diǎn))最長(zhǎng)路徑的長(zhǎng)度。樹的葉結(jié)點(diǎn)的高度是0。右圖中B的高度是2 , C的高度是1。一棵樹的深度等于最深的結(jié)點(diǎn)的深度,該深度總是等于這棵樹的高度。

10、m叉樹中第i層上最多有m^(i-1)個(gè)結(jié)點(diǎn)

11、高度為h的m叉樹最多有( m^(h-1) ) / (m-1) 個(gè)結(jié)點(diǎn)

嚴(yán):
1 )結(jié)點(diǎn)的層次從1開始;
2)沒有對(duì)結(jié)點(diǎn)深度和高度作出解釋;
3)樹中結(jié)點(diǎn)最大的層次稱為樹的深度或高度。

二、二叉樹的種類有哪些？

其中我們接觸最多也最重要的是：滿二叉樹和完全二叉樹。

1、滿二叉樹

只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層。
高度為h的二叉樹有 2^h -1 個(gè)結(jié)點(diǎn)。

2、完全二叉樹

除最底層可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到了最大值，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第h層，則該層包含1~2^(h-1)個(gè)結(jié)點(diǎn)。

3、二叉搜索樹(二叉排序樹)

若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
它的左、右子樹也分別為二叉排序樹；

4、平衡二叉搜索樹

著名的AVL樹，更嚴(yán)格的二叉搜索樹，它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。

C++中set/multiset、map/multimap的底層實(shí)現(xiàn)都是紅黑樹（一種平衡二叉搜索樹），所以map、set的增刪操作時(shí)間時(shí)間復(fù)雜度是logn。

小結(jié)

1、平衡二叉搜索樹就是二叉搜索樹和平衡二叉樹的結(jié)合
2、完全二叉樹一定是平衡二叉樹。他們的區(qū)別在于底層節(jié)點(diǎn)的位置，完全二叉樹底層必須是從左到右連續(xù)的，且次底層是滿的。
3、堆就是一棵完全二叉樹，同時(shí)保證父子節(jié)點(diǎn)的順序關(guān)系(父節(jié)點(diǎn)大于左右孩子)。堆的順序是父節(jié)點(diǎn)大于左右孩子，二叉搜索樹是父節(jié)點(diǎn)大于左孩子，小于右孩子，所以堆不是平衡二叉搜索樹。

三、二叉樹的存儲(chǔ)方式

1、鏈?zhǔn)酱鎯?chǔ)(最重要)

2、順序存儲(chǔ)（了解）

如果父節(jié)點(diǎn)的數(shù)組下標(biāo)是i，那么它的左孩子就是2i + 1，右孩子就是 2i + 2。

四、二叉樹的遍歷方式

1、二叉樹主要有兩種遍歷方式：
深度優(yōu)先遍歷：先往深走，遇到葉子節(jié)點(diǎn)再往回走。
廣度優(yōu)先遍歷：一層一層的去遍歷。

從深度優(yōu)先遍歷和廣度優(yōu)先遍歷進(jìn)一步拓展，才有如下遍歷方式：
深度優(yōu)先遍歷
前序遍歷（遞歸法，迭代法）
中序遍歷（遞歸法，迭代法）
后序遍歷（遞歸法，迭代法）
廣度優(yōu)先遍歷
層次遍歷（迭代法）

中間節(jié)點(diǎn)的順序就是所謂的遍歷方式

小結(jié)

我們做二叉樹相關(guān)題目，經(jīng)常會(huì)使用遞歸的方式來實(shí)現(xiàn)深度優(yōu)先遍歷，也就是實(shí)現(xiàn)前中后序遍歷。

棧其實(shí)就是遞歸的一種是實(shí)現(xiàn)結(jié)構(gòu)，也就說前中后序遍歷的邏輯其實(shí)都是可以借助棧使用非遞歸的方式來實(shí)現(xiàn)的。

而廣度優(yōu)先遍歷的實(shí)現(xiàn)一般使用隊(duì)列來實(shí)現(xiàn)，這也是隊(duì)列先進(jìn)先出的特點(diǎn)所決定的，因?yàn)樾枰冗M(jìn)先出的結(jié)構(gòu)，才能一層一層的來遍歷二叉樹。

五、二叉樹的定義（要能手撕）

代碼如下（示例）：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

---

六、總結(jié)

本篇介紹了二叉樹的種類、存儲(chǔ)方式、遍歷方式以及定義，比較全面的介紹了二叉樹各個(gè)方面的重點(diǎn)，掃了一遍基礎(chǔ)。接下來將要重點(diǎn)學(xué)習(xí)二叉樹的遍歷方法。
注：本篇文章參考代碼隨想錄公眾號(hào)整理所得。

總結(jié)

以上是生活随笔為你收集整理的二叉树的基础知识的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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