好的。我现在需要你采用原址建立的方法利用所给的频度链表将频度链表中的结点作为哈夫曼树中的结点建立哈夫曼树。算法循环执行的每一次循环中从还没有指定双亲指针的结点中选择频度最小的元素和频度次小的两结点。创建其二者的双亲结点并设置二者的双亲指针指向该结点同时使双亲结点的左右孩指针指向两结点。之后将生成的双亲结点插入到频度链表中。循环执行至除根结点外的所有结点都具有双亲指针为止哈夫曼树建立成功。先序遍历哈

以下是修改后的代码：

#include #include #include #include using namespace std;

struct Node { char ch; int freq; Node* left; Node* right; Node* parent; Node(char c = '\0', int f = 0) : ch(c), freq(f), left(NULL), right(NULL), parent(NULL) {} };

bool cmp(const Node* a, const Node* b) { return a->freq < b->freq; }

void buildHuffmanTree(vector<Node*>& freqList) { while (freqList.size() > 1) { sort(freqList.begin(), freqList.end(), cmp); Node* leftNode = freqList[0]; Node* rightNode = freqList[1]; Node* parentNode = new Node('\0', leftNode->freq + rightNode->freq); parentNode->left = leftNode; parentNode->right = rightNode; leftNode->parent = parentNode; rightNode->parent = parentNode; freqList.erase(freqList.begin(), freqList.begin() + 2); freqList.push_back(parentNode); } }

void getHuffmanCode(Node* leafNode, string& code) { if (leafNode->parent) { if (leafNode == leafNode->parent->left) { code = "0" + code; } else { code = "1" + code; } getHuffmanCode(leafNode->parent, code); } }

int main() { int n; cin >> n; vector<Node*> freqList(n); for (int i = 0; i < n; i++) { char ch; int freq; cin >> ch >> freq; freqList[i] = new Node(ch, freq); } buildHuffmanTree(freqList); vector<Node*> leafList; for (int i = 0; i < n; i++) { Node* node = freqList[i]; if (!node->left && !node->right) { leafList.push_back(node); } } sort(leafList.begin(), leafList.end(), cmp); for (int i = 0; i < leafList.size(); i++) { string code; getHuffmanCode(leafList[i], code); cout << leafList[i]->ch << " " << code << endl; } int wpl = 0; for (int i = 0; i < n; i++) { Node* node = freqList[i]; wpl += node->freq * (node->parent ? code.size() : 0); } cout << wpl << endl; return 0;