0

私が書いているアプリケーションでは、特定のプロパティについてハフマン ツリーのブランチをテストする必要があります。そのために、ノードをクエリして、各ブランチのアイテムを表すサブリストを含むフラット リストを返すことを考えました。

たとえば、このツリーがあるとします。

-a
|-b
|-c
|-d

一番上の項目 ('a') を照会してリストを作成し、次のリストを返したいと思います。

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

2 番目の葉 ('b') を照会した場合は、次のように返します。

[[b].[c,d]]

等

これまでのところ、次のようにツリーをタプルとして保存しています。

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

print ステートメントを list() ステートメントに置き換える関数を作成しようとしましたが、うまくいきませんでした。

どうすればこれを実行できるかについて、誰かアイデアがありますか?

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 に答える