[[410995]]

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，作者程序員Carl。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。

二叉樹(shù)理論基礎(chǔ)篇

說(shuō)道二叉樹(shù)，大家對(duì)于二叉樹(shù)其實(shí)都很熟悉了，本文呢我也不想教科書(shū)式的把二叉樹(shù)的基礎(chǔ)內(nèi)容在啰嗦一遍，所以一下我講的都是一些比較重點(diǎn)的內(nèi)容。

相信只要耐心看完，都會(huì)有所收獲!

二叉樹(shù)的種類(lèi)

在我們解題過(guò)程中二叉樹(shù)有兩種主要的形式：滿(mǎn)二叉樹(shù)和完全二叉樹(shù)。

滿(mǎn)二叉樹(shù)

滿(mǎn)二叉樹(shù)：如果一棵二叉樹(shù)只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，則這棵二叉樹(shù)為滿(mǎn)二叉樹(shù)。

如圖所示：

這棵二叉樹(shù)為滿(mǎn)二叉樹(shù)，也可以說(shuō)深度為k，有2^k-1個(gè)節(jié)點(diǎn)的二叉樹(shù)。

完全二叉樹(shù)

什么是完全二叉樹(shù)?

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

大家要自己看完全二叉樹(shù)的定義，很多同學(xué)對(duì)完全二叉樹(shù)其實(shí)不是真正的懂了。

我來(lái)舉一個(gè)典型的例子如題：

相信不少同學(xué)最后一個(gè)二叉樹(shù)是不是完全二叉樹(shù)都中招了。

之前我們剛剛講過(guò)優(yōu)先級(jí)隊(duì)列其實(shí)是一個(gè)堆，堆就是一棵完全二叉樹(shù)，同時(shí)保證父子節(jié)點(diǎn)的順序關(guān)系。

二叉搜索樹(shù)

前面介紹的樹(shù)，都沒(méi)有數(shù)值的，而二叉搜索樹(shù)是有數(shù)值的了，二叉搜索樹(shù)是一個(gè)有序樹(shù)。

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

下面這兩棵樹(shù)都是搜索樹(shù)

平衡二叉搜索樹(shù)

平衡二叉搜索樹(shù)：又被稱(chēng)為AVL(Adelson-Velsky and Landis)樹(shù)，且具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

如圖：

最后一棵 不是平衡二叉樹(shù)，因?yàn)樗淖笥覂蓚€(gè)子樹(shù)的高度差的絕對(duì)值超過(guò)了1。

C++中map、set、multimap，multiset的底層實(shí)現(xiàn)都是平衡二叉搜索樹(shù)，所以map、set的增刪操作時(shí)間時(shí)間復(fù)雜度是logn，注意我這里沒(méi)有說(shuō)unordered_map、unordered_set，unordered_map、unordered_map底層實(shí)現(xiàn)是哈希表。

所以大家使用自己熟悉的編程語(yǔ)言寫(xiě)算法，一定要知道常用的容器底層都是如何實(shí)現(xiàn)的，最基本的就是map、set等等，否則自己寫(xiě)的代碼，自己對(duì)其性能分析都分析不清楚!

二叉樹(shù)的存儲(chǔ)方式

二叉樹(shù)可以鏈?zhǔn)酱鎯?chǔ)，也可以順序存儲(chǔ)。

那么鏈?zhǔn)酱鎯?chǔ)方式就用指針， 順序存儲(chǔ)的方式就是用數(shù)組。

顧名思義就是順序存儲(chǔ)的元素在內(nèi)存是連續(xù)分布的，而鏈?zhǔn)酱鎯?chǔ)則是通過(guò)指針把分布在散落在各個(gè)地址的節(jié)點(diǎn)串聯(lián)一起。

鏈?zhǔn)酱鎯?chǔ)如圖：

鏈?zhǔn)酱鎯?chǔ)是大家很熟悉的一種方式，那么我們來(lái)看看如何順序存儲(chǔ)呢?

其實(shí)就是用數(shù)組來(lái)存儲(chǔ)二叉樹(shù)，順序存儲(chǔ)的方式如圖：

用數(shù)組來(lái)存儲(chǔ)二叉樹(shù)如何遍歷的呢?

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

但是用鏈?zhǔn)奖硎镜亩鏄?shù)，更有利于我們理解，所以一般我們都是用鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)。

所以大家要了解，用數(shù)組依然可以表示二叉樹(shù)。

二叉樹(shù)的遍歷方式

關(guān)于二叉樹(shù)的遍歷方式，要知道二叉樹(shù)遍歷的基本方式都有哪些。

一些同學(xué)用做了很多二叉樹(shù)的題目了，可能知道前中后序遍歷，可能知道層序遍歷，但是卻沒(méi)有框架。

我這里把二叉樹(shù)的幾種遍歷方式列出來(lái)，大家就可以一一串起來(lái)了。

二叉樹(shù)主要有兩種遍歷方式：

1. 深度優(yōu)先遍歷：先往深走，遇到葉子節(jié)點(diǎn)再往回走。
2. 廣度優(yōu)先遍歷：一層一層的去遍歷。

這兩種遍歷是圖論中最基本的兩種遍歷方式，后面在介紹圖論的時(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ì)著如下圖，看看自己理解的前后中序有沒(méi)有問(wèn)題。

最后再說(shuō)一說(shuō)二叉樹(shù)中深度優(yōu)先和廣度優(yōu)先遍歷實(shí)現(xiàn)方式，我們做二叉樹(shù)相關(guān)題目，經(jīng)常會(huì)使用遞歸的方式來(lái)實(shí)現(xiàn)深度優(yōu)先遍歷，也就是實(shí)現(xiàn)前中后序遍歷，使用遞歸是比較方便的。

之前我們講棧與隊(duì)列的時(shí)候，就說(shuō)過(guò)棧其實(shí)就是遞歸的一種是實(shí)現(xiàn)結(jié)構(gòu)，也就說(shuō)前中后序遍歷的邏輯其實(shí)都是可以借助棧使用非遞歸的方式來(lái)實(shí)現(xiàn)的。

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

這里其實(shí)我們又了解了棧與隊(duì)列的一個(gè)應(yīng)用場(chǎng)景了。

具體的實(shí)現(xiàn)我們后面都會(huì)講的，這里大家先要清楚這些理論基礎(chǔ)。

二叉樹(shù)的定義

剛剛我們說(shuō)過(guò)了二叉樹(shù)有兩種存儲(chǔ)方式順序存儲(chǔ)，和鏈?zhǔn)酱鎯?chǔ)，順序存儲(chǔ)就是用數(shù)組來(lái)存，這個(gè)定義沒(méi)啥可說(shuō)的，我們來(lái)看看鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)節(jié)點(diǎn)的定義方式。

C++代碼如下：

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

大家會(huì)發(fā)現(xiàn)二叉樹(shù)的定義 和鏈表是差不多的，相對(duì)于鏈表 ，二叉樹(shù)的節(jié)點(diǎn)里多了一個(gè)指針， 有兩個(gè)指針，指向左右孩子.

這里要提醒大家要注意二叉樹(shù)節(jié)點(diǎn)定義的書(shū)寫(xiě)方式。

在現(xiàn)場(chǎng)面試的時(shí)候 面試官可能要求手寫(xiě)代碼，所以數(shù)據(jù)結(jié)構(gòu)的定義以及簡(jiǎn)單邏輯的代碼一定要鍛煉白紙寫(xiě)出來(lái)。

因?yàn)槲覀冊(cè)谒eetcode的時(shí)候，節(jié)點(diǎn)的定義默認(rèn)都定義好了，真到面試的時(shí)候，需要自己寫(xiě)節(jié)點(diǎn)定義的時(shí)候，有時(shí)候會(huì)一臉懵逼!

總結(jié)

二叉樹(shù)是一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，在算法面試中都是?？停彩潜姸鄶?shù)據(jù)結(jié)構(gòu)的基石。

本篇我們介紹了二叉樹(shù)的種類(lèi)、存儲(chǔ)方式、遍歷方式以及定義，比較全面的介紹了二叉樹(shù)各個(gè)方面的重點(diǎn)，幫助大家掃一遍基礎(chǔ)。

其他語(yǔ)言版本

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; 
   } 
} 

Go：

type TreeNode struct { 
    Val int 
    Left *TreeNode 
    Right *TreeNode 
}