哈夫曼树和哈夫曼编码

Question

我正在使用 huffmans 算法在 python 中创建一个程序来压缩/解压缩文件。接近尾声时，我们有一个函数需要实现这个 improve_tree 方法，我们的目标是尽可能地改进树

出于某种原因，我在这里的实现没有成功，因为它没有通过下面的最后一个 doctest（试图执行后序遍历：

    def improve_tree(tree: HuffmanTree, freq_dict: dict[int, int]) -> None:
        """ Improve the tree <tree> as much as possible, without changing its shape,
        by swapping nodes. The improvements are with respect to the dictionary of
        symbol frequencies <freq_dict>.
    
        >>> left = HuffmanTree(None, HuffmanTree(99, None, None), \
        HuffmanTree(100, None, None))
        >>> right = HuffmanTree(None, HuffmanTree(101, None, None), \
        HuffmanTree(None, HuffmanTree(97, None, None), HuffmanTree(98, None, None)))
        >>> tree = HuffmanTree(None, left, right)
        >>> freq = {97: 26, 98: 23, 99: 20, 100: 16, 101: 15}
        >>> avg_length(tree, freq)
        2.49
        >>> improve_tree(tree, freq)
        >>> avg_length(tree, freq)
        2.31
        """
        # Repeat until no further improvements can be made
        def postorder(node: HuffmanTree) -> int:
            """ Post-order traversal of the Huffman tree """
            if node is None:
                return 0
            # Get the frequencies of the left and right subtrees
            left_freq = postorder(node.left)
            right_freq = postorder(node.right)
            node_freq = freq_dict.get(node.symbol, 0)
            # Swap the children if the left child has a higher frequency
            if left_freq > right_freq and node.right is not None:
                node.left, node.right = node.right, node.left
            return left_freq + right_freq + node_freq
    
        postorder(tree)  # Perform post-order traversal 

任何帮助将不胜感激，因为我的代码没有通过 avg_length doctest。 我尝试了多种实现，但这个错误似乎一直困扰着我，下面是失败的 doctest 错误：

Failed example:
    avg_length(tree, freq)
Expected:
    2.31
Got:
    2.49 ```