3.2.42

3.2.42 #

解答 #

按照题意实现即可，关键点有两个：

一是选择前驱的实现方式，只要选择左子树中的最大结点即可。

if (_random.NextDouble() < 0.5)
{
    x = Min(t.Right);
    x.Right = DeleteMin(t.Right);
    x.Left = t.Left;
}
else
{
    x = Max(t.Left);
    x.Left = DeleteMax(t.Left);
    x.Right = t.Right;
}

二是内部路径长度的计算方式，需要用层序遍历把所有结点的深度加起来。

var internalPath = 0;
var nowLayer = new Queue<Node>();
var nextLayer = new Queue<Node>();
nextLayer.Enqueue(root);

var depth = 0;
while (nextLayer.Count > 0)
{
    var temp = nowLayer;
    nowLayer = nextLayer;
    nextLayer = temp;

    while (nowLayer.Count > 0)
    {
        var node = nowLayer.Dequeue();
        if (node.Left != null)
        {
            nextLayer.Enqueue(node.Left);
        }

        if (node.Right != null)
        {
            nextLayer.Enqueue(node.Right);
        }

        internalPath += depth;
    }

    depth++;
}

return internalPath;

结果如下：

另请参阅 #

BinarySearchTree 库