1

我需要通过检查节点的分支总和是否大于零来搜索树。但是，我遇到了求和的问题 - 我在

branch_sum = [t[0] for t in current]

线。我以为是因为最终我会得到一个节点

current = [[1,'b']]

（例如），所以我添加了 if/else 语句。即我认为我试图总结一些看起来像这样的东西：

first = [1]

但是，问题仍然存在。我不确定是什么原因造成的。

作为参考，current 是一个列表列表，第一个槽是节点数据，第二个槽是节点 ID（在内部列表中）。group() 函数根据子节点的 id 对节点上的数据进行分组（左侧子节点的 id 以 1 开头，右侧的 id 以 0 开头）。

我正在搜索的树存储为列表列表，例如：

tree = [[0, '1'], [1,'01'], [0,'001']]

即它是一组霍夫曼代码。

from collections import deque 

def group(items):
    right = [[item[0],item[1][1:]] for item in items if item[1].startswith('1')]
    left  = [[item[0],item[1][1:]] for item in items if item[1].startswith('0')]

    return left, right

def search(node):
    loops = 0
    to_crawl = deque(group(node))
    while to_crawl:
        current = to_crawl.popleft() # this is the left branch of the tree
        branch_sum = 0
        if len(current)==1:
            branch_sum = sum([t for t in current])
        else: 
            branch_sum = sum([t[0] for t in current])
        if branch_sum !=0 :
            l,r = group(current)
            to_crawl.extendleft(r)
            to_crawl.extendleft(l)
        loops += 1
    return loops

这是我正在尝试做的事情：

给定一棵树，其中很多数据为 0，找到 1。为此，将树分成两个分支（通过 group() 函数）并推送到双端队列。从双端队列中弹出一个分支，然后对分支中的数据求和。如果总和不为零，则将分支拆分为两个子分支，将子分支推送到双端队列。继续这样做，直到我找到非零数据。当我退出时，我应该在双端队列中得到一个 [1,'101'] 形式的项目。

4

1 回答 1

3

我强烈认为错误说

TypeError: 'int' object is not iterable

因为你最终传递了一个 2 元node组

to_crawl = deque(group(node))

这为您提供了一个 2 元素双端队列。然后

current = to_crawl.popleft()

给你一个单一的元素（一个整数）作为current. 这显然是不可迭代的，这会导致给定的错误。

旁注：为简洁起见，您可以像这样使用 sum

sum(current)

代替

sum([x for x in current])
于 2013-10-16T11:35:12.983 回答