A22036. 下⾯代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。struct Symbol { char ch; // 字符 long long freq; // 频率 string code; // 编码 }; struct Node { long long w; // 权值 Node* l, *r; // 左右孩子（节点下标） int sym; // 叶子对应符号下标，内部节点为 -1 Node(l…

下⾯代码实现了哈夫曼编码，则横线处应填写的代码是（    ）。

struct Symbol {
    char ch;          // 字符
    long long freq;   // 频率
    string code;      // 编码
};

struct Node {
    long long w;      // 权值
    Node* l, *r;      // 左右孩子（节点下标）
    int sym;          // 叶子对应符号下标，内部节点为 -1
    Node(long long _w, Node* _l, Node* _r, int _sym)
         : w(_w), l(_l), r(_r), sym(_sym) {}
};

// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node>& nodes, int n, int* pA,
                      const vector<int>& leafIdx, int* pB,
                      const vector<int>& internalIdx) {
    if (pA < n && (pB >= (int)internalIdx.size() ||
                   nodes[leafIdx[*pA]].w <= nodes[internalIdx[*pB]].w)) {
        return leafIdx[pA++];
    } else {
        return internalIdx[pB++];
    }
}


// DFS 生成编码(左 0, 右 1)
static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {
    if (u == -1) return;
    
    if (nodes[u].sym!= -1) {        // 叶子
        sym[nodes[u].sym].code = path;
        return;
    }
    path.push_back('0');
    DFSBuildCodes(nodes[u].l, nodes, sym, path);
    path.pop_back();
    
    path.push_back('1');
    DFSBuildCodes(nodes[u].r, nodes, sym, path);
    path.pop_back();
}

int BuildHuffmanCodes(Symbol sym[], int n) {
    for (int i = 0; i < n; i++) sym[i].code.clear();
    if (n <= 0) return -1;
    
    // 只有一个字符, 约定编码为 "0"
    if (n == 1) {
        sym[0].code = "0";
        return 0;
    }
  
    vector<Node> nodes;
    nodes.reserve(2 * n);
   
    // 1) 建立叶子节点
    vector<int> leafIdx(n);
    for (int i = 0; i < n; i++) {
        leafIdx[i] = (int)nodes.size();
        nodes.push_back(Node(sym[i].freq, -1, -1, i));
    }
}

    // 2) 叶子按权值排序 (A 队列)
sort(leafIdx.begin(), leafIdx.end(),
    [&](int a, int b) {
        if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;
        return nodes[a].sym < nodes[b].sym; // 稳定一下
    });

// B 队列(内部节点下标队列)
vector<int> internalIdx;
internalIdx.reserve(n);

int pA = 0, pB = 0;

// 3) 合并 n-1 次
for (int k = 1; k < n; k++) {
    int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
    int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);

    int z = (int)nodes.size();
    _________________// 在此处填写代码
}

int root = internalIdx.back();

// 4) DFS 生成编码
string path;
DFSBuildCodes(root, nodes, sym, path);

return root;
}