A22264. 下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。class Symbol: def __init__(self, ch='', freq=0, code=''): self.ch = ch self.freq = freq self.code = code class Node: def __init__(self, w=0, l=-1, r=-1, sym=-1): self.w = …

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

class Symbol:
    def __init__(self, ch='', freq=0, code=''):
        self.ch = ch
        self.freq = freq
        self.code = code

class Node:
    def __init__(self, w=0, l=-1, r=-1, sym=-1):
        self.w = w
        self.l = l
        self.r = r
        self.sym = sym

def pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB):
    if pA[0] < n and (pB[0] >= len(internal_idx) or nodes[leaf_idx[pA[0]]].w <= nodes[internal_idx[pB[0]]].w):
        res = leaf_idx[pA[0]]
        pA[0] += 1
        return res
    else:
        res = internal_idx[pB[0]]
        pB[0] += 1
        return res

def dfs_build_codes(u, nodes, sym_list, path):
    if u == -1:
        return
    if nodes[u].sym != -1:
        sym_list[nodes[u].sym].code = ''.join(path)
        return
    path.append('0')
    dfs_build_codes(nodes[u].l, nodes, sym_list, path)
    path.pop()
    path.append('1')
    dfs_build_codes(nodes[u].r, nodes, sym_list, path)
    path.pop()

def build_huffman_codes(sym_list):
    n = len(sym_list)
    for sym in sym_list:
        sym.code = ''
    if n <= 0:
        return -1
    if n == 1:
        sym_list[0].code = '0'
        return 0
    nodes = []
    leaf_idx = []
    for i in range(n):
        leaf_idx.append(len(nodes))
        nodes.append(Node(sym_list[i].freq, -1, -1, i))
    leaf_idx.sort(key=lambda x: (nodes[x].w, nodes[x].sym))
    internal_idx = []
    pA = [0]
    pB = [0]
    for k in range(1, n):
        x = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB)
        y = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB)
        z = len(nodes)
        nodes.append(Node(nodes[x].w + nodes[y].w, x, y, -1))
        internal_idx.append(z)
    root = internal_idx[-1] if internal_idx else -1
    path = []
    dfs_build_codes(root, nodes, sym_list, path)
    return root

if __name__ == "__main__":
    syms = [
        Symbol('A', 5),
        Symbol('B', 9),
        Symbol('C', 12),
        Symbol('D', 13),
        Symbol('E', 16),
        Symbol('F', 45),
    ]
    root = build_huffman_codes(syms)
    print(f"哈夫曼树根节点下标: {root}")
    for sym in syms:
        print(f"字符 {sym.ch} (频率 {sym.freq}): 编码 {sym.code}")