哈夫曼树

以你之姓@ 2022-06-16 14:11 161阅读 0赞

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

1、路径和路径长度  
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长  
哈夫曼树  
哈夫曼树(3张)  
度为L-1。  
2、结点的权及带权路径长度  
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。  
3、树的带权路径长度  
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

如何生成一个哈夫曼树  
用int arr\[\]=\{0,1,2,3,4,5,6,7,8,9\}生成一个哈夫曼树

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

![这里写图片描述][SouthEast 3]

……以此类推，每次选出未被使用的最小的两个数求和，并且将和在放进去，并且将使用过的数字拿出来。

![这里写图片描述][SouthEast 4]

如何用代码来实现构建一颗哈夫曼树，需要借助堆排序  
因为每次要取出最小的两个数

#include"Heap.h"
    template<class T> struct HuffmanTreeNode { 
        HuffmanTreeNode<T>*left;
        HuffmanTreeNode<T>*right;
        HuffmanTreeNode<T>*parent;
        T _w;//权值
        HuffmanTreeNode(const T&w)
            :left(NULL)
            , right(NULL)
            , parent(NULL)
            , _w(w)
        {
    
        }
    };
    template<class T> class HuffmanTree { 
        typedef HuffmanTreeNode<T> Node;
    public:
        HuffmanTree()
            :root(NULL)
        {
    
        }
        HuffmanTree(T*arr, size_t n, const T&invalid)
        {
            struct NodeCompare
            {
                bool operator()(const Node*left,const Node*right)
                {
                    return left->_w < right->_w;
                }
            };
                Heap<Node*, NodeCompare>minHeap;
                for (int i = 0; i < n; i++)
                {
                    if (arr[i] != invalid)
                    {
                        minHeap.Push(new Node(arr[i]));//建立一个存放节点指针的小堆
                    }
                }
                while (minHeap.Size()>1)//当其中只剩下一个数据的时候哈夫曼树已经建成
                {
                    Node*left = minHeap.Top();
                    minHeap.Pop();
                    Node*right = minHeap.Top();
                    minHeap.Pop();
                    Node*parent = new Node(left->_w + right->_w);
                    parent->left = left;
                    parent->right = right;
                    minHeap.Push(parent);
                }
                root = minHeap.Top();
            }
    protected:
        Node*root;
    };

#include"Huffman.h"
    void TestHuffmanTree()
    {
        int arr[] = { 2, 0,1,5,3,4,6,7,8,9,-1 };
        HuffmanTree<int>t1(arr, sizeof(arr) / sizeof(arr[0]), -1);
    }
    int main()
    {
        TestHuffmanTree();
        system("pause");
        return 0;
    }

[SouthEast]: /images/20220616/6001f5fb186d4dc6bd14a7f9c6f6e87c.png
[SouthEast 1]: /images/20220616/800625eab44f404ba4e866f524da983c.png
[SouthEast 2]: /images/20220616/cd3db26b90be4f3fbe78ec4a6e758acc.png
[SouthEast 3]: /images/20220616/b53f7f9e02734967b6e5273f18f66fec.png
[SouthEast 4]: /images/20220616/1099f03c58d44d899a5c5a3a1eb61e28.png