2

二分探索木ではなく二分木で最小値を返す関数を書こうとしています。ここに私が書いたものがありますが、それは正しくありません。

def min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t

    if root.key < min_t:
            min_t = root.key

    min(root.left, min_t)
    min(root.right, min_t)

    return min_t

私は再帰をよく理解していないように感じます。再帰呼び出しで return ステートメントをいつ使用するか、いつ使用しないかを理解できないようです。

あなたの洞察に感謝します！

これは私が思いついた別のものです。動作しますが、最も効率的ではないようです:

n = []
def min_tree(root, n):
    if root:
        n += [(root.key)]
        min_tree(root.left, n)
        min_tree(root.right, n)
    return min(n)

考え？

4

4 に答える 4

4

マイケルの答えは、おそらくあなたが問題に取り組むことになっていた方法を説明していますが、彼はあなたの現在の試みの何が悪いのかを説明していませんでした。私が理解しているように、あなたの戦略は、各ノードを調べ、再帰を使用してすべてのノードを見つけることで、進行中の最小値を追跡することでした。すべてのノードを調べたら、結果がツリー全体の最小値であることがわかります。これは完全に有効なアプローチであり、引数が期待どおりに機能しないことを除いては機能します。

Pythonは、参照ではなく値で引数を渡します。「min_t=root.key」を使用してmin_tに値を割り当てると、関数内でのみ有効になります。関数の呼び出し元には、新しい値は表示されません。

これは、いくつかの簡単なコードでテストできます。

def add_one_to(x):
    x = x + 1
    print "add_one_to", x

x = 2
add_one_to(x)
print x

コードを実行すると、xが関数内でインクリメントされたが、トップレベルではインクリメントされなかったことがわかります。

これは、関数がそれ自体を呼び出すときにも当てはまります。各呼び出しには独自のローカル変数のセットがあり、関数内でローカル変数に割り当てても、それを呼び出したインスタンスには影響しません。

一部の言語では、参照によって引数を渡すことができることに注意してください。参照によって引数を渡す場合、関数内でその引数を割り当てると、呼び出し元にも影響します。Pythonがそれらの言語の1つである場合、min_tを参照引数にすることができ、関数は正しく機能します。

Pythonは参照引数を直接サポートしていませんが、参照引数は、呼び出されたときに関数に入り、関数が完了したときに呼び出し元に返される値と考えることもできます。これらの両方を別々に行うことができます。値を呼び出し元に戻すには、その値を返します。その後、呼び出し元はその関数をローカルに割り当てることができ、基本的に参照によって引数を渡しました。

上記の例にそれを適用する方法は次のとおりです。

def add_one_to(x):
    x = x + 1
    print "add_one_to", x
    return x

x = 2
x = add_one_to(x)
print x

戻り値と割り当てを追加するだけで、正常に機能します。

これを元の関数に適用することもできます。

def min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t

    if root.key < min_t:
            min_t = root.key

    min_t = min(root.left, min_t)
    min_t = min(root.right, min_t)

    return min_t

私がしたのは、min（）を呼び出すたびに「min_t =」を追加し、returnステートメントを変更して最後にmin_tを返すことだけでした。（とにかくmin_tを返すつもりだったと思います。minは関数の名前なので、あまり意味がありません。）バージョンは機能すると思います。

編集：これにもかかわらず、min_tree関数が機能する理由は、nがリストであり、リストが可変オブジェクトであるためです。上記の「値」について話していたとき、私が本当に意味したのは「オブジェクト」でした。Pythonの各変数名は、特定のオブジェクトにマップされます。このようなコードがある場合：

def replace_list(x):
    x = [1, 2, 3]

x = [2]
replace_list(x)
print x

結果は[2]です。したがって、「x =」を使用してxに新しい値を割り当てると、呼び出し元にはその値が表示されません。ただし、これを行う場合：

def replace_list(x):
    x.append(1)

x = [2]
replace_list(x)
print x

結果は[2、1]です。これは、xの値を変更していないためです。xはまだ同じリストを指しています。ただし、そのリストには追加の値が含まれるようになりました。残念ながら、「+=」演算子はこの点で混乱しています。「x+=y」は「x=x + y」と同じだと思うかもしれませんが、Pythonでは常にそうであるとは限りません。「x」が「+=」を具体的にサポートする一種のオブジェクトである場合、その操作はその場でオブジェクトを変更します。それ以外の場合は、「x =x+1」と同じになります。リストは「+=」の処理方法を知っているため、リストで+ =を使用するとその場で変更されますが、数値で使用しても変更されません。

関数呼び出しを行わずに、これを実際にテストできます。

x = [1, 2]
y = x
y += [3]
print x # [1, 2, 3]
print y # [1, 2, 3]
print x is y # True, x and y are the same object, which was modified in place

x = [1, 2]
y = x
y = y + [3]
print x # [1, 2]
print y # [1, 2, 3]
print x is y # False, y is a new object equal to x + [3]

x = 1
y = x
y += 2
print x # 1
print y # 3
print x is y # False, y is a new object equal to x + 2
于 2012-04-21T01:05:06.200 に答える
1

この特定の問題では、ツリー全体をトラバースして、最小値を返します。しかし、一般に、再帰の基本原則は、関数をもう一度呼び出すと、同じ問題の修正版が表示されるということです。

あなたの木を考えてみましょう：

    root
   /    \
left   right

左のサブツリーで再帰関数を呼び出すと、再びツリーが表示されます。したがって、同じ種類のロジックを使用できるはずです。

再帰関数の鍵は、基本ケースと再帰ステップです。ツリーの例では、基本ケースは最小値を見つけたときではなく (どのように知ることができますか?)、むしろツリーの最下部 (リーフ) に到達したときです。

そして、あなたの再帰的なステップは、サブ問題 (bin_min(左) と bin_min(右)) のそれぞれを見ています。

最後の部分は、戻り値を考慮しています。不変条件は、関数が見た最小要素を返したことです。したがって、再帰呼び出しが戻ると、それが最小の要素であることがわかり、返す必要があるのは、3 つの可能な選択肢 (root、left_min、および right_min) の最小の要素です。

def min_bin(root):
    if not root:
        return MAX_VAL
    left_min = min_bin(root.left)
    right_min = min_bin(root.right)

    return min(left_min, right_min, root.val)

これは@Rik Poggiのソリューションとは異なることに注意してください。彼は末尾再帰を使用して少し最適化しています。

于 2012-04-21T00:49:45.250 に答える
1

既製のソリューションよりも、自分でこれを理解しようとする方がより多くのことを得ることができるため、ここにいくつかのヒントを示します。まず第一に、それを呼び出すべきではありません。もちろん、結果をテストするためにminpython を呼び出すことはできません。minそして、Michaelの答えが私に思い出させたように、代わりにテストできるので渡す必要はありませんが、問題を理解するために渡すことは役立つと思います。min_troot.keymin_t

それに加えて、あなたの最初の行はちょうどいいです。ここでよくやった。:

def tree_min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t
    if root.key < min_t:
            min_t = root.key

次に、何を返すかを考える必要があります。基本的に、可能な最小値は 3 つあります。1 つ目はmin_t. 2 番目はrightサブツリーの最小値です。そして 3 番目はleftサブツリーの最小値です。後者の 2 つの値を取得し (ここで再帰呼び出しが行われます)、最小値を返します。

于 2012-04-21T00:53:22.517 に答える