首先我們來看一個偽代碼。這個是代表成績的等級。

然后我們知道，每一次高考，學生的成績分布應該接近某個比例，現在我們假如分別規律如下：

為此可以作出下面的這個樹。

我們發現，概率分布主要是在70-79,80-89之間，如果有很多數據要比較，那么就要從60分開始比較，然后，分布最多的確是70-79,80-89的人，所以我們可以把樹話成這樣

現在先介紹幾個概念：

路徑長度：從樹中一個結點到另一個結點之間的分支構成這兩個結點的路徑，路徑上的分支數目叫路徑長度。

樹的路徑長度：根結點到每個結點的路徑長度和。

WPL(weight path length):樹中所有葉子結點的帶權路徑之和。

比如上面那兩個圖，我們把他權重標號。如下圖所示（為了方便，我們擴大10倍，避免小數點）

現在來看看WPL

WPL1=5*3+15*3+40*2+30*2+10*2=220

WPL2=5*1+15*+40*3+30*4+10*4=315。

現在給出一個概念：帶權路徑長度WPL最小的二叉樹叫最優二叉樹或赫夫曼樹。

下面給出最優二叉樹或赫夫曼樹的畫法。

規則如下：

1.在森林中選出兩顆根結點的權值最小的二叉樹。

2.合并兩顆，增加一個新結點作為新二叉樹的根，全職為左右孩子的權重之和。

3.再從未選中的結點中選擇，小的放左邊，大的放右邊，然后重復，一直到結點沒有了為止。

如下圖所示：

總結

以上是生活随笔為你收集整理的6.6.1最优二叉树(赫夫曼树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。