0

对于我正在编写的应用程序，我需要测试霍夫曼树的分支以获得特定的属性。为此，我考虑过查询一个节点，并返回一个平面列表，其中包含代表每个分支中项目的子列表。

例如，如果我有这棵树：

-a
|-b
|-c
|-d

我想通过查询最上面的项目（'a'）来创建一个列表并返回以下列表：

[[a],[b,c,d]]

如果我查询第二片叶子（'b'），我想返回：

[[b].[c,d]]

ETC

到目前为止，我将我的树存储为一个元组，如下所示：

(1.0,(0.5,(0.25, (0.125,'d'),(0.125,'c')),(0.25,'b')),(0.5,'a'))

我有一个在叶子上打印信息的功能：

def printTree(tree, prefix = ''):
    if len(tree) == 2:
        print tree[1], prefix
    else:
        printTree(tree[1], prefix + '0')
        printTree(tree[2], prefix + '1')

我尝试创建一个函数，用 list() 语句替换 print 语句，但这不起作用。

有人对我该如何解决这个问题有任何想法吗？

4

1 回答 1

0

所以你正在寻找类似的东西：

def printTree(tree, prefix = '', res=[]):
    if len(tree) == 2:
        res.append((tree[1], prefix))
        print tree[1], prefix
    else:
        printTree(tree[1], prefix + '0', res=res)
        printTree(tree[2], prefix + '1', res=res)
    return res

res将在递归中保留您的结果，最后它会返回。

有了你的树，这将返回：[('d', '000'), ('c', '001'), ('b', '01'), ('a', '1')] ，那是你想要的吗？

于 2013-09-20T07:58:02.900 回答