Допустимые случаи и указатели базы обхода дерева

Question

В настоящее время я перевожу свои навыки C ++ в python. Что касается обхода дерева, мне было интересно, какие типичные базовые случаи используются для определения конца ветви, поскольку python не использует указатели. Обычно в C ++ вы передаете следующий узел по ссылке и проверяете, имеет ли он значение NULL. Приведенный ниже пример кода работает; Однако есть ли потенциальные области для этих операторов if, которые могут вызвать ошибки для других примеров? Я прочитал другой ответ, что вы можете проверить, если self.data = None, но я не совсем уверен, почему это работает (это не сработало для моего примера). Спасибо!

 def inOrder(self, list3):
        if self.left:
          self.left.inOrder(list3)
        list3.append(self.data)
        if self.right:
          self.right.inOrder(list3)

Answer 1

Так вы бы определили узел в дереве.

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

Теперь давайте объявим узел temp со значением 10.

temp = Node(10)

Предположим, вы хотите проверить независимо от того, является ли temp листовым узлом или нет, вы бы сделали что-то вроде

if temp.left == None and temp.right == None:
    print('leaf node')
    return

Теперь, если вы прошли через конечный узел и проверяете, существует ли узел на самом деле или нет, вы должны сделать :

temp2 = temp.left
if temp2 == None:
    #abc

или

if not temp2:
    #abc

Не уверен, почему self.data = None будет работать, в этом случае вы объявляете узел, но не назначаете ему никаких данных.

Вероятно, произойдет сбой при проверке конечного узла, поскольку мы проверяем, присутствует ли левый или правый узел. Хорошо создать узел со значением.