构建霍夫曼树：无需优先队列的巧妙算法

# 定义霍夫曼树节点结构
class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char  # 字符，叶子节点有值，内部节点为None
        self.freq = freq  # 频率
        self.left = left  # 左子节点
        self.right = right # 右子节点

    # 用于节点之间的比较，以便排序
    def __lt__(self, other):
        return self.freq < other.freq

    # 可选：用于打印节点信息
    def __repr__(self):
        return f"Node(char={self.char}, freq={self.freq})"

def build_huffman_tree_without_pq(frequencies):
    """
    使用双列表合并策略构建霍夫曼树。

    Args:
        frequencies (dict): 字典，键为字符，值为其频率。
                            示例: {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}

    Returns:
        HuffmanNode: 霍夫曼树的根节点。
    """
    if not frequencies:
        return None
    if len(frequencies) == 1:
        char, freq = list(frequencies.items())[0]
        return HuffmanNode(char=char, freq=freq)

    # list1 存储原始叶子节点，按频率升序排列
    list1 = []
    for char, freq in frequencies.items():
        list1.append(HuffmanNode(char=char, freq=freq))
    list1.sort() # 初始排序

    # list2 存储合并后的内部节点，也按频率升序排列
    list2 = []

    # 辅助函数：从 list1 和 list2 头部选择频率最小的节点
    def get_min_node(l1, l2):
        node1 = l1[0] if l1 else None
        node2 = l2[0] if l2 else None

        if node1 and node2:
            # 比较两个列表的头部，选择频率更小的
            if node1.freq < node2.freq:
                return l1.pop(0) # 移除并返回 list1 的第一个节点
            else:
                return l2.pop(0) # 移除并返回 list2 的第一个节点
        elif node1: # 只有 list1 有节点
            return l1.pop(0)
        elif node2: # 只有 list2 有节点
            return l2.pop(0)
        return None # 两个列表都为空

    # 当总节点数大于1时，持续合并
    while len(list1) + len(list2) > 1:
        # 选取第一个最小频率节点
        node1 = get_min_node(list1, list2)
        # 选取第二个最小频率节点
        node2 = get_min_node(list1, list2)

        # 合并这两个节点
        if node1 and node2:
            new_freq = node1.freq + node2.freq
            new_node = HuffmanNode(freq=new_freq, left=node1, right=node2)
            list2.append(new_node) # 将新节点添加到 list2 的末尾
        else:
            # 理论上不会发生，除非循环条件判断有误或输入异常
            break

    # 循环结束后，总会有一个根节点留在其中一个列表中
    if list1:
        return list1[0]
    elif list2:
        return list2[0]
    return None # 异常情况，不应发生

# 示例用法
if __name__ == "__main__":
    frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}

    # 构建霍夫曼树
    huffman_root = build_huffman_tree_without_pq(frequencies)

    # 打印霍夫曼树（简单遍历，用于验证）
    def print_huffman_codes(node, current_code="", codes={}):
        if node is None:
            return
        if node.char is not None: # 叶子节点
            codes[node.char] = current_code
        print_huffman_codes(node.left, current_code + "0", codes)
        print_huffman_codes(node.right, current_code + "1", codes)
        return codes

    if huffman_root:
        print("霍夫曼树构建成功！")
        huffman_codes = print_huffman_codes(huffman_root)
        print("霍夫曼编码:")
        for char, code in sorted(huffman_codes.items()):
            print(f"  '{char}': {code}")
    else:
        print("霍夫曼树构建失败。")