java基礎(chǔ)復(fù)習(xí)筆記09數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(已修改)
2025-06-19 13:45 本頁面
【正文】 Java基礎(chǔ)復(fù)習(xí)筆記09數(shù)據(jù)結(jié)構(gòu)哈夫曼樹劉巖Email:suhuanzheng7784877@1. 哈夫曼樹哈夫曼樹也稱作最優(yōu)二叉樹，當(dāng)樹中的節(jié)點(diǎn)帶了權(quán)重信息了，帶權(quán)路徑長度最小的二叉樹叫做最優(yōu)二叉樹。帶權(quán)路徑長度=sum（權(quán)重*度）。sum代表每個(gè)節(jié)點(diǎn)的之和。加入有如下帶權(quán)重的節(jié)點(diǎn)。權(quán)重分別是4。那么關(guān)于這些零散的節(jié)點(diǎn)，最優(yōu)二叉樹該如何構(gòu)建呢？首先先將離散節(jié)點(diǎn)從小到大升序排序第二從離散節(jié)點(diǎn)中在挑選排序前兩個(gè)節(jié)點(diǎn)當(dāng)做一個(gè)新的父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)第三從離散的節(jié)點(diǎn)中去除剛剛使用的兩個(gè)節(jié)點(diǎn)第四重復(fù)第二和第三步驟，直到所有離散節(jié)點(diǎn)剔除完畢。哈夫曼樹就構(gòu)建完成用圖形演示過程如下可以看出所有的葉子節(jié)點(diǎn)就是之前的離散節(jié)點(diǎn)，如果在采用廣度遍歷法遍歷此樹。那么遍歷的過程實(shí)際上就是最短遍歷路徑的遍歷過程2. 哈夫曼樹的使用場景其實(shí)哈夫曼樹使用場景還真不少，例如apache負(fù)載均衡的按權(quán)重請(qǐng)求策略的底層算法、咱們生活中的路由器的路由算法、利用哈夫曼樹實(shí)現(xiàn)漢字點(diǎn)陣字形的壓縮存儲(chǔ)()、快速檢索信息等等底層優(yōu)化算法，其實(shí)核心就是因?yàn)槟繕?biāo)帶有權(quán)重、長度遠(yuǎn)近這類信息才能構(gòu)建哈夫曼樹模型。3. 實(shí)現(xiàn)哈夫曼樹要想實(shí)現(xiàn)哈夫曼樹其實(shí)就是將一堆零散的節(jié)點(diǎn)信息構(gòu)建成一顆最優(yōu)二叉樹，之后再按廣度優(yōu)先遍歷它。實(shí)現(xiàn)哈夫曼樹其實(shí)就是構(gòu)建哈夫曼樹的過程，原理其實(shí)上面已經(jīng)說了，
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1