バイナリ検索木pyem

Question

私はバイナリ検索ツリーを実装しようとしていますが、いくつかの問題に直面しています ノードの挿入。 誰かが私のpythonプログラムで何が間違っているかを指摘するのに役立つことができますか？ addChild（）関数が左の子（4、 "hans"）を正しく追加していませんか？ 私の再帰関数に問題がありますか？ありがとうございます。

class Node: 
    def __init__(self, key = None, value = None, leftChild = None, rightChild = None, parent = None): 
     self.key = key 
     self.value = value 
     self.leftChild = leftChild 
     self.rightChild = rightChild 
     self.parent = parent 

    def get_key(self): 
     return self.key 

    def get_value(self): 
     return self.value 

    def get_leftChild(self): 
     return self.leftChild  

    def get_rightChild(self): 
     return self.rightChild 

    def set_leftChild(self, key, value): 
     node = Node(key, value, None, None, self) 
     self.leftChild = node 

    def set_rightChild(self, key, value): 
     node = Node(key, value, None, None, self) 
     self.rightChild = node 

    def isLeaf(self): 
     if self.leftChild is None and self.rightChild is None: 
      return True 
     else: 
      return False 

class BinaryTree: 
    def __init__(self, key = None, value = None, leftChild = None, rightChild = None, parent = None): 
     self.root = Node(key, value, leftChild = None, rightChild = None, parent = None) 

    def addChild(self, key, value): 
     current = self.root 
     if current is None: 
      current = Node(key, value, leftChild = None, rightChild = None, parent = None) 
     else: 
      self._addChild(current, key, value) 

    def _addChild(self, current, key, value):     
     if current is None: 
      current = Node(key, value, leftChild = None, rightChild = None, parent = current) 
      return 

     if current.isLeaf() is True: 
      if current.get_key() > key: 
       current.set_leftChild(key, value) 
      else: 
       current.set_rightChild(key, value) 
      return 
     elif current.get_key() > key: 
       return self._addChild(current.get_leftChild(), key, value) 
     elif current.get_key() <= key:     
       return self._addChild(current.get_rightChild(), key, value) 

    def traversalInOrder(self): 
     if self.root is None: 
      return None 
     else: 
      self._traversalInOrder(self.root)    

obj = BinaryTree(10, "ram") 
obj.addChild(12, "hari") 
obj.addChild(4, "hans") 

Answer 1

current is None、あなたが実際にツリーにだけ、ローカル変数に値を格納しないでください。

それが動作するはずです。この方法は：

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

    def addChild(self, key, value): 
     current = self.root 
     if current is None: 
      self.root = Node(key, value, leftChild = None, rightChild = None, parent = None) 
     else: 
      self._addChild(current, key, value) 

    def _addChild(self, current, key, value):     
     if current.get_key() > key: 
      child = current.get_leftChild() 
      if child is None: 
      current.set_leftChild(key, value) 
      else: 
      self._addChild(child, key, value) 
     else: 
      child = current.get_rightChild() 
      if child is None: 
      current.set_rightChild(key, value) 
      else: 
      self._addChild(child, key, value) 


obj = BinaryTree() 
obj.addChild(10, "ram") 
obj.addChild(12, "hari") 
obj.addChild(4, "hans")