непредвиденное выход бинарное дерево поиска в питона

Question

class Node(): 
    def __init__(self,data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 
class BSTree(): 
    def __init__(self): 
     self.root = None 
    def add(self,data): 
     if self.root is None: 
      self.root = Node(data) 
      self.reset() 
     else: 
      while self.curNode is not None: 
       if data < self.curNode.data: 
        self.curNode = self.curNode.left 
       elif data > self.curNode.data: 
        self.curNode = self.curNode.right 
      self.curNode=Node(data) 
      self.reset() 
    def pprint(self,Node,indent): 
     if Node is not None: 
      self.pprint(Node.left, indent+1) 
      print indent*"  ",Node.data 
      self.pprint(Node.right, indent+1) 
if __name__=="__main__": 
    y = BSTree() 
    for pres in ["OBAMA","BUSHW","CLINTON","BUSHG","REGAN","CARTER","FORD","NIXON","JOHNSON"]: 
     y.add(pres) 
    y.pprint(y.root,0) 

Этот код выполняется без ошибок, но мой выход

OBAMA 

Я не могу понять, почему этот код не имеет ошибок во время выполнения, но только добавить первый узел в дерево

Answer 1

Я понял ответ. Спасибо, данбен, за руководство в получении! Это была комбинация того, что он говорил, и рассмотрел некоторые другие реализации самостоятельно. Вот что я придумал, если кто-то задавался вопросом.

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

    def __add(self,node,data): 
     if self.root is None: 
      self.root = Node(data) 
     if node is None: 
      return Node(data) 
     else: 
      if data < node.data: 
       node.left = self.__add(node.left,data) 
      elif data > node.data: 
       node.right = self.__add(node.right,data) 
      return node 

    def add(self,data): 
     self.__add(self.root,data) 

    def __preorder(self,node): 
     if node is not None: 
      print node.data 
      self.__preorder(node.left) 
      self.__preorder(node.right) 

    def preorder(self): 
     self.__preorder(self.root) 

    def __inorder(self,node): 
     if node is not None: 
      self.__inorder(node.left) 
      self.__inorder(node.right) 
      print node.data 

    def inorder(self): 
     self.__inorder(self.root) 

    def __postorder(self,node): 
     if node is not None: 
      self.__postorder(node.left) 
      print node.data 
      self.__postorder(node.right) 

    def postorder(self): 
     self.__postorder(self.root) 

    def pprint(self,Node,indent): 
     if Node is not None: 
      self.pprint(Node.right, indent+1) 
      print indent*"  ",Node.data 
      self.pprint(Node.left, indent+1) 
    def leafcount(self,Node): 
     if Node is None: 
      return 0 
     if self.atLeaf(Node): 
      return 1 
     else: 
      return self.leafcount(Node.left)+self.leafcount(Node.right) 

if __name__=="__main__": 

    y = BSTree() 

    for pres\ 
     in ["OBAMA","BUSHW","CLINTON","BUSHG","REGAN","CARTER","FORD","NIXON","JOHNSON"]: 
     y.add(pres) 

    y.pprint(y.root,0) 

Answer 2

def __add(self,node,data): 
     if node is None: 
      return Node(data) 
     else: 
      if data < node.data: 
       node.left = self.__add(node.left,data) 
      elif data > node.data: 
       node.right = self.__add(node.right,data) 

Эта функция является неправильной. Он всегда перезаписывает первый левый или правый дочерний узел корневого узла, если корень не равен None.

Поскольку это домашнее задание, я не буду писать для вас правильную версию, но вот подсказка - сначала найдите место, где должен быть добавлен новый узел, затем назначьте левому или правому ребенку.

Редактировать: в ответ на ваше обновление - вы сейчас очень близко. Ваша последняя ошибка заключается в том, что вы фактически не привязываете новый узел к чему-либо. Скорее, вы назначаете его curNode, который не является частью структуры вашего дерева. Вместо этого вы хотите связать его с родительским узлом как с правом, так и с левым дочерним элементом.