バイナリ検索ツリーを実装しているときにPythonの最大再帰深度を超えました

Question

Pythonを使用してBSTを学習していましたが、insertメソッドとfindメソッドを実装しようとしました。しかし、insertNodeメソッドの最大再帰深度を超過しました。私はBSTのデータ構造に慣れていないので、Pythonでメソッドを実装するのに苦労しています。私は研究し、インターネット上のコードに似たコードを作ってみましたが、まだエラーが出ています。

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

class BST: 
    def __init__(self): 
     self.root = None 
    def insert(self,data): 
     temp = Node(data) 
     if self.root is None: 
      self.root = temp 
     else: 
      self.insertNode(self.root,data) 
    def insertNode(self,root,data): 
     temp = Node(data) 
     if data < self.root.data: 
      if self.root.left is None: 
       self.root.left = temp 
      else: 
       self.insertNode(self.root.left,data) 
     elif data > self.root.data: 
      if self.root.right is None: 
       self.root.right = temp 
      else: 
       self.insertNode(self.root.right,data) 
    def findinTree(self,root,data): 
     if self.root is None: 
      return False 
     if data == self.root.data: 
      return True 
     if data < self.root.data: 
      self.findinTree(self.root.left,data) 
     else: 
      self.findinTree(self.root.right,data) 
     return False 


bst = BST() 
bst.insert(30) 
bst.insert(10) 
bst.insert(50) 
bst.insert(90) 
bst.insert(100) 
bst.insert(15) 

エラーをデバッグして、機能が意図したとおりに機能するようにしてください。

Answer 1

これらのメソッドは、ルート ;-)問題の原因である可能性があります：はVPfBの提案を取り、しませんでした：

def insertNode(self, root, data): 
    if data < root.data: # <- use the root parameter ... 
     if root.left is None: 
      root.left = Node(data) 
     else: 
      self.insertNode(root.left, data) 
    else: 
     if root.right is None: 
      root.right = Node(data) 
     else: 
      self.insertNode(root.right, data) 

def findinTree(self, root, data): 
    if root is None: 
     return False 
    if data == root.data: 
     return True 
    if data < root.data: 
     return self.findinTree(root.left, data) 
    else: 
     return self.findinTree(root.right, data) 

NBコード

アップデートをテストしていません不要なノードを作成します。

Answer 2

insertNodeでは、ツリーのルートであるself.rootを参照してください。代わりに、関数のパラメータrootを参照する必要があります。実際に

、第一サブレベルが作成された後（bst.insert(50)）、ツリーのルートの右の枝はもうNoneではありませんので、それはself.insertNode(self.root.right,data)

def insertNode(self,root,data):                                           
    temp = Node(data)                                              
    if data < root.data:                                             
     if root.left is None:                                            
      print("Inserting {} on the left branch of {}".format(data, root.data))                              
      root.left = temp                                            
     else:                                                
      print("Inserting {} on the left branch of {}".format(data, root.data))                              
      self.insertNode(root.left,data)                                        
    elif data > root.data:                                            
     if root.right is None:                                           
      print("Inserting {} on the right branch of {}".format(data, root.data))                              
      root.right = temp                                            
     else:                                                
      print("Inserting {} on the right branch of {}".format(data, root.data))                              
      self.insertNode(root.right,data)