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 に設定されているのですが、どうすれば修正できますか?