前面講的都是線性表結(jié)構(gòu)陵珍，棧、隊(duì)列等等违施。今天講一種非線性表結(jié)構(gòu)互纯，樹(shù)。樹(shù)這種數(shù)據(jù)結(jié)構(gòu)比線性表的數(shù)據(jù)結(jié)構(gòu)要復(fù)雜得多磕蒲，內(nèi)容也比較多留潦，所以我會(huì)分四節(jié)來(lái)講解。
二叉樹(shù)有哪幾種存儲(chǔ)方式辣往？什么樣的二叉樹(shù)適合用數(shù)組來(lái)存儲(chǔ)兔院？
樹(shù)
關(guān)于樹(shù)，有幾個(gè)比較常用的概念需要掌握站削，那就是：根節(jié)點(diǎn)坊萝、葉子節(jié)點(diǎn)、父節(jié)點(diǎn)钻哩、子節(jié)點(diǎn)屹堰、兄弟節(jié)點(diǎn)，還有節(jié)點(diǎn)的高度街氢、深度扯键、層數(shù)，以及樹(shù)的高度珊肃。
這里主要來(lái)明晰一下高度（Height）荣刑、深度（Depth）、層（Level）伦乔。
節(jié)點(diǎn)的高度 = 該節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑（邊數(shù)）
節(jié)點(diǎn)的深度 = 根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所經(jīng)歷的邊的個(gè)數(shù)
節(jié)點(diǎn)的層數(shù) = 節(jié)點(diǎn)的深度 + 1
樹(shù)的高度 = 根節(jié)點(diǎn)的高度
高度和深度按照常識(shí)來(lái)計(jì)數(shù)厉亏，分別是從下往上、從上往下烈和，從 0 開(kāi)始計(jì)數(shù)爱只；
層數(shù)規(guī)定根節(jié)點(diǎn)位于第 1 層，從 1 開(kāi)始計(jì)數(shù)招刹。
二叉樹(shù)
滿(mǎn)二叉樹(shù)：每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)的樹(shù)
完全二叉樹(shù)：除了最后一層恬试，其他層的節(jié)點(diǎn)個(gè)數(shù)達(dá)到最大窝趣，最后一層的葉子節(jié)點(diǎn)都靠左連續(xù)排列。
滿(mǎn)二叉樹(shù)是特殊的完全二叉樹(shù)训柴。
為什么偏偏把最后一層的葉子節(jié)點(diǎn)靠左排列的叫完全二叉樹(shù)呢哑舒？靠右不行嗎？
要理解完全二叉樹(shù)定義的由來(lái)幻馁，我們需要先了解洗鸵，如何表示（或者存儲(chǔ)）一棵二叉樹(shù)？
兩種方法仗嗦，一種是基于指針或者引用的二叉鏈?zhǔn)酱鎯?chǔ)法膘滨，一種是基于數(shù)組的順序存儲(chǔ)法。
關(guān)于數(shù)組順序存儲(chǔ)法儒将，總結(jié)一下吏祸，如果節(jié)點(diǎn) X 存儲(chǔ)在數(shù)組中下標(biāo)為 i 的位置，下標(biāo)為 2 * i 的位置存儲(chǔ)的就是左子節(jié)點(diǎn)钩蚊，下標(biāo)為 2 * i + 1 的位置存儲(chǔ)的就是右子節(jié)點(diǎn)贡翘。反過(guò)來(lái)，下標(biāo)為 i/2 的位置存儲(chǔ)就是它的父節(jié)點(diǎn)砰逻。
通過(guò)這種方式鸣驱，我們只要知道根節(jié)點(diǎn)存儲(chǔ)的位置（一般情況下，為了方便計(jì)算子節(jié)點(diǎn)蝠咆，根節(jié)點(diǎn)會(huì)存儲(chǔ)在下標(biāo)為 1 的位置）踊东，這樣就可以通過(guò)下標(biāo)計(jì)算，把整棵樹(shù)都串起來(lái)刚操。
剛剛舉的例子是一棵完全二叉樹(shù)闸翅，所以?xún)H僅“浪費(fèi)”了一個(gè)下標(biāo)為 0 的存儲(chǔ)位置。如果是非完全二叉樹(shù)菊霜，其實(shí)會(huì)浪費(fèi)比較多的數(shù)組存儲(chǔ)空間坚冀。
所以，如果某棵二叉樹(shù)是一棵完全二叉樹(shù)鉴逞，那用數(shù)組存儲(chǔ)無(wú)疑是最節(jié)省內(nèi)存的一種方式记某。因?yàn)閿?shù)組的存儲(chǔ)方式并不需要像鏈?zhǔn)酱鎯?chǔ)法那樣要存儲(chǔ)額外的左右子節(jié)點(diǎn)的指針。這也是為什么完全二叉樹(shù)會(huì)單獨(dú)拎出來(lái)的原因构捡，也是為什么完全二叉樹(shù)要求最后一層的子節(jié)點(diǎn)都靠左的原因液南。
后面講堆和堆排序的時(shí)候，你會(huì)發(fā)現(xiàn)堆就是一種完全二叉樹(shù)勾徽，最常用的存儲(chǔ)方式就是數(shù)組滑凉。
二叉樹(shù)的遍歷
如何將所有節(jié)點(diǎn)都遍歷打印出來(lái)呢？經(jīng)典的方法有三種，前序遍歷譬涡、中序遍歷和后序遍歷闪幽。其中啥辨，前涡匀、中、后序溉知，表示的是節(jié)點(diǎn)與它的左右子樹(shù)節(jié)點(diǎn)遍歷打印的先后順序陨瘩。
前序遍歷是指，對(duì)于樹(shù)中的任意節(jié)點(diǎn)來(lái)說(shuō)级乍，先打印這個(gè)節(jié)點(diǎn)舌劳，然后再打印它的左子樹(shù)，最后打印它的右子樹(shù)玫荣。
中序遍歷是指甚淡，對(duì)于樹(shù)中的任意節(jié)點(diǎn)來(lái)說(shuō)，先打印它的左子樹(shù)捅厂，然后再打印它本身贯卦，最后打印它的右子樹(shù)。
后序遍歷是指焙贷，對(duì)于樹(shù)中的任意節(jié)點(diǎn)來(lái)說(shuō)撵割，先打印它的左子樹(shù)，然后再打印它的右子樹(shù)辙芍，最后打印這個(gè)節(jié)點(diǎn)本身啡彬。
二叉樹(shù)的前、中故硅、后序遍歷就是一個(gè)遞歸的過(guò)程庶灿。
前序遍歷的遞推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍歷的遞推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍歷的遞推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
有了遞推公式，代碼寫(xiě)起來(lái)就簡(jiǎn)單多了吃衅，這是前序遍歷的偽代碼往踢。
二叉樹(shù)遍歷的時(shí)間復(fù)雜度是多少？
可以看出來(lái)捐晶，每個(gè)節(jié)點(diǎn)最多會(huì)被訪問(wèn)兩次菲语，所以遍歷操作的時(shí)間復(fù)雜度，跟節(jié)點(diǎn)的個(gè)數(shù) n 成正比惑灵，也就是說(shuō)二叉樹(shù)遍歷的時(shí)間復(fù)雜度是 O(n)山上。
課后思考
給定一組數(shù)據(jù)，比如 1英支，3佩憾，5，6，9妄帘，10楞黄。你來(lái)算算，可以構(gòu)建出多少種不同的二叉樹(shù)抡驼？
我們講了三種二叉樹(shù)的遍歷方式鬼廓，前、中致盟、后序碎税。實(shí)際上，還有另外一種遍歷方式馏锡，也就是按層遍歷雷蹂，你知道如何實(shí)現(xiàn)嗎？
