文章目錄

• • • 前言
    • 哈夫曼樹(最優二叉樹)
    • • 定義與原理
      • • 樹的路徑長度
        • 帶權路徑長度
      • 構造哈夫曼樹
    • 哈夫曼樹生成代碼

前言

二叉樹是樹結構中的一種特殊形式，适用于折半查找、真假、對錯等具有兩種情況的事物進行模組化。

比如需要對學生考試得分評不及格、及格、中等、良好、優秀這幾個模糊分數的評級，我們可以很快用如下的代碼實作：

if score < 60:
    print("不及格")
elif score < 70:
    print("及格")
elif score < 80:
    print("中等")
elif score < 90:
    print("良好")
else:
    print("優秀")
           

我們用二叉樹可以表示如下：

我們上面模組化出來的二叉樹在查找判斷中效率是否是最優的呢？

我們結合現實場景進行思考，一場考試下來，發現分數占比如下：

分數	0~59	60~69	70~79	80~89	90~100
所占比例	5%	15%	40%	30%	10%

采用上面的二叉樹進行判斷70分以上的分數，有80%至少要進過3次以上的判斷才能得到結果。

那麼有沒有更好方式進行查找判斷呢？我們可以調整判斷順序，将占比多的70~79的判斷提前，然後再判斷80 ~ 89，這樣按照占比從大到小一次判斷。按照這種方式我們得到如下的二叉樹：

我們優化過後的二叉樹相比第一個二叉樹效率高了很多。

那麼如何建構一個最優二叉樹呢？這就是接下來要介紹的内容，哈夫曼樹。

哈夫曼樹(最優二叉樹)

哈夫曼樹就是我們平時說的最優二叉樹。

哈夫曼(David Huffman)是美國數學家，在1952年發明了哈夫曼編碼，而哈夫曼編碼就是基于哈夫曼樹得來的，本文隻介紹哈夫曼樹。

定義與原理

樹的路徑長度

從樹中一個節點到另一個節點之間的分支構成兩個節點之間的路徑，路徑上的分支數目稱為路徑長度。

樹a的根節點到D節點，路徑長度為4。樹b的根節點到節點D長度為2。樹的路徑長度為根節點到各節點的路徑長度之和。 樹a的樹路徑長度為1+1+2+2+3+3+4+4=20。樹b的樹路徑長度為1+2+3+3+2+1+2+2=16。

帶權路徑長度

樹的帶權路徑長度記為WPL(Weighted Path Length of Tree)

節點的帶權路徑長度為根節點到該節點路徑長度與該節點的權的乘積。樹的帶權路徑長度為各葉子節點的帶權路徑長度之和。

樹a的WPL=1x5+2x15+3x40+4x30+4x10=315

樹b的WPL=3x5+3x15+2x40+2x30+2x10=220

樹的WPL越小，那麼樹就越優。

構造哈夫曼樹

假定我們按照A5、B15、C40、D30、E10生成一棵哈夫曼樹。

按照如下步驟操作：

1. 将所有權重節點按照權重由小到大進行排序，即：A5,E10,B15,D30,C40
2. 将最左的兩個節點按照左小右大作為新節點N1的左右兩個子節點。N1的權重=5+10=15。

   

3. 将N1替換序列的A和E并加入。重複2步驟，将N1和B作為新節點N2的兩個子節點。N2的權重=15+15=30。

   

4. 然後繼續重複2步驟，将N2替換N1和B加入到序列中，并将N2與D作為新節點N3的兩個子節點。N3的權重=30+30=60。

   

5. 然後繼續重複2步驟，将N3替換N2和D并加入到序列。将N3和E作為新節點R的兩個子節點。因為N3的權重為60，C的權重為40，是以C作為R的左子節點，N3作為右子節點。并且R已經是根節點了，是以最終的哈夫曼樹就如下圖：

   

   該樹的WPL=1x40+2x30+3x15+4x10+4x5=205

   比前面的樹b的WPL=225還要少15，是以該樹就是最優的哈夫曼樹了。

我們對建立哈夫曼樹步驟總結如下：

1. 将給定的n個權值構成n棵隻有一個節點的樹，并根據權值由小到大進行排序。
2. 取最左遍權值最小的兩棵樹作為左右子樹構成一顆新二叉樹，新二叉樹的權值為兩棵字數的權值和。
3. 将2步驟構造的新樹的兩個子樹删除，将構造的新樹放入序列的最左邊。
4. 重複2、3步驟，直到所有樹合并為一棵樹為止。最終的樹就是哈夫曼樹，也就是最優二叉樹。

哈夫曼樹生成代碼

代碼用Python3實作如下：

import functools


class TreeNode:

    def __init__(self, data, weight) -> None:
        self.data = data  # 資料
        self.weight = weight  # type: int #權重
        self.left = None  # 左子節點
        self.right = None  # 右子節點

    def __str__(self) -> str:
        return self.data


def cmp(a, b):
    """
    排序
    """
    if a.weight > b.weight:
        return 1
    elif a.weight < b.weight:
        return -1
    else:
        return 0


def gen_huffman_tree(_trees, depth=0):
    """
    建構哈夫曼樹
    :param depth: 深度
    :param _trees: 樹集
    """
    if depth == 0:
        print('對' + ','.join([str(item) for item in tree]) + '樹集生成哈夫曼樹。資料|權重')
    depth = depth + 1  # 深度+1
    if len(_trees) == 1:
        return _trees[0]
    _trees = sorted(_trees, key=functools.cmp_to_key(cmp))
    left_sub = _trees[0]
    right_sub = _trees[1]
    new_node_weight = left_sub.weight + right_sub.weight  # 新樹權重
    # 建構新樹
    new_node = TreeNode('N%s|%s' % (str(depth), str(new_node_weight)), new_node_weight)
    new_node.left = left_sub
    new_node.right = right_sub
    # 删除最左兩個樹
    _trees.remove(left_sub)
    _trees.remove(right_sub)
    # 新樹插入到最左序列
    _trees.insert(0, new_node)
    # 遞歸建構下一個樹，直到隻剩下一棵樹
    return gen_huffman_tree(_trees, depth)


def layer_order_traverse(_layer_nodes):
    """
    按層周遊
    :param _layer_nodes: 目前層節點集合
    :type _layer_nodes: list
    """
    if _layer_nodes is None or len(_layer_nodes) == 0:
        return
    _childs = []  # 子集
    for _node in _layer_nodes:  # 周遊傳入的目前層所有節點
        print(_node.data, end=',')
        if _node.left:
            _childs.append(_node.left)
        if _node.right:
            _childs.append(_node.right)
    layer_order_traverse(_childs)


if __name__ == '__main__':
    tree = [
        TreeNode('A|5', 5),
        TreeNode('B|15', 15),
        TreeNode('C|40', 40),
        TreeNode('D|30', 30),
        TreeNode('E|10', 10)
    ]
    huffman_tree = gen_huffman_tree(tree)
    print('按層周遊哈夫曼樹：', end='')
    layer_order_traverse([huffman_tree])
    print('\b' * 1, end='')

           

該代碼将上面的例子A5、B15、C40、D30、E10樹集生成了如下最優二叉樹。

代碼允許後的結果如下：

對A|5,B|15,C|40,D|30,E|10樹集生成哈夫曼樹。資料|權重
按層周遊哈夫曼樹：N4|100,C|40,N3|60,N2|30,D|30,N1|15,B|15,A|5,E|10
           

生成了哈夫曼樹之後，按層周遊列印出了樹的每個節點，第一個N4為根節點，可以看出和上面的二叉樹的順序是一一對應的。

按層周遊算法可以看下二叉樹周遊算法。