从嵌套元组中提取数据

Question

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

，以供参考元组代表霍夫曼树，一个例子是：

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

这是从霍夫曼程序创建如下概率：

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')] 

这是不太我想要的。

我怎么能修改我的代码来产生我想要的输出？

EDIT

我已经产生一些代码，给定的一个平衡的输入：

('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) 

Answer 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列表转换为树来测试它们，但它可以处理第一个问题。

Answer 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']] 

一个包含两个列表从两侧较低的树枝树叶列表。

编辑：

这个代码是根据在原来的问题给出的格式：）0.125

树=（1.0，（0.5，（0.25，（0.125， 'd'，（ ，'c'）），（0.25，'b'）），（0.5，'a'））

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

Answer 3

看起来像是一个通用算法，您需要一个函数（1）计算下面的树的总权重，然后（2）实现树的旋转来旋转树，直到达到平衡。即在某些方面，这仅仅是标准树平衡算法的变体，除了例如对于AVL树来说，您正在平衡深度，并且在这里您正在权衡数据本身。