通过需要1加注释2删除多余代码3检查内存泄漏4发布5梳理代码逻辑6理解哈夫曼编码

#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) { queue<MyNode*> queue0; root->depth = 0; queue0.push(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); } else { sum += cur->val * cur->depth; } } }

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 *node = new MyNode(1); counts.push_back(node); MyNode *node1 = new MyNode(2); counts.push_back(node1); MyNode node2 = new MyNode(3); counts.push_back(node2);/

MyNode *root = createHFTRee(counts);
//2.遍历每一个字符，确定其对应哈夫曼表
//assert root != null;
getSum(root);
//3.得到最终结果
//System.out.println(sum);
cout << sum;

return 0;

}