霍夫曼樹(哈夫曼樹怎么畫)

樹與樹算法樹的概念

樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構，用來模擬具有樹狀結(jié)構性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成的一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個節(jié)點有零個或多個子節(jié)點；沒有父節(jié)點的節(jié)點稱為根節(jié)點；每一個非根節(jié)點有且只有一個父節(jié)點；除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹；

比如說：

tree.png

Treedatastructure.png

樹的術語節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；葉節(jié)點或終端節(jié)點：度為零的節(jié)點；父親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；樹的高度或深度：樹中節(jié)點的最大層次；堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟；節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。森林：由m（m>=0）棵互不相交的樹的集合稱為森林；樹的種類無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹；有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關系，這種樹稱為有序樹；二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹；完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節(jié)點都在最底層的完全二叉樹;平衡二叉樹（AVL樹）：當且僅當任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹；排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）；霍夫曼樹（用于信息編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數(shù)據(jù)有序，擁有多余兩個子樹。樹的存儲與表示

順序存儲：將數(shù)據(jù)結(jié)構存儲在固定的數(shù)組中，雖然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈式存儲。

樹的順序存儲.png

鏈式存儲：

樹的鏈式存儲.png

由于對節(jié)點的個數(shù)無法掌握，常見樹的存儲表示都轉(zhuǎn)換成二叉樹進行處理，子節(jié)點個數(shù)最多為2

常見的一些樹的應用場景

1.xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹2.路由協(xié)議就是使用了樹的算法3.mysql數(shù)據(jù)庫索引4.文件系統(tǒng)的目錄結(jié)構5.所以很多經(jīng)典的AI算法其實都是樹搜索，此外機器學習中的decision tree也是樹結(jié)構

網(wǎng)頁結(jié)構.jpg