樹(shù)是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。樹(shù)的特點(diǎn)就是樹(shù)的每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)；每一個(gè)非根結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)。這些只是樹(shù)的基本特性，有一些特殊的樹(shù)本身還有一些和其他樹(shù)不一樣的特性，本文我們就來(lái)為大家介紹數(shù)據(jù)結(jié)構(gòu)中7種樹(shù)。

1. 二叉樹(shù)

二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)中一種重要的數(shù)據(jù)結(jié)構(gòu)，也是樹(shù)表家族最為基礎(chǔ)的結(jié)構(gòu)。

二叉樹(shù)的定義：二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)(不存在度大于2的結(jié)點(diǎn))，二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒。二叉樹(shù)的第i層至多有2i-1個(gè)結(jié)點(diǎn)；深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

2. 二叉查找樹(shù)

二叉查找樹(shù)定義：又稱(chēng)為是二叉排序樹(shù)（Binary Sort Tree）或二叉搜索樹(shù)。二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

1) 若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

2) 若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；

3) 左、右子樹(shù)也分別為二叉排序樹(shù)；

4) 沒(méi)有鍵值相等的節(jié)點(diǎn)。

二叉查找樹(shù)的性質(zhì)：對(duì)二叉查找樹(shù)進(jìn)行中序遍歷，即可得到有序的數(shù)列。

二叉查找樹(shù)的時(shí)間復(fù)雜度：它和二分查找一樣，插入和查找的時(shí)間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會(huì)有O(n)的時(shí)間復(fù)雜度。原因在于插入和刪除元素的時(shí)候，樹(shù)沒(méi)有保持平衡。

3. 平衡二叉樹(shù)

平衡二叉樹(shù)定義：平衡二叉樹(shù)（Balanced Binary Tree）又被稱(chēng)為AVL樹(shù)（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。平衡二叉樹(shù)的常用算法有紅黑樹(shù)、AVL樹(shù)等。在平衡二叉搜索樹(shù)中，我們可以看到，其高度一般都良好地維持在O(log2n)，大大降低了操作的時(shí)間復(fù)雜度。

4. B樹(shù)

B樹(shù)也是一種用于查找的平衡樹(shù)，但是它不是二叉樹(shù)。

B樹(shù)的定義：B樹(shù)（B-tree）是一種樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，能夠用來(lái)存儲(chǔ)排序后的數(shù)據(jù)。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、循序存取、插入數(shù)據(jù)及刪除的動(dòng)作，都在對(duì)數(shù)時(shí)間內(nèi)完成。B樹(shù)，概括來(lái)說(shuō)是一個(gè)一般化的二叉查找樹(shù)，可以擁有多于2個(gè)子節(jié)點(diǎn)。與自平衡二叉查找樹(shù)不同，B-樹(shù)為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫(xiě)操作。B-tree算法減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程，從而加快存取速度。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)的實(shí)作上。

5. B+樹(shù)

B+樹(shù)是B樹(shù)的變體，也是一種多路搜索樹(shù)：

1) 其定義基本與B-樹(shù)相同，除了：

2) 非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同；

3) 非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù)（B-樹(shù)是開(kāi)區(qū)間）；

4) 為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；

5）所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；

6. B*樹(shù)

B*樹(shù)是B+樹(shù)的變體，在B+樹(shù)的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3。

B*樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹(shù)的1/2）；

7. Trie樹(shù)

Tire樹(shù)稱(chēng)為字典樹(shù)，又稱(chēng)單詞查找樹(shù)，Trie樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢(xún)時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢(xún)效率比哈希樹(shù)高。　

Tire樹(shù)的三個(gè)基本性質(zhì)：

1) 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符；

2) 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；

3) 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

以上就是數(shù)據(jù)結(jié)構(gòu)中7種樹(shù)，當(dāng)然，在這里我們只是簡(jiǎn)單介紹了這數(shù)據(jù)結(jié)構(gòu)中7種樹(shù)的定義和性質(zhì)，但是要真正意義上掌握數(shù)據(jù)結(jié)構(gòu)中7種樹(shù)，必須還有學(xué)習(xí)它們的數(shù)據(jù)結(jié)構(gòu)，利用圖像表示法畫(huà)出正確的樹(shù)的結(jié)構(gòu)圖。在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中有這些樹(shù)的概述圖，方便我們更好的理解它們的數(shù)據(jù)結(jié)構(gòu)和性質(zhì)。