HuffmanTree

特点：

1. huffman树，又称最优二叉树，是加权路径长度最短的二叉树。

1. 【贪心算法】：是指在求解问题是，当前的选择总是看起来是最好的选择，不考虑整体，所以算法所达成的目的是当前最优解，而不是整体最优。

构建huffmanTree

1. 实现思路
   huffman树建立在堆的基础之上，在此之前必须先建好堆，我这里为建小堆，建好小堆之后，每次取到最小堆的两个最小的节点，将这两个最小节点的权值相加，当做parent节点，然后将parent入堆，在拿出最小的两个节点，new 出parent节点，依此步骤直到堆为空，这样构建出来的树则为huffmanTree，该树根节点的元素权值最大，因为拿元素出现的次数作为权值，所以出现次数最多的元素的huffman编码最短，依此原理对文件进行压缩，这里你肯定出现了一些疑问，不要紧，先掌握huffman树，后续有详细讲解。

2. huffman编码：
   从根节点开始，遍历这棵树直到到达该节点，所走的路径。从根节点开始，向左子树走，为0，向右子树为1，假设最后生成的编码为：101101；那么这个编码就是该节点所对应的huffman编码。如图：
   

3. huffman树的节点：
   template
   struct HuffmanTreeNode
   {

   HuffmanTreeNode<T>* _left;       //左孩子
   HuffmanTreeNode<T>* _right;      //右孩子
   HuffmanTreeNode<T>* _parent;     //指向父节点，方便解压回溯遍历
   T _weight;                       //权值
   
   HuffmanTreeNode(const T& weight)
       :_weight(weight)
       , _left(NULL)
       , _right(NULL)
       , _parent(NULL)
   {}
   

   };

代码实现

//仿函数
//权值weight比较,传给Heap让小堆的形成要按照权值的大小进行比较得出
template
struct NodeCompress
{
bool operator()(HuffmanTreeNode a, const HuffmanTreeNode b)
{
return a->_weight < b->_weight;
}
};
//构建哈弗曼树
template
//用class 编不过
struct HuffmanTree
{
typedef HuffmanTreeNode Node;

    HuffmanTree()
        :_root(NULL)
    {}

    ~HuffmanTree()
    {}

    //先序遍历
    void PrevHuffmanTree()
    {
        _PrevHuffmanTree(_root);
    }

public:
    //建造HuffmanTree
    //建大堆,由于以次数建树，所以权值大的，靠近堆顶，HuffmanCode短，
    Node* CreateTree(const T* a, size_t size, int illegal)
    {
        assert(a);

        MinHeap<Node*, NodeCompress<T>> minHeap;
        for (int i = 0; i < size; ++i)
        {
            if (a[i] != illegal)
            {
                Node* node = new Node(a[i]);
                minHeap.Push(node);
            }
        }

        //不能用empty判空
        while (minHeap.Size() > 1)
        {
            //拿出权值最小的两个数
            Node* left = minHeap.Top();
            minHeap.Pop();
            Node*  right= minHeap.Top();
            minHeap.Pop();

            //权值之和建根节点
            Node* parent = new Node(left->_weight + right->_weight);

            //链接
            parent->_left = left;
            parent->_right = right;
            left->_parent = parent;
            right->_parent = parent;

            _root = parent;

            //将根节点push进堆
            minHeap.Push(parent);
        }
        return _root;
    }
protected:
    void _PrevHuffmanTree(Node* root)
    {
        Node* cur = root;
        if (cur == NULL)
        {
            return;
        }
        cout << cur->_weight << " ";
        _PrevHuffmanTree(cur->_left);
        _PrevHuffmanTree(cur->_right);
    }
protected:
    Node* _root;
};

//测试哈夫曼树的正确性
void TestHuffmanTree()
{
    int array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    HuffmanTree<int> hf;
    hf.CreateTree(array, sizeof(array) / sizeof(int), -1);
    hf.PrevHuffmanTree();
    cout << endl;
}