algorithm - 如何在仅给定叶节点及其深度的情况下构造前缀树

Question

给定一个成对向量（符号：它的码字长度），为这些符号构造一个二叉霍夫曼树。如果这样的树不存在，则会出错。

例如，给定输入 { a : 1, b : 2, c: 2}，输出树应该是：

    *
   / \
  a   *
     / \
    b   c

Answer 1

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class TreeNode {
public:
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int v): left(nullptr), right(nullptr), val(v) {}
    TreeNode(): left(nullptr), right(nullptr), val('*') {}
};

TreeNode *
buildHuffman(const vector<pair<char, int>>& codeLenPairs)
{
    TreeNode* root=nullptr;
    queue<TreeNode*> q;
    int nInternalNode = codeLenPairs.size()-1;

    if(nInternalNode>0) {
        root = new TreeNode();
        q.push(root);
        nInternalNode--;
    }
  
    size_t index=0;
    int level = 1;
    while(!q.empty()) {
        int N= q.size();

        for(int i=0;i<N;++i)
        {
            TreeNode* curr = q.front();
            q.pop();

            if(index>=codeLenPairs.size())
                throw runtime_error("wrong input case 0");

            if( codeLenPairs[index].second == level) {
                curr->left = new TreeNode(codeLenPairs[index].first);
                index++;
            }
            else if ( codeLenPairs[index].second > level && nInternalNode>0) {
                curr->left = new TreeNode();
                q.push(curr->left);
                nInternalNode--;
            }
            else throw runtime_error("wrong input case 1");

            if(index>=codeLenPairs.size())
                throw runtime_error("wrong input case 2");

            if( codeLenPairs[index].second == level) {
                curr->right = new TreeNode(codeLenPairs[index].first);
                index++;
            }
            else if ( codeLenPairs[index].second > level && nInternalNode>0) {
                curr->right = new TreeNode();
                q.push(curr->right);
                nInternalNode--;

            }
            else throw runtime_error("wrong input case 3");

        }
        level++;
    }

    return root;

}

void printTree(TreeNode* root)
{
    if (!root) return;
    printTree(root->left);
    cout<<(char)root->val <<"; ";
    printTree(root->right);
}

int main(int argc, char *argv[])
{
     cout << "111 Hello World!" << endl;
    vector<pair<char, int>> codeLenPairs = {{'a',1}, {'b',2}, {'c',3}, {'d',3}};
    auto res = buildHuffman(codeLenPairs);
    printTree(res);
    cout << "Hello World!" << endl;
    return 0;
}