BST 总深度并发症

Question

这是一个有效的 BST 的摘录：

class BinaryTree():

    def __init__(self,rootid):
      self.left = None
      self.right = None
      self.rootid = rootid
    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

我决定不展示上面 class 的所有功能，只展示我想要实现的重要功能。

我想要计算树中每个节点的总深度，我尝试使用以下函数：

def depth(tree, count=1):
    if tree != None:
        return count + depth(tree.getLeftChild(), count+1) + depth(tree.getRightChild(), count+1)

count=1表示根节点深度为1的思想

然而，这个函数的问题是它在到达 None 节点时崩溃，我不知道如何修复它。

这是我在尝试使用该功能时收到的错误消息：

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

有人可以帮帮我吗？

Answer 1

你的递归函数depth需要一个中断条件：

def depth(tree):
    if tree == None:
        return 0
    else:
        return 1 + max(depth(tree.getLeftChild()), depth(tree.getRightChild()))

而且你忘记了子树深处的 max。

您上面的代码片段一旦 tree == None 就会失败（当节点在任何一侧都没有子节点时）。然后什么都不返回，隐式 returns None in Python.

BST 总深度并发症

BST total depth complication

python

binary-search-tree

depth