3.2.25

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

解答

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

先排序,然后视其为中序序列,每次取中间的键作为根结点,左半数组是左子树,右半数组是右子树,递归构造。

private Node BuildTree(KeyValuePair<TKey, TValue>[] init, int lo, int hi)// init is sorted
{
    if (lo > hi)
    {
        return null;
    }

    var mid = (hi - lo) / 2 + lo;
    var current = new Node(init[mid].Key, init[mid].Value, 1);
    current.Left = BuildTree(init, lo, mid - 1);
    current.Right = BuildTree(init, mid + 1, hi);
    if (current.Left != null)
    {
        current.Size += current.Left.Size;
    }

    if (current.Right != null)
    {
        current.Size += current.Right.Size;
    }
    return current;
}

另请参阅

BinarySearchTree 库

上一题 下一题