3.2.7 #
解答 #
平均查找次数 = 树所有结点的深度之和 / 结点个数 + 1。
只要能够获得深度和，就能构造出如下用于计算平均查找次数的方法：
public int AverageCompares()
{
return DepthSum(_root) / Size() + 1;
}
二叉树的深度之和 = 左子树的深度和 + 右子树的深度和 + 左子树的结点个数 + 右子树的结点个数 （加上根结点会使左右子树所有结点的深度+1）
于是我们可以获得如下递归方法，用于计算一棵树的深度和：
private int DepthSum(Node x)
{
if (x == null)
return 0;
return DepthSum(x.Left) + DepthSum(x.Right) + x.Size - 1;
}
也可以在结点中直接添加一个 DepthSum 属性，用于记录当前结点的深度和。
需要在每次插入新结点时重新计算查找路径上所有结点的 DepthSum。
private Node Put(Node x, TKey key, TValue value, int depth)
{
if (x == null)
return new Node(key, value, 1, depth);
var cmp = key.CompareTo(x.Key);
if (cmp < 0)
x.Left = Put(x.Left, key, value, depth + 1);
else if (cmp > 0)
x.Right = Put(x.Right, key, value, depth + 1);
else
x.Value = value;
x.Size = 1 + Size(x.Left) + Size(x.Right);
x.DepthSum = depth;
if (x.Left != null)
x.DepthSum += x.Left.DepthSum;
if (x.Right != null)
x.DepthSum += x.Right.DepthSum;
return x;
}
在插入结点时需要传入一个参数以记录当前深度，新插入结点的默认深度和就是当前深度。