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

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

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

0、二叉樹

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

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

滿二叉樹與完全二叉樹是兩種特殊的二叉樹：

1、滿二叉樹

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

2,、完全二叉樹

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

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

3,、二叉鏈表

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

4,、穿線二叉樹

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

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

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

6,、二叉排序樹

二叉排序樹用于查找,。

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

所謂的二叉排序樹是這樣的：

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

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

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

7、B- 樹

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

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

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

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

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

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

8,、B+ 樹

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

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

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