0

对于我正在处理的应用程序，我需要从嵌套元组创建列表，表示每个分支中包含的数据。

作为参考，元组代表一棵霍夫曼树，一个例子是：

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

这是从 Huffman 例程创建的，具有以下概率：

a:0.5, b:0.25, c:0.125, d:0.125

我想列出一个看起来像的列表

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

我试过以下代码：

def makeList(tree):
    if len(tree) == 2:
        return [tree[0]]
    else:
        rightlist = []
        leftlist = []
        right = list(tree[1])
        left = list(tree[2])
        for i in range(1, len(right)):
            rightlist.append(right[i])
        for i in range(1, len(left)):
            leftlist.append(left[i])
        return [rightlist, leftlist]

然而这会返回

[['a'],[(0.25, (0.125, 'd'),(0.125,'c')),(0.25,'b')]

这不是我想要的。

我该如何修改上面的代码以产生我想要的输出？

编辑

我制作了一些给出平衡输入的代码：

('a',0.25), ('b', 0.25), ('c', 0.25), ('d',0.25)

产生我想要的输出：

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

def makeList(tree):
if len(tree) == 2:
    print("I'm in here")
    return [tree[1]]
else:
    right = tree[1]
    left = tree[2]
    rightlist = []
    leftlist = []

    for i in range(0, len(right)):
        if type(right[i]) == tuple:
            print('right: ' + str(right[i]))
            rightlist.append(right[i][1])

    for i in range(0, len(left)):
        if type(left[i]) == tuple:
            print('left: ' + str(left[i]))
            leftlist.append(left[i][1])

    return [rightlist, leftlist]

但是，它在以下输入上失败（下面的输出）：

exampleData = [(0.5, 'a'), (0.5,'b')]

[[],[[]]

exampleData = [(0.5, 'a'), (0.25,'b'), (0.25,'c')]

[[],['b'.'c']]

exampleData = [(0.5,'a'), (0.25,'b'), (0.125,'c'), (0.125,'d')]

[[]],['b',(0.125, 'd')]]

然而，这需要通过的黄金标准测试是为随机树创建这些列表：

probs = np.random.dirichlet([1]*4).tolist()
indices = range(0,4)
exampleData = zip(probs, indices)
huffTree = makeHuffmanTree(exampleData)
groups = makeLists(groups)
4

3 回答 3

2

我有一个递归解决方案。

def makeListAndFlatten(tree):
    treeList = makeList(tree)
    branchA = treeList[0]
    branchB = treeList[1]
    flatA = flatten(branchA)
    flatB = flatten(branchB)
    return [flatA, flatB]

def makeList(tree):
    if len(tree) == 2:
        return tree[1]
    else:
        for i in range(1,len(tree)):
                return [tree[len(tree)-1][1], makeList(tree[i])]

def flatten(nestedList):
        def aux(listOrItem):
            if isinstance(listOrItem, list):
                for elem in listOrItem:
                    for item in aux(elem):
                        yield item
            else:
                yield listOrItem
        return list(aux(nestedList))

如果我们运行：

makeListAndFlatten(tree)

这给出了结果：

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

一个包含两个列表的列表，两侧都有来自较低分支的叶子。

编辑：

此代码基于原始问题中给出的格式：

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

如果输入格式被改变，那么这将不起作用。

于 2013-09-23T12:44:44.077 回答
1

假设你已经有了树，最多有两个分支：

import Queue

def leaves(tree):
    result = []
    queue = Queue.Queue()
    queue.put(tree)
    while not queue.empty():
        node = queue.get()
        if type(node[1]) == tuple:
            for subnode in node[1:]:
                queue.put(subnode)
        else:
            result.append(node[1])
    return result

def makeList(tree):
    if len(tree) == 2:
        return [tree[1]]

    left = tree[1]
    right = tree[2]
    return [leaves(left), leaves(right)]

这需要两个分支并抓住每个分支的叶子，丢弃每片叶子的前半部分。它使用广度优先搜索来避免递归问题。

我无法将exampleData列表转换为树来测试它们，但它适用于第一个问题。

于 2013-09-24T18:02:56.933 回答
0

似乎作为一种通用算法，您需要一个函数，它 (1) 计算下面树的总权重，然后 (2) 实现树旋转以旋转树，直到它平衡。也就是说，这在某些方面只是标准树平衡算法的一种变体，除了例如对于 AVL 树，您正在平衡深度，而在这里您正在平衡数据本身的权重。

于 2013-09-23T15:09:57.383 回答