python中二进制搜索树的总深度

Question

我试图在python中找到BST的总深度(这样根深度是1，它的子深度是2，那些子深度是3，等等)，总和是所有这些深度加在一起。我已经连续尝试了大约5个小时，但还是想不出答案。以下是我到目前为止生成的代码

class BinaryTreeVertex:
    '''vertex controls for the BST'''

    def __init__(self, value):
        self.right = None 
        self.left = None
        self.value = value

    ...

    def total_Depth(self):
        print ("val:", self.value)
        if self.left and self.right:
            return (self.left.total_Depth()) + 1 and (self.right.total_Depth()) + 1
        elif self.left:
            return 1 + self.left.total_Depth()
        elif self.right:
            return 1 + self.right.total_Depth()
        else:
            return 1
...

tree = BinarySearchTree()     
arr = [6,10,20,8,3]
for i in arr:
    tree.insert(i)
tree.searchPath(20)
print (tree.total_Depth()) #this calls the total_depth from vertex class

然后，生成的树如下所示。

   6         # Depth 1
___|___
3     10     # Depth 2
    ___|__
    8    20  # Depth 3

但是当我运行它时，它会打印出来：

val: 6
val: 3
val: 10
val: 8
val: 20
3

这棵树的3实际上应该是11，但我想不出如何得到它。请帮帮忙

编辑:为了澄清，我不是在寻找最大深度，我知道如何找到它。我需要我所解释的总深度，其中深度是树的级别。这里应该是11，因为6有深度1、3和10深度2，以及8和20深度3，其中1+2+2+3+3=11。

Answer 1

你的问题来自于这一行。

return (self.left.total_Depth()) + 1 and (self.right.total_Depth()) + 1

使用and将返回所提供的最左边的假的值，如果它们都是真的，则返回最右边的值。在这种情况下，它实际上总是返回self.right.total_Depth() + 1。

我推荐的是通过一个关键字参数来跟踪节点的深度，我称它为_depth是为了强调它应该是私有的，即不是由用户提供的。

class BinaryTreeVertex:

    ...

    def total_depth(self, _depth=1):

        if self.left and self.right:
            return self.left.total_depth(_depth=_depth + 1) \
                   + self.right.total_depth(_depth=_depth + 1) \
                   + _depth

        elif self.left:
            return _depth + self.left.total_depth(_depth=_depth + 1)

        elif self.right:
            return _depth + self.right.total_depth(_depth=_depth + 1)

        else:
            return _depth

你也可以像这样缩短它。

def total_depth(self, _depth=1):

    left_depth  = self.left.total_depth(_depth=_depth + 1)  if self.left else 0
    right_depth = self.right.total_depth(_depth=_depth + 1) if self.right else 0

    return left_depth + right_depth + _depth

在这两种情况下，你都可以像这样得到总深度。

tree.total_depth()