Двоичное дерево поиска — метод подсчета узлов с неверным выводом ⇐ Python

[Anonymous]

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

Код: Выделить всё

    22
/  \
12   30
/ \   / \
8  20 25 40

он ​​возвращает 0,0,1, но я не думаю, что это правильно, разве он не должен возвращать 4,0,3? поскольку 22,12 и 30 — это двойки, поскольку они имеют два дочерних узла, а 8,20,25 и 40 — нули, поскольку они указывают на листья. Буду очень признателен за любую помощь!
Вот мой код:

Код: Выделить всё

def node_counts(self):
"""
---------------------------------------------------------
Returns the number of the three types of nodes in a BST.
Use: zero, one, two = bst.node_counts()
-------------------------------------------------------
Returns:
zero - number of nodes with zero children (int)
one - number of nodes with one child (int)
two - number of nodes with two children (int)
----------------------------------------------------------
"""
zero, one, two = self.node_counts_aux(self._root)
return zero, one, two

return

def node_counts_aux(self, node):
zero = 0
one = 0
two = 0

if node is None:
return zero, one, two

else:
self.node_counts_aux(node._left)
print(node._value)
self.node_counts_aux(node._right)

if node._left is not None and node._right is not None:
two += 1
elif (node._left is not None and node._right is None) or (node._left is None and node._right is not None):
one += 1
else:
zero += 1

return zero, one, two

Сейчас я выполняю обход по порядку, я ожидаю это 4,0,3 вместо этого 0,0,1

Подробнее здесь: https://stackoverflow.com/questions/782 ... ect-output