3.2.30

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

解答

本题在原书后续印刷中已修改,这里仍然采用中文版的题目。

与上一题非常类似,条件有:
根结点必须在 minmax 范围内,
且左右子树要么不存在,要么小于/大于根结点的键,
左右子树同样满足上述条件。

代码

protected static bool IsOrdered(Node x, TKey min, TKey max)
{
    if (x == null)
    {
        return true;        // 空树显然是满足要求的。
    }

    return IsOrdered(x.Left, min, max) &&
           IsOrdered(x.Right, min, max) &&                        // 左右子树都满足要求。
           x.Key.CompareTo(max) <= 0 &&
           x.Key.CompareTo(min) >= 0 &&                           // 当前结点位于范围内。
           (x.Left == null || x.Left.Key.CompareTo(x.Key) < 0) &&
           (x.Right == null || x.Right.Key.CompareTo(x.Key) > 0); // 当前结点与子结点满足大小关系。
}

另请参阅

BinarySearchTree 库

上一题 下一题