Рекурсивное двоичное дерево поиска Python - PullRequest
0 голосов
/ 14 ноября 2018

Я хочу реализовать двоичное дерево поиска с элементом, left & right child и parent в python.

class BSTNode:
""" An internal node for a BST .    """

def __init__(self, item):
    """ Initialise a BSTNode on creation, with value==item. """
    self._element = item
    self._leftchild = None
    self._rightchild = None
    self._parent = None



def __str__(self):
    node = self

    if node != None:
        s = str(node._element)
        if node._leftchild: 
            node._leftchild.__str__()
            s = str(node._element)
            s+= ' '
        elif node._rightchild:
            node._rightchild.__str__()
            s += str(node._element)
        else:
            return s
    else:
        return ''


def add(self, item):
    node = self
    if node:
        if item <node._element :
            if node._leftchild is None:
                node._leftchild = BSTNode(item)
                node._leftchild._parent = node
            else:
                node._leftchild.add(item)
        elif item > node._element:
            if node._rightchild is None:
                node._rightchild = BSTNode(item)
                node._rightchild._parent = node
            else:
                node._rightchild.add(item)


tree = BSTNode(3);
tree.add(7);
 print(tree.__str__());

Я написал эту программу, но когда я ее запускаю, она выводит None, но должна выдавать 3 7 (порядок - обход по порядку).Кто-нибудь знает, что я делаю не так?

1 Ответ

0 голосов
/ 14 ноября 2018

Ваш __str__ метод неверен. В частности, вы вызываете __str__() левого и правого потомков, но ничего не делаете с результатом. Также обратите внимание, что узел может иметь как левого и правого потомка (if...elif будет проверять только одного). Вы также не отступите s, если ударите по одному из блоков if или elif.

Вы можете упростить это до:

def __str__(self):
    node = self
    if node != None:
        s = str(node._element)
        if node._leftchild: 
            s = node._leftchild.__str__() + s
        if node._rightchild:
            s += ' ' + node._rightchild.__str__()
        return s
    return ''
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...