python 二叉搜索树大小

Question

我正在尝试实现二叉搜索树，但我的 size() 方法有问题，该方法计算树中的节点数。

class BSTNode:
def __init__(self, item):

    self._element = item
    self._leftchild = None
    self._rightchild = None
    self._parent = None

这是我的尺码函数的样子：

def size(self):

    size = 0
    if self != None:
        size += 1
        if self._leftchild != None:
            size += 1 + self._leftchild.size()
        if self._rightchild != None:
            size += 1 + self._rightchild.size()
    return size

它多算了树中实际存在的节点数，我不知道为什么，也许是因为它是递归的，但我不确定。

Answer 1

替换

size += 1 + self._leftchild.size()

有

size += self._leftchild.size()

多出的 1 是多算的原因。右子也是如此。

Answer 2

您计算了两次节点。您应该只对每个节点计数一次。

def size(self):

    size = 0
    if self != None:
        size += 1
        if self._leftchild != None:
            size += self._leftchild.size()
        if self._rightchild != None:
            size += self._rightchild.size()
    return size

python 二叉搜索树大小

python binary search tree size

python

counting

nodes

binary-search-tree