python之计算二叉搜索树中的节点数

我正在尝试打印二叉搜索树的大小。但是，我的代码现在正在做的是打印每个节点所在的级别。我觉得好像我把我的 count += 1 放在了错误的地方，或者它可能是别的东西。我想知道是否有人可以为我提供额外的帮助，并给我提示如何解决这个问题。

输出:

3 
3 
2 
3 
3 
2 
1 

预期输出:

7 

我的代码:

def BST_size(root, count = 0): 
    if root is None: 
        print "size -1 (Null value in root)" 
    if root is not None: 
        count += 1 
        if root.left is not None: 
            BST_size(root.left, count) 
        if root.right is not None: 
            BST_size(root.right, count) 
    print count  

额外部分:

class Node: 
    def __init__(self,value): 
        self.right = None 
        self.left = None 
        self.value = value 
 
 
def BST_Insert(root, node):     # root --> root of tree or subtree! 
    if root.value is None: 
        root = node             # beginning of tree 
    else: 
        if root.value > node.value:     # go to left 
            if root.left is None: 
                root.left = node 
            else: 
                BST_Insert(root.left, node) 
 
        if root.value < node.value:    # go to right 
            if root.right is None: 
                root.right = node 
            else: 
                BST_Insert(root.right, node) 
 
r = Node(4) 
# left 
a = Node(2) 
b = Node(1) 
c = Node(3) 
# right 
d = Node(8) 
e = Node(6) 
f = Node(10) 
 
BST_Insert(r, a) 
BST_Insert(r, b) 
BST_Insert(r, c) 
BST_Insert(r, d) 
BST_Insert(r, e) 
BST_Insert(r, f) 

请您参考如下方法:

有两种方法可以做到这一点。

最简单的方法是返回每次递归调用的计数，而不是仅仅打印并递增:

def BST_size(root): 
    if root is None: 
        return -1 
    if root is not None: 
        if root.left is not None: 
            return 1 + BST_size(root.left) 
        if root.right is not None: 
            return 1 + BST_size(root.right) 
 
def print_BST_size(root): 
    size = BST_size(root) 
    if size == -1: 
        print "size -1 (Null value in root)" 
    else: 
        print "size", size 

但是，这仍然不起作用，因为您只是遍历左侧或右侧，而不是两者。你想要的是:

    count = -1 
    if root is not None: 
        if root.left is not None: 
            count += BST_size(root.left) 
        if root.right is not None: 
            count += BST_size(root.right) 
    return count 

但是，看起来您正在尝试以尾递归方式使用累加器。在 Python 中这样做真的没有意义，因为 Python 不会优化尾调用，但对于其他语言和理论上的原因来说，这是一项有用的技能，所以……

这里的问题是您需要所有递归调用共享相同的值，这意味着您需要一个可变值。因此，您可以从 [0] 而不是 0 开始，并执行 count[0] += 1 而不是 count + = 1。

或者您可以重新安排您的代码，使其不可变地使用 count，而是将更新后的计数从一侧向下传递到另一侧。

无论哪种方式，您的代码都有另一个问题。您的递归基本情况是 root 是 None。但是你也把它作为一个特例，打印 -1 而不是 0。你不能同时拥有它。