二元搜索樹中的三種節點數（遞歸）

我想寫一個函數，它將計算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

二元搜索樹中的三種節點數（遞歸）

回答

相關問題