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