python - 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

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

我建议通过关键字参数跟踪节点深度，我将其称为 _深度 以强调它应该是私有(private)的，即不由用户提供。

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()