前言：程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法淑履。本篇是二叉樹基礎(chǔ)，會(huì)介紹二叉樹一些重要性質(zhì)和概念藻雪，整理了前序秘噪、中序、后序遍歷兩種算法（遞歸和迭代）阔涉。本篇簡(jiǎn)書基于《大話數(shù)據(jù)結(jié)構(gòu)》而寫缆娃，非常推薦的入門書籍，如果能力較強(qiáng)可以直接去啃《數(shù)據(jù)結(jié)構(gòu)和算法》瑰排。
一贯要、學(xué)習(xí)二叉樹的重要性
- 工作面試時(shí)，經(jīng)常出現(xiàn)二叉樹相關(guān)算法
- 二叉樹是樹核心和重點(diǎn)
- 支持強(qiáng)大的搜索算法
- 樹椭住、森林是一種非常復(fù)雜數(shù)據(jù)結(jié)構(gòu)崇渗，但是樹、森林可以轉(zhuǎn)換成二叉樹去處理（三者可以相互轉(zhuǎn)換）
二京郑、橫掃基礎(chǔ)知識(shí)
什么是二叉樹宅广？二叉樹（Binary Tree）是 n （n >= 0）個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹）些举，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的跟狱、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。這是官方定義户魏，下面這棵樹就是傳說中的二叉樹驶臊，不會(huì)出現(xiàn)超過二個(gè)分支。
特點(diǎn)：
- 每個(gè)結(jié)點(diǎn)最多有兩棵子樹
- 左子樹和右子樹是有順序的不能任意顛倒叼丑，如下圖就是五棵不同的二叉樹关翎。
滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹鸠信，并且所有葉子都在同一層上纵寝，這樣的二叉樹為滿二叉樹。
這個(gè)定義看圖就能明白星立，就是一棵非常完美的二叉樹爽茴。
完全二叉樹：對(duì)一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為 i （1<= i <= n）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào) i 的結(jié)點(diǎn)在二叉樹中位置完全相同绰垂，則這棵二叉樹稱為完全二叉樹闹啦。
這定義最好結(jié)合滿二叉樹圖去理解，比如此圖i=4或者i=10在滿二叉樹圖中位置就是等于4和10≡樱現(xiàn)在腦補(bǔ)一下，假設(shè)將此圖i=5的左子樹（也就是i=10這個(gè)結(jié)點(diǎn)）荐健，移動(dòng)成i=7這個(gè)結(jié)點(diǎn)左子樹酱畅，那么這棵樹還是完全二叉樹嗎琳袄？答案肯定不是，因?yàn)闈M二叉樹圖i=7左子樹對(duì)應(yīng)的是i=14這個(gè)結(jié)點(diǎn)纺酸。
滿二叉一定是一棵完全二叉樹窖逗，但是完全二叉樹不一定是滿的。
作為兩種特殊的二叉樹餐蔬，滿二叉樹和完全二叉樹容易混淆碎紊，分不清也沒關(guān)系，知道有這兩棵樹就OK了樊诺。
二叉樹的五個(gè)性質(zhì)：(前三個(gè)要求掌握)
性質(zhì)1：在二叉樹的第 i 層上至多有 2^(i-1)個(gè)結(jié)點(diǎn)（i>=1）仗考。
性質(zhì)2：深度為k的二叉樹至多有 2^k - 1個(gè)結(jié)點(diǎn)（k>=1）。
性質(zhì)3：對(duì)任何一棵二叉樹 T 词爬，如果其終端結(jié)點(diǎn)數(shù)為 n0秃嗜，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1顿膨。
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k的度為[log(2)n]+1([X]表示向下取整)锅锨。
性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為[log(2)n]+1）的結(jié)點(diǎn)按層序編號(hào)，對(duì)任一結(jié)點(diǎn) i（1<=i<=n）有：
①如果i=1恋沃，則結(jié)點(diǎn) i 是二叉樹的根必搞，無雙親；如果i>1囊咏，則其雙親是結(jié)點(diǎn)[i/2]向下取整恕洲。
②如果2i>n，則結(jié)點(diǎn)i無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）匆笤；否則其左孩子是結(jié)點(diǎn)2i研侣。
③如果2i+1>n，則結(jié)點(diǎn)i無右孩子炮捧；否則其右孩子是結(jié)點(diǎn)2i+1.
三庶诡、二叉樹的遍歷（重要）
前面都是鋪墊，二叉樹遍歷才是主菜咆课，重點(diǎn)肯定也是難點(diǎn)末誓。
二叉樹遍歷原理：二叉樹的遍歷（traversing binary tree）是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點(diǎn)书蚪，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次喇澡。注意概念中的訪問和遍歷兩個(gè)關(guān)鍵詞。
二叉樹的遍歷方式有很多殊校，按從左到右遍歷主要分為前序遍歷晴玖、中序遍歷、后序遍歷和層序遍歷。
-
前序遍歷
前序遍歷的規(guī)則是若二叉樹為空呕屎，則空操作返回让簿，否則先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹秀睛，再前序遍歷右子樹尔当，如下圖，遍歷的順序?yàn)椋篈BDGHCEIF
前序遍歷 中序遍歷
中序遍歷是從根結(jié)點(diǎn)的左子樹開始蹂安，然后訪問根結(jié)點(diǎn)椭迎，最后中序遍歷右子樹，如下圖田盈，遍歷的順序?yàn)椋篏DHBAEICF
-
后序遍歷
從左到右先葉子結(jié)點(diǎn)的方式遍歷訪問左右子樹畜号，最后訪問根結(jié)點(diǎn)，如下圖缠黍，遍歷的順序?yàn)椋篏HDBIEFCA
后序遍歷 -
層序遍歷
從樹的第一層根結(jié)點(diǎn)弄兜，從上而下遍歷，同層從左到右訪問瓷式，如下圖替饿，遍歷順序?yàn)椋篈BCDEFGHI
層序遍歷
四、實(shí)戰(zhàn)
假設(shè)我們有如下這樣一棵二叉樹T贸典。這樹已經(jīng)用二叉鏈表結(jié)構(gòu)存儲(chǔ)在內(nèi)存當(dāng)中视卢。（之所以不使用原來的圖，僅僅希望能多舉一個(gè)例子廊驼，然后大家可以比較學(xué)習(xí)）
結(jié)點(diǎn)定義：
/*二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義*/
typedef int TElemType;
typedef struct BiTNode{//結(jié)點(diǎn)結(jié)構(gòu)
TElemType date;//結(jié)點(diǎn)數(shù)據(jù)
struct BiTNode *lchild,*rchild;//左右孩子指針
} BiTNode,*BiTree;
- 前序遍歷（遞歸算法）
void PreOrderTraverse(BiTree T){
if(T==null)
return;
printf("%c",T->data);/*顯示結(jié)點(diǎn)數(shù)據(jù)据过，可以更改為其他對(duì)結(jié)點(diǎn)操作*/
PreOrderTraverse(T->lchild);/*遍歷左子樹*/
PreOrderTraverse(T->rchild);/*遍歷右子樹*/
}
看到這里也許你會(huì)和我一樣失望，說好的前序遍歷呢妒挎，為什么這么幾行代碼就把前序遍歷解決了绳锅，不錯(cuò)你沒看錯(cuò)，別小看這幾行代碼酝掩，其實(shí)這幾行代碼才是無窮無盡的鳞芙，這就是遞歸算法！（網(wǎng)上說遞歸算法是神寫的期虾，迭代算法才是人寫的=_=）原朝。不了解遞歸算法的小伙伴趕快去看這篇文章《Java算法》。
分析：
①當(dāng)調(diào)用PreOrderTraverse(T)镶苞，T的根結(jié)點(diǎn)不為null喳坠，所以執(zhí)行printf，打印字母A茂蚓。
②接下來調(diào)用PreOrderTravers(T->lchild);訪問了A結(jié)點(diǎn)的左孩子壕鹉，不為null剃幌，執(zhí)行printf顯示字母B。
③在這里可以很清楚的看到打印B之后御板，會(huì)繼續(xù)執(zhí)行PreOrderTravers(T->lchild);訪問B結(jié)點(diǎn)的左孩子锥忿，執(zhí)行printf顯示字母D。
④再次遞歸調(diào)用PreOrderTravers(T->lchild),打印字母H怠肋。（一直到這里 PreOrderTraverse(T->rchild);方法從來沒有執(zhí)行過，只有當(dāng)左孩子PreOrderTraverse(T->lchild);遞歸完成才會(huì)執(zhí)行右孩子的遞歸）
⑤再次遞歸調(diào)用PreOrderTravers(T->lchild)淹朋；訪問了H孩子的左孩子笙各，此時(shí)因?yàn)镠結(jié)點(diǎn)無左孩子，所以T==null础芍，返回此函數(shù)杈抢。直到此時(shí)PreOrderTravers(T->lchild)；H這個(gè)結(jié)點(diǎn)的左孩子遞歸執(zhí)行完畢 仑性。此時(shí)遞歸調(diào)用PreOrderTravers(T->rchild)惶楼；訪問了H結(jié)點(diǎn)的右孩子，打印顯示字母K诊杆。
⑥再次遞歸調(diào)用PreOrderTravers(T->lchild)歼捐；訪問K的左孩子，沒有晨汹，則返回豹储。調(diào)用PreOrderTravers(T->rchild)；訪問K的右孩子也沒有淘这，則返回剥扣。于是此函數(shù)執(zhí)行完畢，返回到上一級(jí)遞歸的函數(shù)（即打印H結(jié)點(diǎn)時(shí)的函數(shù) ）铝穷，也執(zhí)行完畢钠怯，返回到打印結(jié)點(diǎn)D時(shí)的函數(shù)，訪問了D的函數(shù)曙聂，發(fā)現(xiàn)D結(jié)點(diǎn)沒有右孩子晦炊，繼續(xù)返回上一層遞歸函數(shù)，打印E筹陵。
⑦由于E沒有左右孩子刽锤，返回打印B時(shí)的遞歸函數(shù)，遞歸執(zhí)行完畢朦佩，返回到最初的PreOrderTravers并思，調(diào)用PreOrderTravers(T->rchild)；訪問結(jié)點(diǎn)A的右孩子语稠，打印字母C宋彼。依次類推弄砍，前序遍歷二叉樹的結(jié)點(diǎn)順序是：ABDHKECFIGJ。
如果還是不能理解输涕，可以一邊看代碼一邊畫圖音婶。能用遞歸算法實(shí)現(xiàn)的遍歷按照常理來說使用迭代算法也是可以實(shí)現(xiàn)的，并且在面試中容易被問到遍歷迭代算法應(yīng)注意什么莱坎。
迭代算法：
（迭代算法請(qǐng)看補(bǔ)充篇衣式，鏈接在文章末尾。）
- 中序遍歷（遞歸算法）
void InOrderTraverse(BiTree T){
if(T==null)
return;
InOrderTraverse(T->lchild);/*遍歷左子樹*/
printf("%c",T->data);/*顯示結(jié)點(diǎn)數(shù)據(jù)檐什，可以更改為其他對(duì)結(jié)點(diǎn)操作*/
InOrderTraverse(T->rchild);/*遍歷右子樹*/
}
分析：
①調(diào)用InOrderTraverse（T）碴卧，T的根結(jié)點(diǎn)不為null，于是調(diào)用 InOrderTraverse(T->lchild);訪問結(jié)點(diǎn)B乃正。當(dāng)前指針不為null住册，繼續(xù)調(diào)用 InOrderTraverse(T->lchild)；一直繼續(xù)調(diào)用瓮具；直到訪問結(jié)點(diǎn)H的左孩子荧飞，發(fā)現(xiàn)當(dāng)前指針為null，于是返回名党。打印當(dāng)前結(jié)點(diǎn)H叹阔。
②然后調(diào)用 InOrderTraverse(T->rchild);訪問結(jié)點(diǎn)H的右孩子K，因?yàn)榻Y(jié)點(diǎn)K沒有左孩子兑巾，所以打印K条获。
③因?yàn)榻Y(jié)點(diǎn)K沒有右孩子，所以返回蒋歌。打印結(jié)點(diǎn)H函數(shù)執(zhí)行完畢帅掘，返回。打印D堂油。
④D無右孩子修档，此函數(shù)執(zhí)行完畢，返回府框。打印B吱窝。
⑤后面都是相同的道理了，最終打印結(jié)點(diǎn)順序是：HKDBEAIFCGJ
迭代算法：
（迭代算法請(qǐng)看補(bǔ)充篇迫靖，鏈接在文章末尾院峡。）
- 后序遍歷（遞歸算法）
如果前序遍歷和中序遍歷弄明白了，后序遍歷很容易想到如何寫系宜，打印的結(jié)果是：KHDEBIFJGCA照激。
void PostOrderTraverse(BiTree T){
if(T==null)
return;
PostOrderTraverse(T->lchild);/*遍歷左子樹*/
PostOrderTraverse(T->rchild);/*遍歷右子樹*/
printf("%c",T->data);/*顯示結(jié)點(diǎn)數(shù)據(jù)，可以更改為其他對(duì)結(jié)點(diǎn)操作*/
}
迭代算法：
（迭代算法請(qǐng)看補(bǔ)充篇盹牧，鏈接在文章末尾俩垃。）
五励幼、總結(jié)：
樹和二叉樹的內(nèi)容還有很多，想了解更多細(xì)節(jié)的同學(xué)建議買本書好好研究口柳。我學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)挺遲的苹粟，雖然走了很多彎路，但是相比于有些人說這么難的東西跃闹，工作中又用不到嵌削，干嘛學(xué)呢，自己能認(rèn)識(shí)其重要性還是很幸運(yùn)的辣卒。我承認(rèn)以后參加工作掷贾，尤其是從事應(yīng)用層開發(fā)的人員，幾乎遇不到要求你來寫數(shù)據(jù)結(jié)構(gòu)和算法荣茫。但是有些事物不能因?yàn)槟愀惺懿坏剿鼛Ыo你的直接好處就不去做，就像閱讀场靴，也許現(xiàn)在并不能給你帶來直接的利益啡莉，但是卻在潛移默化影響著你的思想。
每月更新兩篇旨剥，質(zhì)量保證咧欣，點(diǎn)擊關(guān)注！
聽說點(diǎn)喜歡的人運(yùn)氣會(huì)一直很好９熘摹Ｆ枪尽！
