3.2.13

3.2.13 #

解答 #

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

Get 方法可以很方便的改成非递归形式。

private TValue Get(Node x, TKey key)
{
    if (key == null) throw new ArgumentNullException(nameof(key), "calls get() with a null key");
    var cur = x;
    while (cur != null)
    {
        var cmp = key.CompareTo(cur.Key);
        if (cmp < 0)
            cur = cur.Left;
        else if (cmp > 0)
            cur = cur.Right;
        else
            return cur.Value;
    }

    return default;
}

Put 方法结构类似，但需要注意更新路径上各个结点的 Size 属性。

private Node Put(Node x, TKey key, TValue value)
{
    if (x == null)
        return new Node(key, value, 1);

    var path = new Stack<Node>();
    var cur = x;
    while (cur != null)
    {
        path.Push(cur); 
        var cmp = key.CompareTo(cur.Key);
        if (cmp < 0)
            cur = cur.Left;
        else if (cmp > 0)
            cur = cur.Right;
        else
        {
            cur.Value = value;
            return x;
        }
    }

    var parent = path.Peek();
    var node = new Node(key, value, 1);
    if (parent.Key.CompareTo(key) > 0)
        parent.Left = node;
    else
        parent.Right = node;

    while (path.Count > 0)
        path.Pop().Size++;
        
    return x;
}

Keys 方法中，可以用新建一个栈来代替递归栈记录路径。

private static void Keys(Node x, Queue<TKey> queue, TKey lo, TKey hi)
{
    var stack = new Stack<Node>();

    while (x != null || stack.Count > 0)
    {
        if (x != null)
        {
            var cmpLo = lo.CompareTo(x.Key);
            var cmpHi = hi.CompareTo(x.Key);
            if (cmpHi >= 0)
                stack.Push(x);
            if (cmpLo < 0)
                x = x.Left;
            else
                x = null;
        }
        else
        {
            x = stack.Pop();
            var cmpLo = lo.CompareTo(x.Key);
            var cmpHi = hi.CompareTo(x.Key);
            if (cmpLo <= 0 && cmpHi >= 0)
                queue.Enqueue(x.Key);
            x = x.Right;
        }
    }
}

另请参阅 #

BinarySearchTree 库