慶哥：?小白啊，知道什么是樹嗎窘哈？

小白：?啥玩意窝爪？什么是樹亿笤，我也是受過九年義務(wù)教育的啊硕盹，不知道什么是樹那還得了，不就是楊條啊祈坠，春樹啊

慶哥：?等等害碾，楊條是什么鬼啊，我說的此樹非彼樹啊赦拘，我說的是數(shù)據(jù)結(jié)構(gòu)中的概念

小白：?尷了個(gè)大尬慌随，數(shù)據(jù)結(jié)構(gòu)中的樹啊，經(jīng)程赏看但是說不上來阁猜，慶哥給我講講吧，最好大白話的去講蹋艺，我理解力差

慶哥：?可以可以剃袍，我最擅長(zhǎng)大白話解釋復(fù)雜概念了，走起车海，安排上

那你想想，在數(shù)據(jù)結(jié)構(gòu)中為什么叫樹呢隘击？

小白：?我覺得一般就是形似侍芝，也就是結(jié)構(gòu)應(yīng)該差不多，數(shù)據(jù)結(jié)構(gòu)中的樹這種結(jié)構(gòu)應(yīng)該和樹的形狀有關(guān)聯(lián)

慶哥：?哈哈埋同，聰明州叠，數(shù)據(jù)結(jié)構(gòu)中的樹就是和現(xiàn)實(shí)中的樹長(zhǎng)得差不多，我們來看看現(xiàn)實(shí)中的樹是不是都類似這個(gè)樣子：

哈哈凶赁，我這里畫的只是個(gè)模擬圖咧栗，大致就這樣，一棵樹有樹干虱肄，然后有各個(gè)樹枝致板，然后還有各種叉子

小白：?嗯嗯，畫得不賴咏窿，那數(shù)據(jù)機(jī)構(gòu)中的樹也是這樣斟或？

慶哥：?數(shù)據(jù)結(jié)構(gòu)中的樹是這樣的：

這就是數(shù)據(jù)結(jié)構(gòu)中用樹這個(gè)結(jié)構(gòu)去存儲(chǔ)集合{A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意圖了，它和樹有相似的地方集嵌，準(zhǔn)確來說應(yīng)該反著看和樹的形狀更像萝挤，你就記住御毅，樹結(jié)構(gòu)和真實(shí)的樹形狀類似，現(xiàn)在你先不用管其他的怜珍，先來看這個(gè)圖端蛆，你看看這其中的每個(gè)數(shù)據(jù)，也就是ABC那些有什么關(guān)系呢酥泛？

小白：?這樣啊今豆，每個(gè)數(shù)據(jù)之間都是連著的，這是不是說明每個(gè)數(shù)據(jù)之間都是有關(guān)系的揭璃，就比如數(shù)據(jù)A與B,C,D都有關(guān)系晚凿。

慶哥：?是的，我們?cè)谥敖榻B的數(shù)組瘦馍，鏈表歼秽，棧和隊(duì)列等等都是線性存儲(chǔ)結(jié)構(gòu)，但是我們今天要介紹的這個(gè)樹結(jié)構(gòu)則不是線性結(jié)構(gòu)了情组，對(duì)于線性結(jié)構(gòu)燥筷，它們的數(shù)據(jù)基本上是hi一對(duì)一的關(guān)系，但是樹結(jié)構(gòu)從上面的圖中也可以看得出來院崇，它是一對(duì)多的關(guān)系肆氓，所以樹結(jié)構(gòu)是一種非線性數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)的數(shù)據(jù)是具有一對(duì)多的特點(diǎn)底瓣。

從圖中我們看得出來比如A數(shù)據(jù)是和B,C,D都有關(guān)系的谢揪，再拿數(shù)據(jù)B來說，它是與E和F都有關(guān)系的捐凭，因此啊拨扶，我們把這種存儲(chǔ)結(jié)構(gòu)叫為“”樹型“”存儲(chǔ)結(jié)構(gòu)

小白：?曉得了，就是這種結(jié)構(gòu)跟樹的結(jié)構(gòu)差不多茁肠，樹干上有樹枝患民，每個(gè)樹枝上可能還有其他小樹枝，對(duì)吧

慶哥：?完全正確垦梆，接下來我們繼續(xù)學(xué)習(xí)關(guān)于樹的幾個(gè)概念匹颤，對(duì)了，我們接下來說的樹可都是指的樹型結(jié)構(gòu)托猩，可不是你說的楊條哦

小白：

關(guān)于樹的節(jié)點(diǎn)

那什么是節(jié)點(diǎn)呢印蓖？

慶哥：?關(guān)于這里，我發(fā)現(xiàn)有叫做節(jié)點(diǎn)京腥，也有叫做結(jié)點(diǎn)的另伍，反正都是一個(gè)意思啦，那什么是節(jié)點(diǎn)啊，其實(shí)也很簡(jiǎn)單摆尝，看圖你就能猜得出來什么是節(jié)點(diǎn)温艇？畢竟你是接受過九年義務(wù)教育的

小白：?我猜啊，這個(gè)節(jié)點(diǎn)應(yīng)該指的就是樹結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)啊堕汞，也就是下圖的每一個(gè)圓圈

慶哥：?對(duì)的勺爱，就是這樣的，比如圖中的數(shù)據(jù)A或者B讯检，它其實(shí)就是一個(gè)節(jié)點(diǎn)琐鲁，那么怎么定義這個(gè)節(jié)點(diǎn)呢？

節(jié)點(diǎn)：使用樹結(jié)構(gòu)存儲(chǔ)的每一個(gè)數(shù)據(jù)元素都被稱為“節(jié)點(diǎn)”人灼。比如 A就是一個(gè)節(jié)點(diǎn)

根節(jié)點(diǎn)

那就這個(gè)節(jié)點(diǎn)來說围段，圖中每個(gè)數(shù)據(jù)其實(shí)都是一個(gè)節(jié)點(diǎn)，但是根據(jù)每個(gè)節(jié)點(diǎn)所處的位置不同投放，它們還有各自獨(dú)特的命名奈泪，什么嘞？你看啊灸芳，比如圖中的A節(jié)點(diǎn)涝桅，你看看它是不是很特殊？

小白：?確實(shí)啊烙样，最上面冯遂，老大節(jié)點(diǎn)

慶哥：?什么啊，準(zhǔn)確來說谒获，它是根節(jié)點(diǎn)蛤肌，為啥叫根節(jié)點(diǎn)，你想批狱，如果是一棵樹的話裸准，它是不是相當(dāng)于在最下面，類似樹根了精耐，說一也叫作樹根節(jié)點(diǎn)狼速，簡(jiǎn)稱根節(jié)點(diǎn)琅锻，然后你再看卦停，它還有什么特點(diǎn)？

小白：?還有什么嘞恼蓬？哦哦惊完，它應(yīng)該只有一個(gè)吧，也就是說只有一個(gè)根點(diǎn)处硬，一棵樹不可能有兩個(gè)樹根吧

慶哥：?說的很對(duì)小槐，對(duì)于樹結(jié)構(gòu)來說，它只有一個(gè)根節(jié)點(diǎn)，那怎么來給根節(jié)點(diǎn)下一個(gè)定義呢凿跳？那要來看另外一個(gè)節(jié)點(diǎn)叫做父節(jié)點(diǎn)

父節(jié)點(diǎn)件豌，子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)

慶哥：?那什么是父節(jié)點(diǎn)嘞？你說

小白：?父節(jié)點(diǎn)控嗜？這個(gè)有點(diǎn)懵啊

慶哥：?這個(gè)也好理解啊茧彤，父節(jié)點(diǎn)，就是父親疆栏，兒子和兄弟這些概念曾掂，你看圖中的B，它就是一個(gè)父節(jié)點(diǎn)壁顶，這個(gè)其實(shí)要找一個(gè)參照來說珠洗，不能孤立的來說哪個(gè)是父節(jié)點(diǎn)，對(duì)于B來說若专，E和F在它的下面许蓖，所以有這么一個(gè)關(guān)系就是B是E和F的父節(jié)點(diǎn)，而E和F是它們的子節(jié)點(diǎn)富岳，這么一說好理解吧

在這里蛔糯，這個(gè)父節(jié)點(diǎn)也可以叫做雙親節(jié)點(diǎn)，而子節(jié)點(diǎn)也可以叫做孩子節(jié)點(diǎn)窖式，怎么樣蚁飒，這些概念名詞都很形象化啊

小白：?你這么一說倒是清楚的很/p>

葉子節(jié)點(diǎn)

慶哥：?然后還有一個(gè)葉子節(jié)點(diǎn)的概念，這個(gè)更好理解萝喘，葉子節(jié)點(diǎn)淮逻，葉子，不就是樹葉子嗎阁簸，那你說哪些是葉子節(jié)點(diǎn)

小白：?這個(gè)啊爬早，應(yīng)該就是最邊上的吧，也就是K,L,F這些

慶哥：?完全正確启妹，說白了筛严，葉子節(jié)點(diǎn)就是那些沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，那么我們?cè)賮砜慈拿祝趺磁袛嗄膫€(gè)是根節(jié)點(diǎn)呢桨啃？

小白：?這個(gè)，我看看檬输，應(yīng)該就是沒有父節(jié)點(diǎn)的話就是根節(jié)點(diǎn)吧

慶哥：?很正確啊照瘾，根節(jié)點(diǎn)的判斷依據(jù)就是如果一個(gè)結(jié)點(diǎn)沒有父結(jié)點(diǎn)，那么這個(gè)結(jié)點(diǎn)就是整棵樹的根結(jié)點(diǎn)丧慈。好了析命，我們繼續(xù)說其他概念

子樹和空樹

慶哥：?這里的子樹其實(shí)就可以根據(jù)子節(jié)點(diǎn)來說，比如上圖，A是根節(jié)點(diǎn)鹃愤，但是如果你單看節(jié)點(diǎn) B簇搅、E、F软吐、K馍资、L 組成的部分來說，也是一棵樹关噪，而且節(jié)點(diǎn) B 為這棵樹的根結(jié)點(diǎn)鸟蟹。所以稱 B、E使兔、F建钥、K、L 這幾個(gè)結(jié)點(diǎn)組成的樹為整棵樹的子樹虐沥；同樣熊经，結(jié)點(diǎn)E、K欲险、L 構(gòu)成的也是一棵子樹镐依，根結(jié)點(diǎn)為 E。

腫么樣天试，這也好理解吧

小白：?嗯嗯槐壳，不過這里我有個(gè)疑問啊，那這樣的話喜每，一個(gè)單個(gè)節(jié)點(diǎn)是不是也可以看做是一棵樹呢务唐？只不過是一顆光禿禿的樹

慶哥：?這個(gè)問題提的可以啊，這里要注意带兜，正如你想的那樣枫笛，單個(gè)結(jié)點(diǎn)也是一棵樹，只不過根節(jié)點(diǎn)就是它本身刚照。圖 中刑巧，節(jié)點(diǎn) K、L无畔、F 等都是樹啊楚，且都是整棵樹的子樹。

那啥是空樹知道不

小白：?這個(gè)啊檩互，就是啥數(shù)據(jù)都沒有吧特幔，沒有任何節(jié)點(diǎn)咨演，一個(gè)空集合吧闸昨。

慶哥：?非常正確，這里再補(bǔ)充一點(diǎn)，你可以看圖饵较，有沒有發(fā)現(xiàn)拍嵌，具有同一個(gè)根節(jié)點(diǎn)的子樹是互不聯(lián)系的，也就是各個(gè)子樹之間不能有交集循诉，就比如圖中横辆，我們可以看到除了根節(jié)點(diǎn) A，其余各個(gè)數(shù)據(jù)又各自構(gòu)成了三個(gè)子樹茄猫，根結(jié)點(diǎn)分別為 B狈蚤、C、D划纽，這三個(gè)子樹相互之間沒有相同的節(jié)點(diǎn)脆侮。如果有的話，那就破壞了樹的結(jié)構(gòu)勇劣，不能算做是一棵樹靖避。

小白：?嗯嗯，這點(diǎn)確實(shí)需要好好記一下比默！

節(jié)點(diǎn)的度和層次

慶哥：?我們接著來說樹的另外兩個(gè)概念幻捏，那就是度和層次，這又是啥嘞命咐，我們?cè)谏厦嬉呀?jīng)分析了什么是子樹篡九，那么度就好理解了：

度：對(duì)于一個(gè)節(jié)點(diǎn)而言，擁有的子樹數(shù)稱為節(jié)點(diǎn)的度（Degree）醋奠。比如瓮下，圖中根節(jié)點(diǎn) A 下分出了 3 個(gè)子樹（BCD），所以钝域，結(jié)點(diǎn) A 的度為 3讽坏。

這也好理解吧，有個(gè)例子一看就明白了例证，這里說的是針對(duì)單個(gè)節(jié)點(diǎn)來說路呜，那么對(duì)于一棵樹而言，它的度是多少呢织咧？

樹的度：一棵樹的度是樹內(nèi)各節(jié)點(diǎn)的度的最大值胀葱。圖 中，各個(gè)節(jié)點(diǎn)的度的最大值為 3笙蒙，所以抵屿，整棵樹的度的值是 3。咋樣捅位，

理解不

小白： 嗯嗯轧葛，看著圖很好理解這些概念

慶哥：?嗯嗯搂抒，那繼續(xù)說層次，也就是節(jié)點(diǎn)的層次尿扯，這個(gè)更好理解求晶，看圖：

是不是很好理解，然后這里還有個(gè)概念衷笋，那就是樹的深度也可以叫高度

樹的高度（深度）

那什么是深度（高度）呢芳杏？

一棵樹的深度（高度）是樹中節(jié)點(diǎn)所在的最大的層次。上圖樹的深度為 4辟宗。

對(duì)了上面好像沒有說什么是兄弟節(jié)點(diǎn)：

如果兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)雖不相同爵赵，但是它們的父節(jié)點(diǎn)處在同一層次上，那么這兩個(gè)節(jié)點(diǎn)互為堂兄弟泊脐，也即是兄弟節(jié)點(diǎn)亚再，比如，節(jié)點(diǎn) G 和E晨抡、F氛悬、H、I耘柱、J 的父結(jié)點(diǎn)都在第二層如捅，所以之間為堂兄弟的關(guān)系。

ok调煎，這些概念也講清楚了吧

小白：?沒問題的/p>

有序樹和無序樹

慶哥：?咱們這里再來談兩個(gè)概念镜遣，就是有序樹和無序樹，這又是什么呢士袄？

你看啊悲关，如果樹中節(jié)點(diǎn)的子樹從左到右看，誰在左邊娄柳，誰在右邊寓辱，是有規(guī)定的，那么這棵樹稱為有序樹赤拒；反之就稱為無序樹秫筏，你看這也好理解吧

基于此，就有新的概念了挎挖，在有序樹中这敬，一個(gè)節(jié)點(diǎn)最左邊的子樹稱為"第一個(gè)孩子"，最右邊的稱為"最后一個(gè)孩子"蕉朵。

舉例來說崔涂，如果上圖中的樹其本身是一棵有序樹，則以節(jié)點(diǎn) B 為根節(jié)點(diǎn)的子樹為整棵樹的第一個(gè)孩子始衅，以節(jié)點(diǎn) D 為根節(jié)點(diǎn)的子樹為整棵樹的最后一個(gè)孩子冷蚂。

ok缭保，到這里就差不多了，下面咱們來總結(jié)一下

總結(jié)

到了這里知道了啥是樹了吧帝雇，看圖：

對(duì)于樹這種存儲(chǔ)結(jié)構(gòu)啊，它從邏輯上來看蛉拙，就類似我們生活中見到的樹一樣尸闸，只不過是倒過來的，而且我們?cè)诹私饬岁P(guān)于樹的一些概念之后孕锄，比如父子節(jié)點(diǎn)這些吮廉，是不是感覺更像我們熟知的家族圖譜一樣，每個(gè)節(jié)點(diǎn)之間有這樣的父子畸肆，兄弟關(guān)系宦芦。

經(jīng)過上面的講解，對(duì)于樹啊轴脐，你要知道各種節(jié)點(diǎn)是怎么一回事调卑，然后還要會(huì)計(jì)算各個(gè)幾點(diǎn)的度和層次，當(dāng)然樹的深度也必須要知道大咱。

關(guān)于樹啊恬涧，這才是剛剛開始，知識(shí)先了解基礎(chǔ)概念碴巾，后面還有很多內(nèi)容嘞溯捆，比如二叉樹，紅黑樹厦瓢，我猜你肯定聽過提揍，這些內(nèi)容我們以后再詳細(xì)探討，今天就先到煮仇！再會(huì)劳跃！