4

ノード用のカスタムクラスを作成しました

class NodeTree(object):
    def __init__(self, name = None, children = None):
        self.name = name
        self.children = children

ツリー（子ノードを含むノード）を作成する関数を定義しました

def create_tree(d):
    x = NodeTree()
    for a in d.keys():
        if type(d[a]) == str:
            x.name = d[a]
        if type(d[a]) == list:
            if d[a] != []:
                for b in d[a]:
                    x.add_child(create_tree(b))
    return x

入力は、ノード名の 1 つの引数を持つ dict と、親と同じ形式の子を持つリストです。関数は正常に動作し、それを証明するメソッドを作成しましたが、それを正しくトラバースしてツリーの高さを取得する方法が見つかりません。「高さ」が正しい用語であるかどうかはわかりません。あいまいな可能性があることはわかっているため、次のようにノードを測​​定単位としてカウントする必要があります。

                                      parent
                                         |
                                         |
                                     ---------
                                     |       |
                                    child   child

このツリーの高さは 2 です。カウンターからクラスのタグまで、すべてを試しましたが、すべてが縮退しているようで、適切な高さが得られません。どのようにアプローチすればよいですか？

4

1 に答える 1

4

heightノードの高さ（つまり、そのノードから葉までのパス内のノードの最大数）を決定するツリーの再帰方法を作成するには：

def height(self):
    if not self.children:  # base case
        return 1
    else:                  # recursive case
        return 1 + max(child.height() for child in self.children)

他のツリー トラバーサルも再帰的に実行できます。たとえば、ツリー ノードの名前を「前の順序」で生成するジェネレータ メソッドを次に示します (つまり、各親がその子と子孫に先行します)。

def preorder(self):
    yield self.name
    for child in self.children:
        yield from child.preorder() # Python 3.3 only!

yield fromそのループの構文は、Python 3.3 で新しく追加されました。これにより、以前のバージョンで同じ結果を得ることができます。

        for descendent in child.preorder():
            yield descendent
于 2012-12-05T19:17:04.917 に答える