Блог

Главная - Вопросы по программированию - Двоичное дерево поиска по порядку не работает (python)

Двоичное дерево поиска по порядку не работает (python)

#python #binary-search-tree

Вопрос:

Я возился с изучением объектов и классов, и когда я, наконец, почувствовал, что мне удалось разобраться в том, как построить двоичное дерево поиска в python, я столкнулся с проблемой. Вот мой код:

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

class BST:
    def __init__(self):
        self.root = None

    def add(self,current,value):
        if self.root == None:
            self.root = node(value)
        else:
            if value < current.value:
                if current.left == None:
                    current.left = node(value)
                else:
                    self.add(current.left,value)
            if value > current.value:
                if current.right == None:
                    current.right = node(value)
                else:
                    self.add(current.right,value)

    def visit(self,node):
        print(node.value)

    def inorder(self,current):
        self.inorder(current.left)
        self.visit(current)
        self.inorder(current.right)

Tree = BST()
root = node(2)
Tree.root = root
Tree.add(Tree.root,7)

Tree.inorder(Tree.root)

после запуска кода я получил ошибку: AttributeError: 'NoneType' object has no attribute 'left' .
Ошибка возникает из функции inorder, так как, по-видимому, значение, которое я вставляю в функцию, является объектом без типа.
как вы можете видеть, корень дерева является объектом узла, поэтому у него должен быть атрибут «слева» в соответствии с кодировкой в классе. Я был бы очень признателен, если бы кто-нибудь мог помочь мне с тем, что я делаю неправильно.
Заранее спасибо!

ПРАВКА: Я должен отметить , что я проверил, является ли корень узлом с isinstance() функцией, и действительно ли он вернул значение True.

Комментарии:

1. Таким образом, вы ожидаете, что каждый узел в вашем дереве будет иметь как левый, так и правый дочерний узел? Я надеюсь, что у вас действительно хорошая сделка с бесконечным объемом оперативной памяти, который вам понадобится для хранения этого дерева…

2. Вы можете определить лист?

Ответ №1:

Я думаю, вам следует проверить, что ток не равен нулю, прежде чем обращаться к нему слева и справа.

   def inorder(self, current):
        if current:
            self.inorder(current.left)
            self.visit(current)
            self.inorder(current.right)

Ответ №2:

У вашего дизайна есть некоторые проблемы. Дерево должно быть единственным объектом, который знает о корне. Вам не нужно передавать корень. Обратите внимание, как это проще в использовании:

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

class BST:
    def __init__(self):
        self.root = None

    def add(self,value,current=None):
        if not self.root:
            self.root = node(value)
            return

        if not current:
            current = self.root

        if value < current.value:
            if not current.left:
                current.left = node(value)
            else:
                self.add(value,current.left)
        else:
            if not current.right:
                current.right = node(value)
            else:
                self.add(value, current.right)

    def visit(self,node):
        print(node.value)

    def inorder(self,current=-1):
        if current == -1:
            current = self.root
        if not current:
            return
        self.inorder(current.left)
        self.visit(current)
        self.inorder(current.right)

Tree = BST()
Tree.add(2)
Tree.add(7)

Tree.inorder()
Метки: