数据结构：haffman树

#include <iostream>
using namespace std;

struct haffNode
{
    int data;
    haffNode *left;
    haffNode *right;
    haffNode *parent;
    haffNode(int d = int()) :data(d), left(NULL), right(NULL), parent(NULL){}
    bool operator>(const haffNode &node)
    {
        //重载>,方便最小堆的生成。
        return data > node.data;
    }
};
template<int N,typename T>
class MixHash
{
public:
    MixHash()
    {
        *hashVal = new T[N];
        currentsize = 0;
    }
    ~MixHash()
    {
        if (*hashVal)
        delete[] *hashVal;
        //析构二维数组，二维数组里面的节点在haffman树里面析构释放。
    }
    void Insert(T *val)
    {
        hashVal[currentsize++] = val;
        int n = currentsize / 2;
        while ( n >= 0 )
        {
            adjust(hashVal,n);
            n--;
        }
    }
    void adjust(T *hashVal[],int n)//最小堆的再生成。
    {
        int i = n;
        int j = i * 2 + 1;
        while (j < currentsize)
        {
            if (j+1<currentsize && (*hashVal[j])>(*hashVal[j + 1]))
                j = j + 1;
            if ((*hashVal[i]) > (*hashVal[j]))
            {
                T *temp = hashVal[i];
                hashVal[i] = hashVal[j];
                hashVal[j] = temp;
            }
            i = j;
            j = i * 2 + 1;
        }
    }
    T *GetNode()
    {
        T *temp = hashVal[0];
        hashVal[0] = hashVal[--currentsize];
        adjust(hashVal,0);
        return temp;
    }
    bool IsOk()
    {
        return currentsize == 1;
    }
private:
    T *hashVal[N];
    //唉，开始搞的一维数组，传进去的节点是指针，节点指针赋值对象肯定要解引用，
    //然后相当与保存了N个对象，当我在交换时，有没有深拷贝，所以导致交换不彻底，
    //当我返回地址时，还是原来的地址，根本没有改变，于是我觉得用二维数组，就是
    //指针数组，让数组里面保存的是真实的节点指针，我可以直接操作这些指针作为树的
    //节点。
    int currentsize;
};

template<int N>
class haffTree
{
public:
    haffTree() :root(NULL){}
    void Insert(int a[],int n)
    {

        for (int i = 0; i < n; i++)
        {
            haffNode *s = new haffNode(a[i]);
            mh.Insert(s);
        }
    }
    ~haffTree()
    {
        DELETE(root);
    }
    void DELETE(haffNode *&t)
    {
        if (t == NULL)return;
        else
        {
            DELETE(t->left);
            DELETE(t->right);
            delete t;
            t = NULL;//赋空，防止野指针。
        }
    }
    void Create()//开始构造haffman树。
    {
        while (!mh.IsOk())//剩下最后一个节点了，就是最后的haffman树。
        {
            haffNode *node1 = mh.GetNode();

            haffNode *node2 = mh.GetNode();
            haffNode *newnode = new haffNode(node1->data + node2->data);
            newnode->right =node2;//开始连接构造。
            node2->parent = newnode;
            newnode->left = node1;
            node1->parent = newnode;
            mh.Insert(newnode);//插入最小堆，继续选择。
            root = newnode;
        }
    }
    void Printf()
    {
        Printf(root);
    }
private:
    void Printf(haffNode *t)
    {
        if (t == NULL)return;
        else
        {
            cout << t->data << " ";
            Printf(t->left);
            Printf(t->right);
        }
    }
private:
    haffNode *root;
    MixHash<N, haffNode> mh;//维护一个最小堆。
};

int main()
{
    int a[] = {1,2,3,4,5};
    haffTree<sizeof(a) / sizeof(int)> ht;
    ht.Insert(a, sizeof(a) / sizeof(int));
    ht.Create();
    ht.Printf();
}