樹是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。樹的特點(diǎn)就是樹的每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；沒有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；每一個(gè)非根結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為多個(gè)不相交的子樹。這些只是樹的基本特性，有一些特殊的樹本身還有一些和其他樹不一樣的特性，本文我們就來為大家介紹數(shù)據(jù)結(jié)構(gòu)中7種樹。

1. 二叉樹

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

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

2. 二叉查找樹

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

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

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

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

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

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

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

3. 平衡二叉樹

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

4. B樹

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

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

5. B+樹

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

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

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

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

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

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

6. B*樹

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

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

7. Trie樹

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

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

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

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

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

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