计算二叉搜索树中不同类型的节点

Question

我正在尝试编写一个计算不同类型节点的递归函数：

零节点数children
节点数 child

节点数children

def _node_counts_aux(self,node):

    zero = 0
    one = 0
    two = 0

    if node is not None:     
        #print("==========")
        #print(node)
        #print(node._left)
        #print(node._right)
        #print()

        # Two children case
        if node._left is not None and node._right is not None:
            #print("Two")
            two = self._node_counts_aux(node._left)[2] + self._node_counts_aux(node._right)[2] + 1

        # One child case
        elif node._left is None and node._right is not None:
            #print("One")
            one = self._node_counts_aux(node._right)[1] + 1

        elif node._right is None and node._left is not None:
            #print("One")
            one = self._node_counts_aux(node._left)[1] + 1

        # Zero children case
        elif node._left is None and node._right is None:
            #print("Zero")
            zero = self._node_counts_aux(node._left)[0] + self._node_counts_aux(node._right)[0] + 1

    return zero, one, two

我相信 if 语句结构涵盖所有情况，但是当我运行我的程序使用这个 bst 时，我得到这个结果：

Zero children: 0
One child:     0
Two children:  4

我已经使用 print 语句测试了我的程序，我确定我的递归调用有问题。然而，问题是，一切（据我所知）都是正确的。有人可以指出我的错误吗？提前致谢

Answer 1

你的函数实际上returns后续全节点的数量。您应该保留每次调用的计数器信息。

def _node_counts_aux(self,node):
    # 'n[i]' is the total number of nodes with 'i' sons
    n = [0,0,0]
    sons = 0

    #one call for left 
    if node._left:
        n = [sum(x) for x in zip(n, self._node_counts_aux(node._left))]
        sons += 1

    #one call for right 
    if node._right:
        n = [sum(x) for x in zip(n, self._node_counts_aux(node._right))]
        sons += 1

    #count this node in the relevant counter 
    n[sons] += 1

    return n

更好（代码重用）：

def _node_counts_aux(self,node):
    # 'n[i]' is the total number of nodes with 'i' sons
    n = [0,0,0]
    sons = 0

    for son_node in [node._left, node._right]:
        if son_node:
            n = [sum(x) for x in zip(n, self._node_counts_aux(son_node))]
            sons += 1

    #count this node in the relevant counter 
    n[sons] += 1

    return n

计算二叉搜索树中不同类型的节点

Counting different types of nodes in a Binary Search Tree

recursion

binary-tree

python-3.x