1

次の二分木を考えてみましょう: (ここから取得)

リーフ ノードが true または false のいずれかになる場合、すべてのリーフ ノードが true であるブランチ (複数可) を見つけるにはどうすればよいでしょうか?

したがって、8、5、6、または 7 のみが true の場合、最初の分岐は一致しません (一致するには 9 が true である必要があります) が、2 番目の分岐はすべてのリーフが true であるため一致します。

このタイプの検索でこの名前を特定するだけでも役立つので、Google で検索できます。

4

2 に答える 2

2

再帰関数を使用して、ツリーを深く掘り下げ、特定のブランチのすべての葉が true かどうかをボトムアップで判断できます。これらのブランチは、いくつかのリストに保存できます。

ここにいくつかの Python コードがあります。ツリーのルート ノードを最初のパラメータとして、空のリストを 2 番目のパラメータとしてこの関数を呼び出すと、リストに正しいブランチが取り込まれます。

def allTrue(node, trueList=[]):
    if isLeaf(node):
        return node.value == True
    else:
        leftTrue = allTrue(node.left, trueList)
        rightTrue = allTrue(node.right, trueList)
        bothTrue = leftTrue and rightTrue
        if bothTrue:
            trueList.append(node)
        return bothTrue

注意すべきことの 1 つ: 多くのプログラミング言語は、既に falsex and yである場合、 の 2 番目の引数を評価しないことによって、賢く、または怠惰になろうとします。xただし、この場合、左の分岐がすべて true でない場合、右の分岐にアクセスせず、すべて true の分岐をいくつか見逃してしまいます。したがって、再帰呼び出しは別の行に移動する方がよいでしょう。

于 2013-02-05T14:07:18.170 に答える
0

ポストオーダー ツリー トラバーサルを作成し、両方の子がサブツリーのすべてのリーフを true に、それ以外の場合は false を持っている場合は、各非リーフ ノード x を true にマークできます (これは、子のラベルの AND 演算です)。このようにして、ツリー全体を目的のプロパティで再帰的にマークします。

于 2013-02-05T14:08:07.510 に答える