一、數(shù)據(jù)結(jié)構(gòu)與算法中，樹的應(yīng)用

1、xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹，示例：

2、文件系統(tǒng)的目錄結(jié)構(gòu)

Linux操作系統(tǒng)就應(yīng)用了文件目錄樹，目錄樹的起點是根目錄，Linux文件系統(tǒng)中每一文件在此目錄樹中的文件名都是獨一無二的，因為其包含從根目錄開始的完整路徑。

3、MySQL數(shù)據(jù)庫索引

MySQL數(shù)據(jù)庫生成索引的數(shù)據(jù)結(jié)構(gòu)，就是應(yīng)用了排序二叉樹也稱為搜索二叉樹中的B+樹。

4、路由協(xié)議也是使用了樹的算法。

例如：STP生成樹協(xié)議，確保網(wǎng)絡(luò)中沒有環(huán)路；SPF優(yōu)異樹協(xié)議，不僅確保沒有環(huán)路，還保障網(wǎng)絡(luò)路徑優(yōu)異即：網(wǎng)絡(luò)路徑代價最小。

5、數(shù)據(jù)文件壓縮

典型代表：哈夫曼樹也稱為優(yōu)異二叉樹。

應(yīng)用場景：哈夫曼樹的應(yīng)用很廣.

哈夫曼編碼就是其在電訊通信中的應(yīng)用之一,在電訊通信業(yè)務(wù)中，通常用二進制編碼來表示字母或其他字符，并用這樣的編碼來表示字符序列。

廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法,其壓縮率通常在20%～90%之間。

6、深度優(yōu)先搜索算法（英語：Depth-First-Search，簡稱DFS）是一種用于遍歷或搜索樹或圖的算法。 沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。

7、紅黑樹

示例：linux中進程的調(diào)度用的是紅黑樹。

8、C4.5算法（基于信息增益率實現(xiàn)的決策樹算法）、CART算法（基于基尼指數(shù)實現(xiàn)的決策樹算法）

延伸閱讀：

二、樹的種類

無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系，這種樹稱為有序樹；

二叉樹：每個節(jié)點非常多含有兩個子樹的樹稱為二叉樹；

完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節(jié)點都在最底層的完全二叉樹;

平衡二叉樹（AVL樹）：當(dāng)且僅當(dāng)任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹；

排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）；

霍夫曼樹（用于信息編碼）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或優(yōu)異二叉樹；

B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個子樹。