3.2.6

上次更新:2019-06-13
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

官方 BST 实现见:https://algs4.cs.princeton.edu/32bst/BST.java.html

二叉树的高度=左右子树最大高度+1,叶结点的高度为 0。
于是我们可以构造如下递归方法:

private int Height(Node x)
{
    return x == null ? -1 : 1 + Math.Max(Height(x.Left), Height(x.Right));
}

x 等于 null 时,说明它是叶子结点的左/右子树,应该返回 0-1=-1。

也可以在结点中添加一个 Height 属性,记录当前结点的高度,当插入新结点时重新计算高度。
Put 方法中添加计算高度的代码:

private Node Put(Node x, TKey key, TValue value)
{
    if (x == null)
        return new Node(key, value, 1, 0);
    int cmp = key.CompareTo(x.Key);
    if (cmp < 0)
        x.Left = Put(x.Left, key, value);
    else if (cmp > 0)
        x.Right = Put(x.Right, key, value);
    else
        x.Value = value;
    x.Size = 1 + Size(x.Left) + Size(x.Right);
    x.Height = 1 + Math.Max(Height(x.Left), Height(x.Right));
    return x;
}

由于叶结点的高度为零,因此新插入的结点高度应该初始化为 0。

上一题 下一题