バイナリ検索ツリー - 再帰的挿入python

Question

私はツリーを初期化してノード（stems）を追加し続ける再帰的な挿入関数を持つバイナリ検索ツリーを正しく構築しようとしています。ここで私は（そう、おそらくあまりにも長ったらしい、コーディングに新しい）、これまで行ってきたコードは次のとおりです。

class Binary_Search_Tree: 

    class __BST_Node: 

    def __init__(self, value): 
     self.value = value 
     self.right_child = None 
     self.left_child = None 

    def __init__(self): 
    self.__root = None 
    self.__height = 0 
    self.value = None 

    def _recursive_insert(self, value): 
    new_stem = Binary_Search_Tree.__BST_Node(value) 
    if self.__root is None: 
     self.__root = new_stem 
     self.__root.value = new_stem.value 
    else: 
     if self.__root.value > new_stem.value: 
     if self.__root.right_child is None: 
      self.__root.right_child = new_stem 
      self.__root.right_child.value = new_stem.value 
     else: 
      self.__root.right_child._recursive_insert(self.__root, value) 
     else: 
     if self.__root.left_child is None: 
      self.__root.left_child = new_stem 
      self.__root.left_child.value = new_stem.value 
     else: 
      self.__root.left_child._recursive_insert(self.__root, value) 

    def insert_element(self, value): 
    element_to_insert = self._recursive_insert(value) 
    return element_to_insert 

私は、メインメソッドでは、この新しいツリーに値を追加しよう：

if __name__ == '__main__': 
    new = Binary_Search_Tree() 
    new.insert_element(23) 
    new.insert_element(42) 
    new.insert_element(8) 
    new.insert_element(15) 
    new.insert_element(4) 
    new.insert_element(16) 

私が得るエラーは次のとおりです。'__BST_Node' object has no attribute '_recursive_insert'これは、最初の要素を挿入した後にポップアップするので、エラーがelse文のどこかで発生していると推測しています。誰かが私のエラーがどこにあるかを知ることができる、またはこのコードをより読みやすくする/ユーザーフレンドリーにするためのヒントがあれば、私は感謝しています！このように同様

self.__root.right_child._recursive_insert(self.__root, value) 

：

Answer 1

問題は、このラインであるあなたがBinary_Search_Treeの方法であることが_recursive_insertを定義した

self.__root.left_child._recursive_insert(self.__root, value) 

、しかし、あなたがそれを呼んでいますインスタンス__BST_Node、self.__root.xxxxx_child._recursive_insertであり、xxxx_childはBST_Nodeのインスタンスです。

---

実際には、_recursive_insert関数全体が必要なものになります。あなたは何も返していませんが、（存在しない）戻り値をinsert_elementの値に割り当てています。

固定コード：

def _recursive_insert(self, root, value): 
    new_stem = Binary_Search_Tree.__BST_Node(value) 

    if root is None: 
     root = new_stem 

    else: 
     if root.value < new_stem.value: 
      if root.right_child is None: 
       root.right_child = new_stem 
      else: 
       root = self._recursive_insert(root.right_child, value) 

     elif root.value > new_stem.value: 
      if root.left_child is None: 
       root.left_child = new_stem 
      else: 
       root = self._recursive_insert(root.left_child, value) 

     return root 

def insert_element(self, value): 
    self.__root = self._recursive_insert(self.__root, value) 
    return element_to_insert 

1. あなたの関数が挿入されている値は、偽のエントリを引き起こし、既存の値に等しくなるとき、あなたの関数がケースを処理しません、更新ルート
2. を返しませんでした。
3. 各再帰呼び出しで、関数が同じ値を渡していたため、何をすべきかを知ることができませんでした。ノードの新しいパラメータは、呼び出しの間に渡される必要があります。これにより、ベースケースを確立してリターンすることができます。