12

Python で関数を作成しようとしています。これは、ツリーの任意のノードを取得し、ノードに基づいてリストのリストを作成します。

次の不適切に描画されたツリーがあるとします。

木

たとえば、ノード 5 から開始すると、次のようになります。

  • 開始したノード (4 と 5) を含む、同じ親ノードを持つすべてのノードを含むリスト
  • 子ノードはありますが、その子ノードは含まれません (6)。
  • 親ノードと同じ親を持つすべての親ノード、およびそれらの親のノードなど、ルート ノードに到達するまで、ただしルート ノードは含まれません (この場合は 2 と 3 だけですが、ツリーがより深く、開始した場合)低く、ここにもっとあるでしょう。

ノードは、深さごとに 1 つのリストのリストのリストになるはずです。

Python のノード:

nodes = [
    {'id': 1, 'parent': None},
    {'id': 2, 'parent': 1},
    {'id': 3, 'parent': 1},
    {'id': 4, 'parent': 2},
    {'id': 5, 'parent': 2},
    {'id': 6, 'parent': 5},
    {'id': 7, 'parent': 6},
    {'id': 8, 'parent': 3}
]

私たちが見ることができるのは親だけで、子供は見えませんが、悲しいことに、これは私が扱わなければならないデータ形式です。

このことから、ノード 5 を取得すると、最終的に次のようなノード リストになります。

nl = [
    [{'id': 6, 'parent': 5}],
    [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}],
    [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}],
]

これは私がこれまでに持っているコードです。再帰関数がおそらく最も簡単な方法だと思います。残念ながら、私がそうあるべきだと思うようなことは何もしていないようで、明らかに私は何か非常に間違ったことをしています。そして、このコードは、処理方法がまったくわからない子ノードを取得することさえ考慮していません。後で処理する方がはるかに簡単です。

node_list = []

def pop_list(nodes=None, parent=None, node_list=None):
    if parent is None:
        return node_list
    node_list.append([])
    for node in nodes:
        if node['parent'] == parent:
            node_list[-1].append(node)
        if node['id'] == parent:
            parent = node['parent']
    return pop_list(nodes, parent, node_list)

print pop_list(nodes, 5, node_list)

出力は次のとおりです。

[[], [{'id': 3, 'parent': 1}], []]

ここでどこが間違っているのか正確にはわかりません。

4

2 に答える 2

6

問題はここにあります

    if node['id'] == parent:
        parent = node['parent']

現在parentはその親によって上書きされます。

return node_listまた、関数の最後に追加するかnode_list、結果として使用する必要があります。

def pop_list(nodes=None, parent=None, node_list=None):
    if parent is None:
        return node_list
    node_list.append([])
    for node in nodes:
        if node['parent'] == parent:
            node_list[-1].append(node)
        if node['id'] == parent:
            next_parent = node['parent']

    pop_list(nodes, next_parent, node_list)
    return node_list

>>> print pop_list(nodes, 5, node_list)
[[{'id': 6, 'parent': 5}], [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}], [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}]]
于 2013-03-20T14:16:30.373 に答える