2017-08-29 31 views
-4

再帰を使用してバイナリ検索ツリーに値を挿入しようとしていますが、これをinorderトラバーサルを使用して実行すると、Noneという出力が得られます。私はこれを実装している他の言語を見ようとしましたが、コピーしようとしましたが動作しません。私はツリーのルートを挿入関数に渡しています。空でなければ、左右どちらかを横切ることを期待していました。誰かがこれに間違っていることを教えてもらえますか?私はbst.get_root()にbst.rootを作ろうとしましたが、それと同じ結果が得られます。Pythonで再帰を使用してバイナリ検索ツリーに挿入

class Node: 
    def __init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 

class BinaryTree: 
    def __init__(self): 
     self.root = None 
     self.size = 0 

    def get_size(self): 
     return self.size 

    def get_root(self): 
     return self.root 

    def insert(self, root, value): 
     if root is None: 
      root = Node(value) 
     else: 
      if value < root.value: 
       root.left = self.insert(root.left, value) 
      else: 
       root.right = self.insert(root.right, value) 
     return root 

    def inorder(self, root): 
     if root == None: 
      return 
     else: 
      self.inorder(root.left) 
      print(root.value, end=" -> ") 
      self.inorder(root.right) 

bst = BinaryTree() 
bst.insert(bst.root, 2) 
bst.insert(bst.root, 4) 
bst.insert(bst.root, 3) 
bst.insert(bst.root, 1) 

print(bst.inorder(bst.root)) 

答えて

-2

問題は、ルートノードに挿入した結果を割り当てたことがないことでした。メソッドの挿入と、self.rootに_insertの戻り値がどのように割り当てられているかを見てください。

class Node: 
    def __init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 


class BinaryTree: 
    def __init__(self): 
     self.root = None 
     self.size = 0 

    def get_size(self): 
     return self.size 

    def get_root(self): 
     return self.root 

    def insert(self, value): 
     self.root = self._insert(self.root, value) 

    def _insert(self, root, value): 
     if root is None: 
      root = Node(value) 
     elif value < root.value: 
      root.left = self._insert(root.left, value) 
     elif value >= root.value: 
      root.right = self._insert(root.right, value) 
     return root 

    def inorder(self, root): 
     if root == None: 
      return 
     else: 
      self.inorder(root.left) 
      # print(root.value, end=" -> ") 
      print(root.value) 
      self.inorder(root.right) 

bst = BinaryTree() 
bst.insert(2) 
bst.insert(4) 
bst.insert(3) 
bst.insert(1) 

print(bst.inorder(bst.root)) 

EDIT 大きな問題は、インサート呼び出しの結果がルートに保存されていないということです。次のようにあなたがあなたの元のコードを変更した場合、それはまた、動作します:

bst = BinaryTree() 
bst.root = bst.insert(bst.root, 2) 
bst.root = bst.insert(bst.root, 4) 
bst.root = bst.insert(bst.root, 3) 
bst.root = bst.insert(bst.root, 1) 
+0

こんにちは@アスタリスク、ありがとうございました。なぜこれが動作し、私のコードはしなかったのですか? self.rootにinsert関数を割り当てる必要があるのはなぜですか?また、これを1つの関数で行うことは可能ですか? – mike26

+0

もちろん、問題は、あなたのルートとしての挿入結果を保存しないということです。コードを次のように変更した場合:bst = BinaryTree() bst.root = bst.insert(bst.root、2) bst.root = bst.insert(bst.root、4) bst.root = bst。挿入(bst.root、3) bst.root = bst.insert(bst.root、1)。それも動作します。 – Asterisk

+0

投票者が私の答えに何が問題であるか説明できますか?フィードバックありがとう!説明のために – Asterisk

1

問題はnodeNoneかもしれないし、あなたがそれで関数を呼び出し、その後、Noneにノードを割り当て、何も保存されません取得しているということです。

のは、戦利品を持ってみましょう:

def insert(self, root, value): # say root is None 
    if root is None: 
     root = Node(value) # here we're doing: `None = Node(value)` 
    else: 
     if value < root.value: 
      root.left = self.insert(root.left, value) 
     else: 
      root.right = self.insert(root.right, value) 
    return root 

それを修正するために、我々は、「1つ上のレベルに行く」する必要があるとnode.leftNoneであるならば、node.leftへの割り当てを行う(ルートは道で悪い名前です、代わりに "ノード"を使用しています)。それを行うには

一つの方法は、次のようになります。

def insert(self, value): # this is the function that gets called, pay attention that we're not sending `root` 
    if self.root is None: 
     self.root = Node(value) 
    else: 
     self._insert(self.root, value) # here's the call to a "private" function to which we are passing nodes down, starting from root 

def _insert(self, node, value): 
    if value < node.value: # we know that `node` cannot be None - so it's safe to check its value! 
     if node.left: 
      self._insert(node.left, value) # the recursive call is done only when `node.left` is not None 
     else: 
      node.left = Node(value) # direct assignment 
    else: 
     if node.right: 
      self._insert(node.right, value) 
     else: 
      node.right = Node(value) # direct assignment 

二つのコメント:

  1. 今すぐクリーナーインタフェースがあります、今見てどのように挿入呼び出しを参照してください。 bst = BinaryTree() bst.insert(2) bst.insert(4) bst.insert(3) bst.insert(1)

  2. 挿入値を「設定」するアクションです。何かを返す必要はありません(本当にしたい場合でも可能です)。

+0

ありがとう。私が理解していないことは、私のコードでは、ツリーのルートであるinsert()にbst.rootを渡していることです。もし私が誤解されていないならば、Pythonは関数内で参照によって渡します。もしrootがNoneならば、rootはツリーのルートを参照し、最初はNoneなので、挿入された値はrootに代入されるべきです。ここで、ルートよりも低い値を挿入すると、else条件に進み、root.leftにinsert()を適用して、ルートにもう一度行き、Noneになり、その値をrootに割り当てます。左に戻し、それをvar root.leftに代入します。 – mike26

+0

@myc26を引数 'bst.root'で' None'に解決していますので、 'bst.insert(bst.root、2)'を呼び出すと、 'bst.insert(None、 2) ' - あなたがデバッガを使って走るなら、それを見ることができます。お役に立てれば! – alfasin

+0

ありがとうございます。だから、何も関数に渡すことはできません。私はNoneを含むルートのメモリスロットを通過していると思った。ありがとう@alfasin – mike26

関連する問題