Количество трех типов узлов в двоичном дереве поиска (рекурсивно)

Question

Я пытаюсь написать функцию, которая будет считать три типа узлов в двоичном дереве поиска в Python. Он будет подсчитывать и возвращать общее количество узлов с 0 детьми, 1 ребенком и 2 детьми. Я заметил, что рекурсивный метод будет лучше для этого, а не для итеративного.

def node_counts(self): 
    """ 
    --------------------------------------------------------- 
    Returns the number of the three types of nodes in a BST. 
    Use: zero, one, two = bst.node_counts() 
    ------------------------------------------------------- 
    Postconditions: 
     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 

def _node_counts_aux(self, node): 
    zero, one, two = 0, 0, 0 
    if node is not None: 
     if not node._right and not node._left: 
      zero = 1 # I understand that the problem is here. 
     if node._left and node._right: 
      two = 1 + self._node_counts_aux(node._left)[2] + self._node_counts_aux(node._right)[2] 
     if node._left or node._right: 
      one = 1 + self._node_counts_aux(node._left)[1] + self._node_counts_aux(node._right)[1] 
    return zero, one, two 

""" 
I am testing with this Tree: 
     36 
    /\ 
    / \ 
    6  50 
    /\ /\ 
    4 17 49 84 
    ///\ 
     12 42 65 85 

The output with this code comes to: (0, 6, 4). 

""" 

Один столбец ошибочен в некотором смысле, но в некотором смысле также прав. Это не мое беспокойство. Моя забота - это нуль, не считающийся. нуль устанавливается как 0, так как я могу это исправить?

Answer 1

Проблема заключается в том, что метод _node_counts_aux() возвращает кортеж, но вы пытаетесь добавить 1 в свой результат. Вам придется вытащить счетчики для элементов типа 0, 1 и 2 из рекурсивных вызовов и использовать эти значения.

Answer 2

Вы должны аккумулировать результаты, полученные с помощью рекурсивных вызовов. Это можно сделать с помощью zero, one, two = map(sum, zip(result_right, result_left)), а затем добавить соответствующее значение в зависимости от количества детей.

Обратите внимание, что я использую операторы if/elif, иначе ваш код, когда узел имеет двух детей, также входит в следующий блок if для одного ребенка.

def _node_counts_aux(self, node): 
    zero, one, two = 0, 0, 0 
    if node is not None: 
     result_right = self._node_counts_aux(node._right) 
     result_left = self._node_counts_aux(node._left) 
     zero, one, two = map(sum, zip(result_right, result_left)) 
     if not node._right and not node._left: 
      zero += 1 
     elif node._left and node._right: 
      two += 1 
     elif node._left or node._right: 
      one += 1 
    return zero, one, two