二进制搜索中节点数的计算

Question

我试图打印我的二叉搜索树的大小。但是，我的代码现在所做的是打印每个节点所处的级别。我觉得好像把我的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)

Answer 1

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

---

简单的方法是return每个递归调用的计数，而不仅仅是print并递增：

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。你不能两全其美。

Answer 2

def BST_size(root):
    if root is None:
        return 0
    else:
        return BST_size(root.left) + BST_size(root.right) + 1

print "Size is: " + str(BST_size(r))

Answer 3

def BST_size(root, count = 0):
    if root is None:
        return count

    return BST_size(root.left, BST_size(root.right, count + 1))