樹是一種特殊的數據結構，它是由n(n>=1)個有限結點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。樹的特點就是樹的每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹。這些只是樹的基本特性，有一些特殊的樹本身還有一些和其他樹不一樣的特性，本文我們就來為大家介紹數據結構中7種樹。

1. 二叉樹

二叉樹是數據結構中一種重要的數據結構，也是樹表家族最為基礎的結構。

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

2. 二叉查找樹

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

1) 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

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

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

4) 沒有鍵值相等的節點。

二叉查找樹的性質：對二叉查找樹進行中序遍歷，即可得到有序的數列。

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

3. 平衡二叉樹

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

4. B樹

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

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

5. B+樹

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

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

2) 非葉子結點的子樹指針與關鍵字個數相同；

3) 非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區間）；

4) 為所有葉子結點增加一個鏈指針；

5）所有關鍵字都在葉子結點出現；

6. B*樹

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

B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）；

7. Trie樹

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

Tire樹的三個基本性質：

1) 根節點不包含字符，除根節點外每一個節點都只包含一個字符；

2) 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串；

3) 每個節點的所有子節點包含的字符都不相同。

以上就是數據結構中7種樹，當然，在這里我們只是簡單介紹了這數據結構中7種樹的定義和性質，但是要真正意義上掌握數據結構中7種樹，必須還有學習它們的數據結構，利用圖像表示法畫出正確的樹的結構圖。在本站的數據結構和算法教程中有這些樹的概述圖，方便我們更好的理解它們的數據結構和性質。