對于程序員而言，樹這種數(shù)據(jù)結構是一種比較常見的數(shù)據(jù)結構，今天小編就來介紹一下數(shù)這種數(shù)據(jù)結構，然后介紹一個簡單的二叉樹的C語言實現(xiàn)。
前驅內容
前情回顧
首先，我們先來溫習一下什么是數(shù)據(jù)結構，我們之前介紹過，在實際使用數(shù)據(jù)的時候我們會把一些有關聯(lián)的點組合起來進行使用，這就是有結構的數(shù)據(jù)。我們也介紹過一種簡單的數(shù)據(jù)結構，這種數(shù)據(jù)結構的特點是一個數(shù)據(jù)連接著另一個數(shù)據(jù)，后一個數(shù)據(jù)連接著前一個數(shù)據(jù)。最后這些數(shù)據(jù)會像線一樣連成一串，這就是線性表。
什么是樹？
那么，有沒有一種情況，每個數(shù)據(jù)都可以連接多個數(shù)據(jù)呢？確實存在著這樣的情況，當每個數(shù)據(jù)連接著多個數(shù)據(jù)的時候，就是圖（后續(xù)文章會介紹）。當每個數(shù)據(jù)后面連接著0到多個數(shù)據(jù)，而前面指連接著一個數(shù)據(jù)的時候，就是樹，就像這樣：
樹狀圖是一種數(shù)據(jù)結構，它是由n（n>=1）個有限結點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
關于樹的結構
我們之前有談到數(shù)據(jù)之間的關系，對于線性表而言，一個數(shù)據(jù)只會連接另一個數(shù)據(jù)，這樣的關系我們稱為一對一的關系，也就是說，一個數(shù)據(jù)只會有一個后繼節(jié)點。
對于數(shù)而說，一個數(shù)據(jù)后面可能會連接一個數(shù)據(jù)，也可能連接多個數(shù)據(jù)，甚至有可能一個數(shù)據(jù)都沒有，這樣的關系我們稱為一對多的關系。
對于線性表而言，因為結構比較簡單，所以數(shù)據(jù)之間互相稱為前驅節(jié)點，后續(xù)節(jié)點，代表數(shù)據(jù)間的關系。而在樹中，明顯復雜得多。以下是對一顆數(shù)的結構描述（以下面的樹狀圖為例）：
1、結點(Node)：表示樹中的數(shù)據(jù)元素，由數(shù)據(jù)項和數(shù)據(jù)元素之間的關系組成。在圖中，共有10個結點。
2、結點的度(Degree of Node)：結點所擁有的子樹的個數(shù)，在圖中，結點A的度為3（注意，E,F也符合樹的定義（樹的定義見下文）所以B的度為2）。
3、樹的度(Degree of Tree)：樹中各結點度的最大值（節(jié)點A和D的度都為最大值3）。上圖中樹的度為3。
4、葉子結點(Leaf Node)：度為0的結點，也叫終端結點。上圖中，結點E、F、G、H、I、J都是葉子結點。
5、分支結點(Branch Node)：度不為0的結點，也叫非終端結點或內部結點。上圖中，結點A、B、C、D是分支結點。
6、孩子(Child)：結點子樹的根。上圖中，結點B、C、D是結點A的孩子。
7、雙親(Parent)：結點的上層結點叫該結點的雙親。上圖中，結點B、C、D的雙親是結點A。
8、祖先(Ancestor)：從根到該結點所經分支上的所有結點。上圖中，結點E的祖先是A和B。
9、子孫(Descendant)：以某結點為根的子樹中的任一結點。上圖中，除A之外的所有結點都是A的子孫。
10、兄弟(Brother)：同一雙親的孩子。上圖中，結點B、C、D互為兄弟。
11、結點的層次(Level of Node)：從根結點到樹中某結點所經路徑上的分支數(shù)稱為該結點的層次。根結點的層次規(guī)定為1，其余結點的層次等于其雙親結點的層次加1。
12、堂兄弟(Sibling)：同一層的雙親不同的結點。上圖中，G和H互為堂兄弟。
13、樹的深度(Depth of Tree)：樹中結點的最大層次數(shù)。上圖中，樹的深度為3。
14、無序樹(Unordered Tree)：樹中任意一個結點的各孩子結點之間的次序構成無關緊要的樹。通常樹指無序樹。
15、有序樹(Ordered Tree)：樹中任意一個結點的各孩子結點有嚴格排列次序的樹。二叉樹是有序樹，因為二叉樹中每個孩子結點都確切定義為是該結點的左孩子結點還是右孩子結點。
16、森林(Forest)：m(m≥0)棵樹的集合。自然界中的樹和森林的概念差別很大，但在數(shù)據(jù)結構中樹和森林的概念差別很小。從定義可知，一棵樹由根結點和m個子樹構成，若把樹的根結點刪除，則樹變成了包含m棵樹的森林。當然，根據(jù)定義，一棵樹也可以稱為森林。
如何判斷一個節(jié)點算不算樹（樹的定義）
- 有且僅有一個稱為根的結點。
- 如果n>1, 除根結點以外其它結點可以分為m(m>0)個不相交的集合T1,T2,T3,T4,......,Tm，其中每一個集合都是一棵樹。樹T1, T2, T3,......,Tm稱為這棵樹的子樹。
樹的種類
樹的種類
無序樹
樹的任意節(jié)點的子節(jié)點沒有順序關系。
有序樹
樹的任意節(jié)點的子節(jié)點有順序關系。
二叉樹
樹的任意節(jié)點至多包含兩棵子樹。二叉樹遍歷:二叉樹的遍歷是指從二叉樹的根結點出發(fā)，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次，且僅被訪問一次。二叉樹的訪問次序可以分為四種：前序遍歷 中序遍歷 后序遍歷 層次遍歷
滿二叉樹
葉子節(jié)點都在同一層并且除葉子節(jié)點外的所有節(jié)點都有兩個子節(jié)點。
完全二叉樹
對于一顆二叉樹，假設其深度為d（d>1）。除第d層外的所有節(jié)點構成滿二叉樹，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹；
完滿二叉樹
霍夫曼樹
帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。
二叉查找樹（二叉搜索樹、二叉排序樹、BST）[這幾個都是別名]
若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；任意節(jié)點的左、右子樹也分別為二叉查找樹；沒有鍵值相等的節(jié)點。
平衡二叉樹
它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，同時，平衡二叉樹必定是二叉搜索樹。
AVL樹
在計算機科學中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。AVL樹本質上還是一棵二叉搜索樹，它的特點是：1.本身首先是一棵二叉搜索樹。2.帶有平衡條件：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1。也就是說，AVL樹，本質上是帶了平衡功能的二叉查找樹（二叉排序樹，二叉搜索樹）。使用場景：AVL樹適合用于插入刪除次數(shù)比較少，但查找多的情況。也在Windows進程地址空間管理中得到了使用旋轉的目的是為了降低樹的高度，使其平衡
紅黑樹
紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:性質1. 節(jié)點是紅色或黑色。性質2. 根節(jié)點是黑色。性質3. 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)性質4. 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。使用場景：紅黑樹多用于搜索,插入,刪除操作多的情況下紅黑樹應用比較廣泛：1. 廣泛用在C++的STL中。map和set都是用紅黑樹實現(xiàn)的。2. 著名的linux進程調度Completely Fair Scheduler,用紅黑樹管理進程控制塊。3.epoll在內核中的實現(xiàn)，用紅黑樹管理事件塊4.nginx中，用紅黑樹管理timer等
伸展樹
伸展樹（Splay Tree），也叫分裂樹，是一種二叉排序樹，它能在O(log n)內完成插入、查找和刪除操作。它由丹尼爾·斯立特Daniel Sleator 和 羅伯特·恩卓·塔揚Robert Endre Tarjan 在1985年發(fā)明的。在伸展樹上的一般操作都基于伸展操作：假設想要對一個二叉查找樹執(zhí)行一系列的查找操作，為了使整個查找時間更小，被查頻率高的那些條目就應當經常處于靠近樹根的位置。于是想到設計一個簡單方法， 在每次查找之后對樹進行重構，把被查找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉查找樹，它會沿著從某個節(jié)點到樹根之間的路徑，通過一系列的旋轉把這個節(jié)點搬移到樹根去。它的優(yōu)勢在于不需要記錄用于平衡樹的冗余信息。
替罪羊樹
替罪羊樹是計算機科學中，一種基于部分重建的自平衡二叉搜索樹。在替罪羊樹上，插入或刪除節(jié)點的平攤最壞時間復雜度是O(log n)，搜索節(jié)點的最壞時間復雜度是O(log n)。在非平衡的二叉搜索樹中，每次操作以后檢查操作路徑，找到最高的滿足max(size(son_L),size(son_R))>alpha*size(this)的結點，重建整個子樹。這樣就得到了替罪羊樹，而被重建的子樹的原來的根就被稱為替罪羊節(jié)點。替罪羊樹替罪羊樹是一棵自平衡二叉搜索樹，由ArneAndersson提出。替罪羊樹的主要思想就是將不平衡的樹壓成一個序列,然后暴力重構成一顆平衡的樹。
B-tree（B-樹或者B樹）
一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質的樹：1、根結點至少有兩個子女；2、每個非根節(jié)點所包含的關鍵字個數(shù) j 滿足：┌m/2┐ - 1 <= j <= m - 1；3、除根結點以外的所有結點（不包括葉子結點）的度數(shù)正好是關鍵字總數(shù)加1，故內部子樹個數(shù) k 滿足：┌m/2┐ <= k <= m ；4、所有的葉子結點都位于同一層。
B樹(B-Tree)是一種自平衡的樹,它是一種多路搜索樹（并不是二叉的），能夠保證數(shù)據(jù)有序。同時它還保證了在查找、插入、刪除等操作時性能都能保持在O(logn)，為大塊數(shù)據(jù)的讀寫操作做了優(yōu)化,同時它也可以用來描述外部存儲(支持對保存在磁盤或者網(wǎng)絡上的符號表進行外部查找)
B+樹
B+樹是B樹的一種變形形式，B+樹上的葉子結點存儲關鍵字以及相應記錄的地址，葉子結點以上各層作為索引使用。一棵m階的B+樹定義如下:(1)每個結點至多有m個子女；(2)除根結點外，每個結點至少有[m/2]個子女，根結點至少有兩個子女；(3)有k個子女的結點必有k個關鍵字。B+樹的查找與B樹不同，當索引部分某個結點的關鍵字與所查的關鍵字相等時，并不停止查找，應繼續(xù)沿著這個關鍵字左邊的指針向下，一直查到該關鍵字所在的葉子結點為止。更適合文件索引系統(tǒng)原因： 增刪文件（節(jié)點）時，效率更高，因為B+樹的葉子節(jié)點包含所有關鍵字，并以有序的鏈表結構存儲，這樣可很好提高增刪效率使用場景：文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中常用的B/B+ 樹，他通過對每個節(jié)點存儲個數(shù)的擴展，使得對連續(xù)的數(shù)據(jù)能夠進行較快的定位和訪問，能夠有效減少查找時間，提高存儲的空間局部性從而減少IO操作。他廣泛用于文件系統(tǒng)及數(shù)據(jù)庫中，如：Windows：HPFS 文件系統(tǒng)Mac：HFS，HFS+ 文件系統(tǒng)Linux：ResiserFS，XFS，Ext3FS，JFS 文件系統(tǒng)數(shù)據(jù)庫：ORACLE，MYSQL，SQLSERVER 等中B樹：有序數(shù)組+平衡多叉樹B+樹：有序數(shù)組鏈表+平衡多叉樹
B*樹
B*樹是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；B*樹定義了非葉子結點關鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）。B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數(shù)據(jù)復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分數(shù)據(jù)移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數(shù)據(jù)到新結點，最后在父結點增加新結點的指針；所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高；
字典樹
又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。它有3個基本性質：根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符；從根節(jié)點到某一節(jié)點，路徑上經過的字符連接起來，為該節(jié)點對應的字符串；每個節(jié)點的所有子節(jié)點包含的字符都不相同。
線索二叉樹
在二叉樹的結點上加上線索的二叉樹稱為線索二叉樹，對二叉樹以某種遍歷方式（如先序、中序、后序或層次等）進行遍歷，使其變?yōu)榫€索二叉樹的過程稱為對二叉樹進行線索化。
總結一下：
該處內容來自知乎大佬的總結，原文章請查看：https://zhuanlan.zhihu.com/p/90255760
