什么叫二叉树平均深度？

1.平均深度应该是对于所有叶结点的平均，所以应该把所有叶结点的深度相加然后除以叶结点数量
2.复杂度的确O(n)，因为每个叶结点只算了一次

(ab+cd)/(a+c)!=(b+d)/2所以你的算法是错的

那能给出个算法吗?
谢谢了

如果像二楼所说的

那你只要求出所有叶节点的深度之和，除以叶节点之和不就是答案了。

这就是答案。至于怎么遍历一棵树，你应该看书才对。

以下delphi程序测试通过，c程序由delphi改写，未测试

float HeightTotal(float *le;float Ceng;Bitre T);
{
  if (T==null) 
    return(0);
  else
  {  Ceng+=1;
    if (T->lchild==null)&&(T->rchild==null) then
    {
      le+=1;
      return(HeightTotal(le,Ceng,null)+ceng);
    }
    else 
      return(HeightTotal(le,Ceng,T^.lchild)+HeightTotal(le,Ceng,T^.rchild));
  }
}

//二叉树平均高度
float AverTree(Bitre T);
{
  float le,Ceng;
  le=0;ceng=0;
  //Ceng是当前层数，le是叶子数，HeightTotal返回所有叶子高度和
  return(HeightTotal(le,Ceng,T)/le);
}



//二叉树平均高度
function TForm1.AverTree(T: bitreptr): Extended;
  function HeightTotal(var le:Extended;Ceng:Extended;T:bitreptr):Extended;
  begin
    if T=nil then
      HeightTotal:=0
    else begin
      Ceng:=Ceng+1;
      if (T^.lchild=nil) and (T^.rchild=nil) then
      begin
        le:=le+1;
        HeightTotal:=HeightTotal(le,Ceng,nil)+ceng;
      end
      else begin
        HeightTotal:=HeightTotal(le,Ceng,T^.lchild)+HeightTotal(le,Ceng,T^.rchild);
      end;
    end;
  end;
var
  le,Ceng:Extended;
begin
  le:=0;ceng:=0;
  //Ceng是当前层数，le是叶子数，HeightTotal返回所有叶子高度和
  AverTree:=HeightTotal(le,Ceng,T)/le;
end;