一、數(shù)據(jù)結(jié)構(gòu)與算法中，樹(shù)的應(yīng)用
1、xml，html等，那么編寫(xiě)這些東西的解析器的時(shí)候，不可避免用到樹(shù)，示例：
2、文件系統(tǒng)的目錄結(jié)構(gòu)
Linux操作系統(tǒng)就應(yīng)用了文件目錄樹(shù)，目錄樹(shù)的起點(diǎn)是根目錄，Linux文件系統(tǒng)中每一文件在此目錄樹(shù)中的文件名都是獨(dú)一無(wú)二的，因?yàn)槠浒瑥母夸涢_(kāi)始的完整路徑。
3、MySQL數(shù)據(jù)庫(kù)索引
MySQL數(shù)據(jù)庫(kù)生成索引的數(shù)據(jù)結(jié)構(gòu)，就是應(yīng)用了排序二叉樹(shù)也稱(chēng)為搜索二叉樹(shù)中的B+樹(shù)。
4、路由協(xié)議也是使用了樹(shù)的算法。
例如：STP生成樹(shù)協(xié)議，確保網(wǎng)絡(luò)中沒(méi)有環(huán)路；SPF優(yōu)異樹(shù)協(xié)議，不僅確保沒(méi)有環(huán)路，還保障網(wǎng)絡(luò)路徑優(yōu)異即：網(wǎng)絡(luò)路徑代價(jià)最小。
5、數(shù)據(jù)文件壓縮
典型代表：哈夫曼樹(shù)也稱(chēng)為優(yōu)異二叉樹(shù)。
應(yīng)用場(chǎng)景：哈夫曼樹(shù)的應(yīng)用很廣.
哈夫曼編碼就是其在電訊通信中的應(yīng)用之一,在電訊通信業(yè)務(wù)中，通常用二進(jìn)制編碼來(lái)表示字母或其他字符，并用這樣的編碼來(lái)表示字符序列。
廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法,其壓縮率通常在20%～90%之間。
6、深度優(yōu)先搜索算法（英語(yǔ)：Depth-First-Search，簡(jiǎn)稱(chēng)DFS）是一種用于遍歷或搜索樹(shù)或圖的算法。 沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。
7、紅黑樹(shù)
示例：linux中進(jìn)程的調(diào)度用的是紅黑樹(shù)。
8、C4.5算法（基于信息增益率實(shí)現(xiàn)的決策樹(shù)算法）、CART算法（基于基尼指數(shù)實(shí)現(xiàn)的決策樹(shù)算法）
延伸閱讀：
二、樹(shù)的種類(lèi)
無(wú)序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒(méi)有順序關(guān)系，這種樹(shù)稱(chēng)為無(wú)序樹(shù)，也稱(chēng)為自由樹(shù)；
有序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系，這種樹(shù)稱(chēng)為有序樹(shù)；
二叉樹(shù)：每個(gè)節(jié)點(diǎn)非常多含有兩個(gè)子樹(shù)的樹(shù)稱(chēng)為二叉樹(shù)；
完全二叉樹(shù)：對(duì)于一顆二叉樹(shù)，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹(shù)被稱(chēng)為完全二叉樹(shù)，其中滿二叉樹(shù)的定義是所有葉節(jié)點(diǎn)都在最底層的完全二叉樹(shù);
平衡二叉樹(shù)（AVL樹(shù)）：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹(shù)的高度差不大于1的二叉樹(shù)；
排序二叉樹(shù)（二叉查找樹(shù)（英語(yǔ)：Binary Search Tree），也稱(chēng)二叉搜索樹(shù)、有序二叉樹(shù)）；
霍夫曼樹(shù)（用于信息編碼）：帶權(quán)路徑最短的二叉樹(shù)稱(chēng)為哈夫曼樹(shù)或優(yōu)異二叉樹(shù)；
B樹(shù)：一種對(duì)讀寫(xiě)操作進(jìn)行優(yōu)化的自平衡的二叉查找樹(shù)，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹(shù)。
京公網(wǎng)安備 11010802030320號(hào)