3.2.13

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

解答

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

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

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;
}

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

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++;

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

while (x != null || stack.Count > 0)
{
    if (x != null)
    {
        stack.Push(x);
        x = x.Left;
    }
    else
    {
        x = stack.Pop();
        queue.Enqueue(x.Key);
        x = x.Right;
    }
}

另请参阅

BinarySearchTree 库

上一题 下一题