3.2.14 #
解答 #
就 min，max 和 select 而言，它们是尾递归的，可以直接转换成迭代形式。
（简单的说，尾递归就是所有递归操作都出现在 return 语句上，且返回值不需要参与其他运算）
例如 min，递归形式为：
if (x.Left == null)
return x;
return Min(x.Left);
递归调用获得的值直接返回，不再参与运算，可以直接转换为递推：
while (true)
{
if (x.Left == null) return x;
x = x.Left;
}
ceiling 和 floor 会略微复杂一些，具体见代码。
代码 #
min 和 max 比较简单，用一个 while 循环就可以转换为递推形式，例如 min。
while (x != null)
{
if (x.Left == null) return x;
x = x.Left;
}
return x;
floor 和 ceiling 则要稍微复杂一点，需要记录当前找到的最小/最大值，例如 floor。
Node floor = null;
while (x != null)
{
var cmp = key.CompareTo(x.Key);
if (cmp == 0)
{
return x;
}
if (cmp < 0)
{
x = x.Left;
}
else
{
floor = x;
x = x.Right;
}
}
return floor;
rank 和它们类似，需要用一个变量记录当前排名。
var rank = 0;
while (x != null)
{
var cmp = key.CompareTo(x.Key);
if (cmp < 0)
{
x = x.Left;
}
else if (cmp > 0)
{
rank += 1 + Size(x.Left);
x = x.Right;
}
else
{
rank += Size(x.Left);
return rank;
}
}
return rank;
select 比较简单，不需要维护变量。
while (x != null)
{
var t = Size(x.Left);
if (t > k)
{
x = x.Left;
}
else if (t < k)
{
x = x.Right;
k = k - t - 1;
}
else
{
return x;
}
}
return null;