2

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

6 回答 6

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

    return BST_size(root.left, BST_size(root.right, count + 1))
于 2013-10-04T18:13:28.750 回答
4

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

简单的方法是return从每个递归调用中计数，而不是仅仅printing 它，然后递增：

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 不会优化尾调用，但它是学习其他语言和理论上的有用技能，所以……</p>

这里的问题是您需要所有递归调用共享相同的值，这意味着您需要一个可变值。所以，你可以从[0]代替开始0，然后count[0] += 1代替count += 1。

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

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

于 2013-10-04T18:15:10.710 回答
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))
于 2013-10-04T18:15:43.777 回答
1 
if root is not None:
        count = 1
        if root.left is not None:
            count += BST_size(root.left, count)
        if root.right is not None:
            count += BST_size(root.right, count)
return count
于 2013-10-04T18:11:23.647 回答
1

这是一个简短的答案

您必须进行树遍历，其中函数返回低于 + 1 的节点数（本身）

伪代码：

def counter(t):
  rCount = counter(t.right)
  lCount = counter(t.left)
  return 1 + rCount + lCount
于 2013-10-04T18:16:16.517 回答
0

你可以使用这样的东西：

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

并像下面这样调用它：

print ("\nCount of Nodes :" + str(countNodes(root)))
于 2018-04-05T07:14:10.990 回答