二叉樹的種類
- 滿二叉樹
- 完全二叉樹
滿二叉樹
滿二叉樹：如果一棵二叉樹只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)俐银，并且度為0的結(jié)點(diǎn)在同一層上隶债，則這棵二叉樹為滿二叉樹躬拢。
這棵二叉樹為滿二叉樹袍冷，也可以說深度為k季眷，有2^k-1個(gè)節(jié)點(diǎn)的二叉樹。
完全二叉樹
什么是完全二叉樹腺晾？
完全二叉樹的定義如下：在完全二叉樹中燕锥，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值悯蝉，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置归形。若最底層為第 h 層，則該層包含 1~ 2^h -1 個(gè)節(jié)點(diǎn)鼻由。
大家要自己看完全二叉樹的定義暇榴，很多同學(xué)對(duì)完全二叉樹其實(shí)不是真正的懂了。
我來舉一個(gè)典型的例子如題：
相信不少同學(xué)最后一個(gè)二叉樹是不是完全二叉樹都中招了蕉世。
之前我們剛剛講過優(yōu)先級(jí)隊(duì)列其實(shí)是一個(gè)堆蔼紧，堆就是一棵完全二叉樹，同時(shí)保證父子節(jié)點(diǎn)的順序關(guān)系狠轻。
二叉搜索樹
前面介紹的樹奸例，都沒有數(shù)值的，而二叉搜索樹是有數(shù)值的了向楼，二叉搜索樹是一個(gè)有序樹哩至。
- 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值蜜自；
- 若它的右子樹不空菩貌，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
- 它的左重荠、右子樹也分別為二叉排序樹
下面這兩棵樹都是搜索樹
平衡二叉搜索樹
平衡二叉搜索樹：又被稱為AVL（Adelson-Velsky and Landis）樹箭阶，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹戈鲁。
如圖：
最后一棵 不是平衡二叉樹仇参，因?yàn)樗淖笥覂蓚€(gè)子樹的高度差的絕對(duì)值超過了1。
C++中map婆殿、set诈乒、multimap，multiset的底層實(shí)現(xiàn)都是平衡二叉搜索樹婆芦，所以map怕磨、set的增刪操作時(shí)間時(shí)間復(fù)雜度是logn喂饥，注意我這里沒有說unordered_map、unordered_set肠鲫，unordered_map员帮、unordered_map底層實(shí)現(xiàn)是哈希表。
所以大家使用自己熟悉的編程語(yǔ)言寫算法导饲，一定要知道常用的容器底層都是如何實(shí)現(xiàn)的捞高，最基本的就是map、set等等渣锦，否則自己寫的代碼硝岗，自己對(duì)其性能分析都分析不清楚！
二叉樹的存儲(chǔ)方式
二叉樹可以鏈?zhǔn)酱鎯?chǔ)袋毙，也可以順序存儲(chǔ)型檀。
那么鏈?zhǔn)酱鎯?chǔ)方式就用指針， 順序存儲(chǔ)的方式就是用數(shù)組娄猫。
顧名思義就是順序存儲(chǔ)的元素在內(nèi)存是連續(xù)分布的贱除，而鏈?zhǔn)酱鎯?chǔ)則是通過指針把分布在散落在各個(gè)地址的節(jié)點(diǎn)串聯(lián)一起生闲。
鏈?zhǔn)酱鎯?chǔ)如圖：
鏈?zhǔn)酱鎯?chǔ)是大家很熟悉的一種方式媳溺，那么我們來看看如何順序存儲(chǔ)呢？
其實(shí)就是用數(shù)組來存儲(chǔ)二叉樹碍讯，順序存儲(chǔ)的方式如圖：
用數(shù)組來存儲(chǔ)二叉樹如何遍歷的呢悬蔽？
如果父節(jié)點(diǎn)的數(shù)組下表是i，那么它的左孩子就是i * 2 + 1捉兴，右孩子就是 i * 2 + 2蝎困。
但是用鏈?zhǔn)奖硎镜亩鏄洌欣谖覀兝斫獗渡叮砸话阄覀兌际怯面準(zhǔn)酱鎯?chǔ)二叉樹禾乘。
所以大家要了解，用數(shù)組依然可以表示二叉樹虽缕。
二叉樹的遍歷方式
關(guān)于二叉樹的遍歷方式始藕，要知道二叉樹遍歷的基本方式都有哪些。
一些同學(xué)用做了很多二叉樹的題目了氮趋，可能知道前中后序遍歷伍派，可能知道層序遍歷，但是卻沒有框架剩胁。
我這里把二叉樹的幾種遍歷方式列出來诉植，大家就可以一一串起來了。
二叉樹主要有兩種遍歷方式：
- 深度優(yōu)先遍歷：先往深走昵观，遇到葉子節(jié)點(diǎn)再往回走晾腔。（可以理解為棧舌稀，使用遞歸）
- 廣度優(yōu)先遍歷：一層一層的去遍歷。（隊(duì)列）
這兩種遍歷是圖論中最基本的兩種遍歷方式建车，后面在介紹圖論的時(shí)候 還會(huì)介紹到扩借。
那么從深度優(yōu)先遍歷和廣度優(yōu)先遍歷進(jìn)一步拓展，才有如下遍歷方式：
- 深度優(yōu)先遍歷
- 前序遍歷（遞歸法缤至，迭代法）
- 中序遍歷（遞歸法潮罪，迭代法）
- 后序遍歷（遞歸法，迭代法）
- 廣度優(yōu)先遍歷
- 層次遍歷（迭代法）
在深度優(yōu)先遍歷中：有三個(gè)順序领斥，前中后序遍歷嫉到， 有同學(xué)總分不清這三個(gè)順序，經(jīng)常搞混月洛，我這里教大家一個(gè)技巧何恶。
這里前中后，其實(shí)指的就是中間節(jié)點(diǎn)的遍歷順序嚼黔，只要大家記住 前中后序指的就是中間節(jié)點(diǎn)的位置就可以了细层。
看如下中間節(jié)點(diǎn)的順序，就可以發(fā)現(xiàn)唬涧，中間節(jié)點(diǎn)的順序就是所謂的遍歷方式
- 前序遍歷：中左右
- 中序遍歷：左中右
-
后序遍歷：左右中
大家可以對(duì)著如下圖疫赎，看看自己理解的前后中序有沒有問題。
image.png
最后再說一說二叉樹中深度優(yōu)先和廣度優(yōu)先遍歷實(shí)現(xiàn)方式碎节，我們做二叉樹相關(guān)題目捧搞，經(jīng)常會(huì)使用遞歸的方式來實(shí)現(xiàn)深度優(yōu)先遍歷，也就是實(shí)現(xiàn)前中后序遍歷狮荔，使用遞歸是比較方便的胎撇。
之前我們講棧與隊(duì)列的時(shí)候，就說過棧其實(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)爵憎，才能一層一層的來遍歷二叉樹。
這里其實(shí)我們又了解了棧與隊(duì)列的一個(gè)應(yīng)用場(chǎng)景了总滩。
具體的實(shí)現(xiàn)我們后面都會(huì)講的纲堵，這里大家先要清楚這些理論基礎(chǔ)。
二叉樹的定義
剛剛我們說過了二叉樹有兩種存儲(chǔ)方式順序存儲(chǔ)闰渔，和鏈?zhǔn)酱鎯?chǔ)席函，順序存儲(chǔ)就是用數(shù)組來存，這個(gè)定義沒啥可說的冈涧，我們來看看鏈?zhǔn)酱鎯?chǔ)的二叉樹節(jié)點(diǎn)的定義方式茂附。
C++代碼如下：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
Java代碼如下：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
大家會(huì)發(fā)現(xiàn)二叉樹的定義 和鏈表是差不多的正蛙，相對(duì)于鏈表 ，二叉樹的節(jié)點(diǎn)里多了一個(gè)指針营曼， 有兩個(gè)指針乒验，指向左右孩子.
這里要提醒大家要注意二叉樹節(jié)點(diǎn)定義的書寫方式。
在現(xiàn)場(chǎng)面試的時(shí)候 面試官可能要求手寫代碼蒂阱，所以數(shù)據(jù)結(jié)構(gòu)的定義以及簡(jiǎn)單邏輯的代碼一定要鍛煉白紙寫出來锻全。
因?yàn)槲覀冊(cè)谒eetcode的時(shí)候，節(jié)點(diǎn)的定義默認(rèn)都定義好了录煤，真到面試的時(shí)候鳄厌，需要自己寫節(jié)點(diǎn)定義的時(shí)候，有時(shí)候會(huì)一臉懵逼妈踊！
總結(jié)
二叉樹是一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)了嚎，在算法面試中都是常客廊营，也是眾多數(shù)據(jù)結(jié)構(gòu)的基石歪泳。
本篇我們介紹了二叉樹的種類、存儲(chǔ)方式露筒、遍歷方式以及定義呐伞，比較全面的介紹了二叉樹各個(gè)方面的重點(diǎn)，幫助大家掃一遍基礎(chǔ)邀窃。
** 說道二叉樹荸哟，就不得不說遞歸假哎，很多同學(xué)對(duì)遞歸都是又熟悉又陌生瞬捕，遞歸的代碼一般很簡(jiǎn)短，但每次都是一看就會(huì)舵抹，一寫就廢肪虎。**
快來練習(xí)一下吧
144. 二叉樹的前序遍歷 - 力扣（LeetCode） (leetcode-cn.com)
94. 二叉樹的中序遍歷 - 力扣（LeetCode） (leetcode-cn.com)
145. 二叉樹的后序遍歷 - 力扣（LeetCode） (leetcode-cn.com)
102. 二叉樹的層序遍歷 - 力扣（LeetCode） (leetcode-cn.com)
107. 二叉樹的層序遍歷 II - 力扣（LeetCode） (leetcode-cn.com)
