二元搜索树中的三种节点数（递归）

我想写一个函数，它将计算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，所以我该如何解决这个问题？

来源

2013-03-20 user1757703

对不起，该函数被称为_node_counts_aux。它只是一个辅助函数，它执行主函数的递归。 – user1757703 2013-03-20 19:53:33

你在使用任何类别的课程吗？ – 2013-03-20 19:58:12

该类是一个自定义二叉搜索树ADT。它具有属性root。它使用另一个具有3个属性值，左侧和右侧的短二叉搜索树节点类。其中左和右基本上是指向它们各自位置的指针。 – user1757703 2013-03-20 20:01:55

问题是方法_node_counts_aux()返回一个元组，但您试图将1添加到其结果中。您必须从递归调用中抽取类型为0,1和2的元素的计数，然后使用这些值。

来源

2013-03-20 19:58:00

为了澄清，您可以使用下标运算符 - 'zero = 1 + self._node_counts_aux（node._left）[0] + self._node_counts_aux（node._right）[0]'等等（或元组拆包 - - 下面） – forivall 2013-03-20 19:59:28

虽然使用赋值：'zero_left，one_left，two_left = self._node_counts_aux（node._left）'可以更清楚地做到这一点，依此类推...... – 2013-03-20 20:00:19

是的，我打算写一个答案，元组解包，但是你的很好。 – forivall 2013-03-20 20:01:36

您必须累积递归调用的结果。这可以通过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

来源

2013-03-21 21:30:39

二元搜索树中的三种节点数（递归）

回答

相关问题