バイナリツリーの最小値を見つける、Python

Question

私はバイナリツリーの最小値を返す関数を書くつもりですではなく、バイナリ検索ツリーです。 これは私が書いたものですが、正しくありません。

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) 

思考？

Answer 1

この特定の問題については、ツリー全体を走査し、見られる最小値を戻したいとします。しかし、一般的には、再帰の基本原則は、関数を再度呼び出すと、同じ問題の修正版が表示されます。

あなたのツリーを考えてみましょう：

root 
/ \ 
left right 

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

再帰関数のキーは、基本ケースと再帰ステップです。あなたのツリーの例では、最小値を見つけたとき（基本的なケースは分かりません）ではなく、ツリーの最下部（別名葉）に達したときです。

そして、あなたの再帰的なステップは、それぞれの問題（bin_min（left）とbin_min（right））を調べています。

最後の部分は戻り値を考慮しています。 invariantは、あなたの関数が見た最小の要素を返したということです。したがって、あなたの再帰呼び出しが返ってくるとき、それは最小の要素であることがわかります。次に、返さなければならないものは、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'sとは異なる解決策です。彼はそれを少し最適化するためにテール再帰を使用します。

Answer 2

缶詰ソリューションよりも自分自身を理解しようとしていることから、多くのヒントがあります。まず、minと呼ぶべきではありません。もちろん、結果をテストするためにpythonのminを呼び出すことはできません。 Michaelさんの答えがわかったので、代わりにroot.keyをテストすることができるのでにはがありますが、min_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つあります。最初はmin_tです。 2番目はサブツリーrightの最小値です。 3番目はサブツリーleftの最小値です。後者の2つの値（これは再帰呼び出しが入る場所です）を取得し、最小の値を返します。

Answer 3

マイケルの答えは、あなたがおそらく問題に近づくはずの方法を説明していますが、あなたの現在の試みが間違っていたことを説明しませんでした。私が理解しているように、あなたの戦略は、各ノードを調べ、再帰を使ってすべてのノードを見つけることで、最も低い値を追跡することでした。すべてのノードを調べたら、その結果がツリー全体の最小値であることがわかります。これは完全に有効なアプローチであり、あなたが期待しているように議論がうまく機能しないという点を除いては効果があります。

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

あなたは、いくつかの単純なコードでこれをテストすることができます：あなたは、Xは、関数の内部ではなく、トップレベルでインクリメントされたコードを実行したときにあなたが見ることができます

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

x = 2 
add_one_to(x) 
print 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を=」追加（）と最後にmin_tを返すために、あなたのreturn文を変更しました。 （おそらく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 

Answer 4

は、最小の要素を見つけるための再帰的な方法である：

minelement = float("inf") 
def minimum(self, root): 
    global minelement 
    if root: 
     if root.data < minelement: 
      minelement = root.data 

     self.minimum(root.left) 
     self.minimum(root.right) 
    return minelement