为什么我不能在 BST 上获得最短的根叶高度？

Question

我想使用Python 3.所以，我写了这样的代码。

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

class BST:
    def __init__(self):
        self.root = None

    def get(self, key):
        self.get_item(self.root, key)

    def get_item(self, n, k):
        if n == None:
            return None
        if n.key > k:
            return self.get_item(n.left, k)
        elif n.key < k:
            return self.get_item(n.right, k)
        else:
            return n.value

    def put(self, key, value):
        self.root = self.put_item(self.root, key, value)

    def put_item(self, n, key, value):
        if n == None:
            return Node(key, value)
        if n.key > key:
            n.left = self.put_item(n.left, key, value)
        elif n.key < key:
            n.right = self.put_item(n.right, key, value)
        else:
            n.value = value
        return n

    def print_height(self):
        h = self.min_height(self.root)
        print(h)

    def short_height(self, root):
        if root == None:
            return 0
        return min(self.short_height(root.left), self.short_height(root.right)) +1

if __name__ == '__main__':
    t = BST()
    t.put(60, 'a')
    t.put(50, 'b')
    t.put(70, 'c')
    t.put(20, 'd')
    t.put(10, 'e')
    t.put(45, 'f')
    t.put(35, 'g')
    t.put(25, 'h')
    t.put(40, 'i')
    t.put(30, 'j')
    t.put(80, 'z')

t.print_height

print_height 的正确结果是“3”，但我得到了错误的结果“2”。 (当我没有放node(key:80, value:z)时，正确的结果是'2'，但是这次我得到'2')

为了解决这个问题，首先，我把方法'short_height'改成了这样。（确保+1之前的代码写好）

    def short_height(self, root):
        if root == None:
            return 0
        return min(self.short_height(root.left), self.short_height(root.right)) +3

正常的话应该在height(不包括根节点)+3 2 of 80 结果是5，但是既然6出来了，我确认+1之前的代码是错的.

我不知道如何解决这个问题。

Answer 1

首先要让您的代码可运行的一些问题：

t.print_height 没有调用方法。您需要添加括号
方法 print_height 调用方法 min_height，但没有该名称的方法。我想你想打电话给 short_height

主要问题是您的算法不寻找叶，而是寻找 child 即 None。这是不一样的。以这个简单的树为例：

                  3
                 /
                1

只有一片叶子，但您的算法会找到一条从根到它的 (non-existing) 右边 child (None) 的短路径。但是这条路径不算数，因为它没有以 leaf.

结束

所以改变你的算法，让它使用 leaf 的概念作为基本情况，即一个没有 children 的节点，而不是它本身是 None.

另一个评论：显然，在您的代码挑战中，“高度”被定义为路径上的节点数。更常见的定义是计算路径上 edges 的数量。这有很大的不同。这就是为什么我在下面的解决方案中使用了术语“级别”而不是“高度”，所以要清楚计算 nodes 的数量：

    def short_levels(self):
        if self.root is None:
            return 0  # boundary case (empty tree)
        return self.short_levels_node(self.root)

    def short_levels_node(self, root):
        if not root.left and not root.right:  # It's a leaf
            return 1
        if not root.left:
            return self.short_levels_node(root.right) + 1
        if not root.right:
            return self.short_levels_node(root.left) + 1
        return min(self.short_levels_node(root.left), 
                   self.short_levels_node(root.right)) + 1

呼叫为：

print(t.short_levels())

为什么我不能在 BST 上获得最短的根叶高度？

Why I can't get the shortest root to leaf height on BST?

binary-search-tree

python-3.x