ノードからのブランチの合計がゼロより大きいかどうかを確認して、ツリーを検索する必要があります。ただし、合計で問題が発生しています。
branch_sum = [t[0] for t in current]
ライン。最終的には単一のノードを取得するためだと思いました
current = [[1,'b']]
(たとえば)、if/else ステートメントを追加しました。つまり、次のようなものを合計しようとしていると思いました。
first = [1]
ただし、問題は解決しません。何が原因なのかわかりません。
参考までに、current はリストのリストで、最初のスロットはノード データで、2 番目のスロットはノード 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() 関数を使用して) ツリーを 2 つのブランチに分割し、deque にプッシュします。両端キューからブランチをポップし、ブランチ内のデータを合計します。合計がゼロでない場合は、ブランチを 2 つのサブブランチに分割し、サブブランチを両端キューにプッシュします。ゼロ以外のデータが見つかるまで、これを続けてください。終了すると、両端キューに [1,'101'] という形式の 1 つの項目が残るはずです。