итератор двоичного дерева python - почему возвращаемый узел становится None?

Question

итератор двоичного дерева python - почему возвращаемый узел становится None?

Исключение нулевого указателя генерируется, когда приложение пытается использовать null в случае, когда требуется объект. К ним относятся:

Вызов метода экземпляра объекта null.
Доступ или изменение поля объекта null.
Принимая длину null, как если бы это был массив.
Доступ или изменение слотов null, как если бы это был массив.
Бросок null как будто это было значение Throwable.

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

Ссылка: http://docs.oracle.com/javase/8/docs/api/java/lang/NullPointerException.html

0

python binary-search-tree

задан recnac 14 April 2019 в 09:38

1 ответ

Другие вопросы по тегам:

python binary-search-tree

Похожие вопросы:

score 0 · Answer 1

В вашей реализации есть три проблемы, на которые я хочу обратить внимание:

Основная проблема в том, что ваша реализация в Next неверна. Поскольку обход по порядку равен left->root->right, часть if (node.left != None): верна, но здесь:

        elif (node.right != None):
            node = node.right
            while (node.left != None):
                self.stack.append(node)
                node = node.left
            return node

вы должны сначала вернуть сам узел, прежде чем иметь дело с right child.

        else:
            if self.stack != []:
                node = self.stack.pop()
                node.left = None
                return node

и вы должны не только pop, когда узел является листом, вы должны помещать каждый узел в стек и вставлять каждый Next.

Вы не можете поместить Next в оба условия и блок, потому что он будет вызываться дважды.

while (self.Next(node) != None):
   node = self.Next(node)

!= None в if (node.left != None): не требуется в python, вы можете просто использовать if node.left:

, потому что Next имеет много проблем, поэтому Я должен переписать Next, вот версия, которую я отредактировал на основе вашего кода, и я прокомментировал в деталях:

class BTIterator:
    def __init__(self, root):
        self.stack = []  # Use a list as a stack by using pop() & append()
        self.root = root

    def Run(self):
        # find the left most node, which means then first node
        node = self.root
        while node.left:
            self.stack.append(node)
            node = node.left

        # start from left most node
        while node:
            print(node.val)
            node = self.Next(node)

    def Next(self, node):
        # find right node, if it is none, it's ok, we will deal with it afterwards
        node = node.right

        # reach the end
        if not self.stack and not node:
            return None

        # push left child iteratively
        while node:
            self.stack.append(node)
            node = node.left

        # this is next node we want
        return self.stack.pop()

Надеюсь, что это поможет вам, и прокомментируйте, если у вас есть дополнительные вопросы. :)