樹(shù)是數(shù)據(jù)結(jié)構(gòu)中很重要的一環(huán)。工作中，也常常用到。

樹(shù)，是一種數(shù)據(jù)的表示結(jié)構(gòu)，主要用于算法中的查找、排序。常常與指針聯(lián)系在一起。

樹(shù)有許多種，讀書(shū)的時(shí)候，印象中就是一大堆樹(shù)，搞不清?，F(xiàn)在梳理一下：

0、二叉樹(shù)

1）非空二叉樹(shù)只有一個(gè)根節(jié)點(diǎn)（空的話，一個(gè)節(jié)點(diǎn)也沒(méi)有了，哪還是樹(shù)嗎？）

2）每個(gè)節(jié)點(diǎn)至多兩個(gè)子樹(shù)，成為左、右子樹(shù)

滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊的二叉樹(shù)：

1、滿二叉樹(shù)

除了葉子結(jié)點(diǎn)，每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)結(jié)點(diǎn)。

2、完全二叉樹(shù)

除最后一層，每一層的結(jié)點(diǎn)都達(dá)到最大值，且最后一層只缺少右邊的若干結(jié)點(diǎn)。完全二叉樹(shù)就是最后一層的右葉子結(jié)點(diǎn)可能會(huì)殘缺的二叉樹(shù)。

二叉樹(shù)的遍歷，按根結(jié)點(diǎn)遍歷的順序分為前序、中序、后序。

3、二叉鏈表

二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二叉樹(shù)每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)以由2部分組成：數(shù)據(jù)域與指針域。指針域有兩個(gè)，分別指向左右子結(jié)點(diǎn)。因此二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也成為二叉鏈表。

4、穿線二叉樹(shù)

二叉鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域。對(duì)于葉子結(jié)點(diǎn)來(lái)說(shuō)，沒(méi)有子節(jié)點(diǎn)，指針根本沒(méi)用。于是就可以用來(lái)存儲(chǔ)遍歷樹(shù)的順序，如同在二叉鏈表中增加了一條線索，故名穿線二叉樹(shù)。

5、最優(yōu)二叉樹(shù)

最優(yōu)二叉樹(shù)是構(gòu)造出來(lái)的。利用霍夫曼算法構(gòu)造出來(lái)的二叉樹(shù)叫最優(yōu)二叉樹(shù)。最優(yōu)二叉樹(shù)可以用來(lái)優(yōu)化算法。比如霍夫曼編碼。

6、二叉排序樹(shù)

二叉排序樹(shù)用于查找。

首先將無(wú)序表構(gòu)造成二叉排序樹(shù)，然后利用這個(gè)樹(shù)，就能很快的進(jìn)行查找鳥(niǎo)。

所謂的二叉排序樹(shù)是這樣的：

1）左子樹(shù)上的所有結(jié)點(diǎn)都小于根節(jié)點(diǎn)

2）右子樹(shù)上的所有結(jié)點(diǎn)都不小于根節(jié)點(diǎn)

3）左右子樹(shù)也滿足上述兩個(gè)要求

7、B- 樹(shù)

一種動(dòng)態(tài)調(diào)節(jié)的平衡多路查找樹(shù)，作用也是在于有利查找。

B-樹(shù)不一定是二叉樹(shù)，是多路樹(shù)。什么意思？就是一個(gè)結(jié)點(diǎn)有好多數(shù)據(jù)域組成，然后每個(gè)數(shù)據(jù)域左右兩邊都有一個(gè)指針域，一個(gè)結(jié)點(diǎn)有n個(gè)數(shù)據(jù)域的話，就會(huì)有n+1個(gè)指針域。

B-樹(shù)的定義很繁復(fù)，突出的2點(diǎn)就是：

1）數(shù)據(jù)域左邊的子樹(shù)中，所有數(shù)據(jù)域都小于它；右邊的子樹(shù)中，所有數(shù)據(jù)域都不小于它。

2）B-樹(shù)是有序的，從左到右，左小右大，數(shù)據(jù)散落在所有結(jié)點(diǎn)上，包括葉子、非葉子。

B-樹(shù)是分階的。所謂的階，就是每個(gè)結(jié)點(diǎn)可以放多少個(gè)數(shù)據(jù)域。比如，3階B-樹(shù)，就是每個(gè)結(jié)點(diǎn)最多有3個(gè)數(shù)據(jù)域。有數(shù)據(jù)加入或者刪減，那就要有所調(diào)整，甚至也許因?yàn)槟辰Y(jié)點(diǎn)放不下了，還要進(jìn)行裂變。

8、B+ 樹(shù)

B+樹(shù)是B-樹(shù)的變種。不同的是，數(shù)據(jù)散落在B-樹(shù)的所有結(jié)點(diǎn)上，而B(niǎo)+樹(shù)則是，位于非葉結(jié)點(diǎn)上的數(shù)據(jù)，在葉子結(jié)點(diǎn)上也會(huì)有一份。比如說(shuō)，數(shù)據(jù)52，在B-樹(shù)位于根節(jié)點(diǎn)，那么它在葉子結(jié)點(diǎn)上就沒(méi)有；但在B+樹(shù)，它在某個(gè)葉子結(jié)點(diǎn)上也會(huì)存在。就是說(shuō)，B+樹(shù)的葉子結(jié)點(diǎn)，有全部的數(shù)據(jù)。

到這里，說(shuō)SQL SERVER建了聚集索引的表，存儲(chǔ)結(jié)構(gòu)是B+樹(shù)就很好理解了。聚集索引字段，位于非葉子結(jié)點(diǎn)，而葉子結(jié)點(diǎn)，則包含全部字段。。。

寶貝、寶貝，我是你的大叔