数据结构 | 构造哈夫曼树

template<class T>
void Heap<T>::PercolateUp() //为了向上调整为堆，我们需要比较当前节点和其父节点的值，如果父节点的值比当前节点大，则交换它们的值。
{

    int p = size - 1, c = (p - 1) / 2;//`c`表示当前节点的父节点，`p`表示当前节点。
    T temp = vec[p];
    while (p > 0) //为什么不是c>0
        

        //在`while`循环中，我们判断当前节点是否已经到达根节点，如果是根节点则停止循环。所以条件应该是`p > 0`，而不是`c > 0`。

        
    {
        if (vec[c] <= temp)
            break;
        else
        {
            vec[p] = vec[c];
            p = c;
            c = (p - 1) / 2;
        }
    }
    vec[p] = temp; //写在while 里面还是外面？ 目前结点最后会空出来
}

 

---

template<class T>
void Heap<T>::PercolateDown(int h)// 向下调整为堆，如果父亲节点（目前结点）比孩子结点(较小值）大交换
{
    int p = h, c = 2 * p + 1;// c为p的左孩子
    T temp = vec[h]; //不定类型  不用写成int
    while (c < size)  //怎么修改？
    {
        if (c + 1 < size && vec[c + 1] < vec[c]) //左孩子的下标小于size-1（最后一个叶子结点）&&找到左右孩子的最小值

//c < size表示当前节点有左孩子，而c + 1 < size表示当前节点有右孩子。根据堆的性质，选择较小的孩子进行交换。

        {
            ++c;
        }
        if (temp <= vec[c])
            break;
        else
        {
            vec[p] = vec[c];
            p = c;
            c = 2 * p + 1;
        }
    }
    vec[p] = temp;
} 

#include<iostream>
#include<vector> 
#include<queue>
using namespace std;template<class T>
struct BTNode
{T data;BTNode* left, * right;BTNode(const T& item = T(), BTNode* lptr = NULL, BTNode* rptr = NULL) :data(item), left(lptr), right(rptr) {}
};void Gotoxy(int x, int y)
{static int level = 0, indent = 0;if (y == 0){indent = 0;level = 0;}if (level != y){cout << endl;indent = 0;level++;}cout.width(x - indent);indent = x;
}template<class T>
BTNode<T>* GetBTNode(const T& item, BTNode<T>* lp = NULL, BTNode<T>* rp = NULL)
{BTNode<T>* p;p = new BTNode<T>(item, lp, rp);if (p == NULL){cout << "error!" << endl;}return p;
}struct Location
{int xindent, ylevel;
};template<class T>
void PrintBTree(const BTNode<T>* t, int screenwidth)
{if (t == NULL){return;}int level = 0, offset = screenwidth / 2;Location floc, cloc;queue<const BTNode<T>*> Q;queue<Location> LQ;floc.xindent = offset;floc.ylevel = level;Q.push(t);LQ.push(floc);while (!Q.empty()){t = Q.front();floc = LQ.front();Q.pop();LQ.pop();Gotoxy(floc.xindent, floc.ylevel);cout << t->data;if (floc.ylevel != level){level++;offset = offset / 2;}if (t->left){Q.push(t->left);cloc.ylevel = floc.ylevel + 1;cloc.xindent = floc.xindent - offset / 2;LQ.push(cloc);}if (t->right){Q.push(t->right);cloc.ylevel = floc.ylevel + 1;cloc.xindent = floc.xindent + offset / 2;LQ.push(cloc);}}cout << endl;}template<class T>
class Heap   //小根堆 根->叶子 小到大
{vector<T> vec;int size;void BuildHeap(void);void PercolateUp();void PercolateDown(int h);
public:Heap(int max = 100) : vec(max), size(0) {}Heap(const vector<T>& vt);int Size(){return size;}void Insert(const T& item);void DeleteMin(void);void DeleteMin(T& item);
};template<class T>
void Heap<T>::PercolateUp() //为了向上调整为堆，我们需要比较当前节点和其父节点的值，如果父节点的值比当前节点大，则交换它们的值。
{int p = size - 1, c = (p - 1) / 2;//`c`表示当前节点的父节点，`p`表示当前节点。T temp = vec[p];while (p > 0) //为什么不是c>0//在`while`循环中，我们判断当前节点是否已经到达根节点，如果是根节点则停止循环。所以条件应该是`p > 0`，而不是`c > 0`。{if (vec[c] <= temp)break;else{vec[p] = vec[c];p = c;c = (p - 1) / 2;}}vec[p] = temp; //写在while 里面还是外面？ 目前结点最后会空出来
}template<class T>
void Heap<T>::PercolateDown(int h)// 向下调整为堆，如果父亲节点（目前结点）比孩子结点(较小值）大交换
{int p = h, c = 2 * p + 1;// c为p的左孩子T temp = vec[h];while (c < size)  //怎么修改？{if (c + 1 < size && vec[c + 1] < vec[c]) //左孩子的下标小于size-1（最后一个叶子结点）&&找到左右孩子的最小值{++c;}if (temp <= vec[c])break;else{vec[p] = vec[c];p = c;c = 2 * p + 1;}}vec[p] = temp;
}template<class T>
void Heap<T>::Insert(const T& item)
{if (size == vec.size()){vec.resize(vec.size() *2);}vec[size] = item;size++;PercolateUp();}template<class T>
void Heap<T>::BuildHeap(void) //从最后一个非叶子结点（a)开始，size-1是最后一个叶子结点,a是它的parent
{for (int i = size / 2 - 1; i >= 0; i--){PercolateDown(i);//为该结点的子树调整成堆}
}template<class T>
void Heap<T>::DeleteMin()
{if (size == 0){return;}vec[0] = vec[size - 1];size--;PercolateDown(0);
}template<class T>
void Heap<T>::DeleteMin(T& item)
{if (size == 0) //删除最小值需要判断堆是否为空{return;}item = vec[0];vec[0] = vec[size - 1];size--;PercolateDown(0);
}template<class T>
Heap<T>::Heap(const vector<T>& vt) : vec(vt.size() + 10), size(vt.size())
{for (int i = 0; i < size; i++){vec[i] = vt[i];}BuildHeap();
}template<class T>
struct HuffmanNode
{BTNode<T>* t;int operator<(const HuffmanNode& h)//穿入参数是哈夫曼节点 bool类型{return (t->data < h.t->data);}int operator<=(const HuffmanNode& h)//穿入参数是哈夫曼节点{return (t->data <= h.t->data);}
};template<class T>
BTNode<T>* MakeHuffman(T* pa, int n)
{BTNode<T>* t, * right, * left;HuffmanNode<T> hf;Heap<HuffmanNode<T>> HF(n);//第一个循环将数组里的元素插入到哈夫曼堆for (int i = 0; i < n; i++){t = GetBTNode<int>(pa[i]);hf.t = t;HF.Insert(hf);}//第二个循环找到最小的两个数，生成根节点后删除for (int i = 1; i < n; i++){HF.DeleteMin(hf);left = hf.t;HF.DeleteMin(hf);right = hf.t;t = GetBTNode(left->data + right->data, left, right);//t的左孩子是left,右孩子是righthf.t = t;HF.Insert(hf);}HF.DeleteMin(hf);//是一个对象调用函数t = hf.t;return t;
};int main()
{int a[] = { 7,5,2,4 };BTNode<int>* root;root = MakeHuffman(a, 4);PrintBTree(root, 40);cout << endl;return 0;
}