# 实现霍夫曼树的基本操作

什么是哈夫曼树呢？

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明。

![](https://img-blog.csdn.net/20171108134143639?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveHVlYmE4/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center)

它们的带权路径长度分别为：

图a： WPL=5*2+7*2+2*2+13*2=54

图b： WPL=5*3+2*3+7*2+13*1=48

可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

```python
class TreeNode(object):
    def __init__(self,data):
        self.val=data[0]
        self.priority=data[1]
        self.lefChild=None
        self.rightChild=None
        self.code=''

def createnodeQ(codes):

    # 创建树节点队列
    q=[]
    for code in codes:
        q.append(TreeNode(code))
    return q

def addQ(queue,nodeNew):
    # 给队列添加元素
    if len(queue)==0:
        return [nodeNew]
    for i in range(len(queue)):
        if queue[i].priority>=nodeNew.priority:
            return queue[:i]+[nodeNew]+queue[i:]
    return queue+[nodeNew]

class nodeQueue(object):
    def __init__(self,code):
        self.que=createnodeQ(code)
        self.size=len(self.que)

    def addNode(self,node):
        self.que=addQ(self.que,node)
        self.size+=1

    def popNode(self):
        self.size-=1
        return self.que.pop(0)
    # 计算字符串中字符出现次数，作为优先级
def freChar(string):
    d={}
    for c in string:
        if not c in d:
            d[c]=1
        else:
            d[c]+=1

    return sorted(d.items(),key=lambda x:x[1])  #item:(key,value)

def createHuffmanTree(nodeQ):
    #nodeQ isinstance nodeQueue
    while nodeQ.size!=1:
        node1=nodeQ.popNode()
        node2=nodeQ.popNode()
        # 暂时只有优先级，没有val
        r=TreeNode([None,node1.priority+node2.priority])
        r.lefChild=node1
        r.rightChild=node2
        nodeQ.addNode(r)
    return nodeQ.popNode()

codeDic1={}
codeDic2={}

# 霍夫曼树，到霍夫曼编码。（对当前节点node，编码为x）
def HuffmanCodeDic(node,x):
    global codeDic1,codeDic2
    if node:#如果这个节点不为空
        # 对当前节点node，编码为x
        node.code=x

        # 如果此点有内容（因为可能是最后叶子节点的空左右节点），记录此处编码对应的值&此处值对应的编码
        if node.val:
            codeDic2[node.code]=node.val
            codeDic1[node.val]=node.code

        #编码节点左边的，编码内容为当前编码+0
        HuffmanCodeDic(node.lefChild,x+'0')

        #编码节点右边的，编码内容为当前编码+1
        HuffmanCodeDic(node.rightChild,x+'1')


def TransEncode(string):#编码
    global codeDic1 #此字典根据字母，取得字母对应的编码
    transcode=''
    for c in  string:
        transcode+=codeDic1[c]
    return transcode

def TransDecode(stringCode):#解码
    global codeDic2 #此字典根据编码，取得编码对应的字母
    code=''
    ans=''
    for ch in stringCode:
        code+=ch
        if code in codeDic2:
            ans+=codeDic2[code]
            code=''
    return ans


string='AAGGDCCCDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA'
fre_dict=freChar(string)
print(fre_dict)

t=nodeQueue(fre_dict)
# 创建了霍夫曼树，根据字符串字母频率
tree=createHuffmanTree(t)

#对霍夫曼树进行编码，得到节点编码
HuffmanCodeDic(tree,'')
print(codeDic1,codeDic2)

# 进行编码
a=TransEncode(string)
print(a)

# 解码
aa=TransDecode(a)
print(aa)
print(string==aa)
```

```
[('E', 1), ('B', 3), ('A', 5), ('F', 6), ('C', 7), ('G', 9), ('D', 11)]
{'E': '0000', 'B': '0001', 'A': '001', 'G': '01', 'D': '10', 'F': '110', 'C': '111'} {'0000': 'E', '0001': 'B', '001': 'A', '01': 'G', '10': 'D', '110': 'F', '111': 'C'}
00100101011011111111110100111000010001000111011001011010101001010100001101101010111111111111101011001001001001
AAGGDCCCDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA
True
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/shu-ju-jie-gou-lei/huffman-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.