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

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

 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, который не является частью структуры вашего дерева. Вместо этого вы хотите связать его с родительским узлом как правого или левого потомка.

Answer 2

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

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)