двоичное дерево поиска impelemntation в python

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")