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