程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Huffman tree(赫夫曼樹、霍夫曼樹、哈夫曼樹、最優二叉樹)

Huffman tree(赫夫曼樹、霍夫曼樹、哈夫曼樹、最優二叉樹)

編輯:關於C++

Huffman tree(赫夫曼樹、霍夫曼樹、哈夫曼樹、最優二叉樹)

flyfish 2015-8-1

Huffman tree因為翻譯不同所以有其他的名字 赫夫曼樹、霍夫曼樹、哈夫曼樹
定義引用自嚴蔚敏《數據結構》
路徑
從樹中一個結點到另一個結點之間的分支構成兩個結點之間的路徑.

路徑長度
路徑上的分支數目稱作路徑長度。

樹的路徑長度
樹的路徑長度就是從根節點到每一結點的路徑長度之和。

結點的帶權路徑長度
結點的帶權路徑長度就是從該結點到根節點之間的路徑長度與結點上權的乘積。

樹的帶權路徑長度
樹的帶權路徑長度就是樹中所有葉子結點的帶權路徑長度之和,通常記做WPL。

Huffman tree
假設有n個權值{w1,w2,…wn},構造一棵有n個葉子結點的二叉樹,每個葉子結點帶權wi,則其中帶權路徑長度WPL最小的二叉樹稱作Huffman tree 。

假設有一個字符串每個字符出現的次數如下
A:5
B:15
C:40
D:30
E:10
將字符按照出現次數從小到大排序形成一個有序序列
這裡寫圖片描述
自底向上建樹過程
第一步
這裡寫圖片描述

第二步
這裡寫圖片描述

第三步
這裡寫圖片描述

第四步
這裡寫圖片描述

構造完成<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+uMXE7rK5s+Q8L3N0cm9uZz48L3A+DQo8cD48aW1nIGFsdD0="這裡寫圖片描述" src="/uploadfile/Collfiles/20150802/20150802090847408.png" title="" />

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved