题解 | #【模板】哈夫曼编码#

#include #include #include using namespace std; long sum = 0; class MyNode { public: long val; long depth; class MyNode left; class MyNode right; public: MyNode(long val) { this->val = val; this->left = NULL; this->right = NULL; } MyNode operator=(long a) { MyNode pNewNode = new MyNode(a); return a; } bool operator()(MyNode a, MyNode b) { return a.val > b.val; } ~MyNode() { if (left != NULL) { //delete left; } if (right != NULL) { //delete right; } } }; class cmp { public: //重载 () 运算符 bool operator()(MyNode a, MyNode b) { return a->val > b->val; } }; MyNode createHFTRee(vector<MyNode*>& counts) {

priority_queue<MyNode*, vector<MyNode*>, cmp > queue(counts.begin(), counts.end());
while (!queue.empty()) {
	MyNode *left = queue.top();
	queue.pop();
	MyNode *right = queue.top();
	queue.pop();
	MyNode *par = new MyNode(left->val + right->val);
	par->left = left;
	par->right = right;
	if (queue.empty()) {
		return par;
	}
	else {
		queue.push(par);
	}
}
return NULL;

}

void getSum(MyNode* root) { vector<MyNode*> vec; queue<MyNode*> queue0; root->depth = 0; queue0.push(root); vec.push_back(root); MyNode* cur = new MyNode(0); while (!queue0.empty()) { cur = queue0.front(); queue0.pop(); //哈夫曼树中，一个结点要么无左无右，要么有左有右 if (cur->left != NULL && cur->right != NULL) { cur->left->depth = cur->depth + 1; cur->right->depth = cur->depth + 1; queue0.push(cur->left); queue0.push(cur->right); vec.push_back(cur->left); vec.push_back(cur->right); } else { sum += cur->val * cur->depth; } } for(auto it = vec.begin();it != vec.end();it++) { if(*it != NULL) { delete *it; *it = NULL; } } }

int main() { int n; cin >> n; vector<MyNode*> counts; for (int i = 0; i < n; i++) { long m; cin >> m; MyNode* node = new MyNode(m); counts.push_back(node); } MyNode *root = createHFTRee(counts); getSum(root); cout << sum;

for(auto it = counts.begin();it != counts.end();it++)
{
    if(*it != NULL)
    {
        //delete *it;
        *it = NULL;
    }
}
return 0;

}