Метод вставки двоичного дерева поиска не может вставить какие-либо узлы - PullRequest
Новая
       2

Метод вставки двоичного дерева поиска не может вставить какие-либо узлы

2 голосов
/ 17 июня 2019

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

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.value)


def insert(root,value):
    if root is None:
        root = Node(value)
        print(1)
    elif value <= root.value:
        root.left = insert(root.left, value)
        print(2)
    else:
        root.right = insert(root.right, value)
        print(3)


def search(root,value):
    if root is None:
        print("False")
    elif root.value == value:
        print("True")
    elif value <= root.value:
        return search(root.left, value)
    else:
        return search(root.right, value)


root = None

insert(root,15)
insert(root,10)
insert(root,25)

search(root,10)

Вывод: 

1
1
1
False

1 Ответ

2 голосов
/ 17 июня 2019

Когда вы делаете назначение, такое как root = Node(value), в функции, оно не изменяет объект root во внешней области видимости, как вы могли бы ожидать. Вместо этого он переназначает локальную переменную root внутри функции insert на новый объект Node, который выходит из области видимости при возврате функции.

Одно из решений - вернуть созданный вами новый корневой объект и переназначить его в области вызова, перезаписав значение старого корневого объекта. Это также важно для рекурсивных присваиваний, чтобы свойства .left и .right были установлены правильно.

Вот фиксированный код: 

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.value)


def insert(root,value):
    if root is None:
        root = Node(value)
        print(1)
    elif value <= root.value:
        root.left = insert(root.left, value)
        print(2)
    else:
        root.right = insert(root.right, value)
        print(3)

    return root
    #^^^^^^^^^^


def search(root,value):
    if root is None:
        print("False")
    elif root.value == value:
        print("True")
    elif value <= root.value:
        return search(root.left, value)
    else:
        return search(root.right, value)


root = None
root = insert(root,15)
#^^^^^^
root = insert(root,10)
root = insert(root,25)
search(root,10)
search(root,15)
search(root,25)

Выход: 

1
1
2
1
3
True
True
True

Я бы также рекомендовал удалять отпечатки изнутри ваших функций, хотя я понимаю, что вы, скорее всего, находитесь в режиме отладки. Вот быстрая очистка: 

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.value)


def insert(root,value):
    if not root:
        root = Node(value)
    elif value <= root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)

    return root

def search(root, value):
    if not root:
        return False
    elif root.value == value:
        return True
    elif value <= root.value:
        return search(root.left, value)

    return search(root.right, value)


if __name__ == "__main__":
    root = None
    root = insert(root, 15)
    root = insert(root, 10)
    root = insert(root, 25)
    root = insert(root, 27)
    print(root, root.left, root.right, root.right.right)
    print(search(root, 10))
    print(search(root, 15))
    print(search(root, 25))
    print(search(root, 27))
    print(search(root, 12))
...