3.2.47

3.2.47 #

解答 #

如下图所示，内部路径平均长度是比较符合规律的：

方差：

代码 #

一次测试：

private int Test(int n)
{
    var data = GetRandomInt(n);
    var bst = new BST<int, int>();
    foreach (var d in data)
    {
        bst.Put(d, d);
    }

    return bst.AverageInternalPathLength();
}

求解内部路径长度：

public int AverageInternalPathLength() => InternalPath() / Size() + 1;

private int InternalPath()
{
    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 库