2

Python の二分探索ツリーで 3 種類のノードをカウントする関数を作成しようとしています。子が 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).

"""

1 列はある意味では間違っていますが、ある意味では正しいことでもあります。それは私の関心事ではありません。私の懸念は、ゼロがカウントされないことです。ゼロが 0 に設定されているのですが、どうすれば修正できますか?

4

2 に答える 2

2

問題は、メソッド_node_counts_aux()がタプルを返すが、1その結果に追加しようとしていることです。タイプ0、1、および2の要素のカウントを再帰呼び出しから引き出し、代わりにそれらの値を使用する必要があります。

于 2013-03-20T19:58:00.250 に答える
1

再帰呼び出しから得た結果を蓄積する必要があります。これは で行うことができzero, one, two = map(sum, zip(result_right, result_left))、子の数に応じて対応する値を追加します。

if/elifステートメントを使用していることに注意してください。それ以外の場合、ノードに 2 つの子がある場合のコードはif、1 つの子の次のブロックにも入ります。

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-21T21:30:39.997 に答える