问题提出
已知一棵二叉排序树，如何计算其ASL？

问题分析
ASL的定义在这里不再赘述，在这里其计算方法就是：第一层元素个数 *1 + 第二层元素个数 *2 + 第三层元素个数 *3+……+第n层元素个数 *n 。是不是看到这里已经有了一些熟悉的感觉，对，就是用到了二叉树的 层次遍历，然而既然是每层的元素个数乘以第几层，那么是要将层次遍历中的每一层分开的。这就是这个问题的重点。关于如何分层，笔者可以提供两个思路：

（1）层次遍历是要用到队列的，每层入队列的时候，可以将每层的开始和结尾做标记start和end，出队列出到end的时候，就是下一层开始了，就可以求出所有层的元素个数。这种分层方法在所有的二叉树中都可以使用；
（2）但是对于二叉排序树，根据其特点，每层都是从小到大的顺序排列，并且下一层的第一个一定比这一层的最后一个要小，所以，这个特点也可以作为分层依据。在层次遍历的同时，设一个max变量，如果值比max大，那么把该值赋值给max然后接着遍历，只要值比max小，就是新的一层，把该值赋给max之后开始新的计数。在本篇中笔者给出的是这个思路的代码。

解决问题（思路二代码）

void BSTS_ASL(BinSearTree *bt)     //层次遍历分层 并计算ASL
{
    BSTreeNode p;
    int tempwidth=0,width[10],i=0;
    int max,len;
    float count=0;

    printf("层次遍历结果: ");
    LinkQueue queue=SetNullLinkQueue();

    if(*bt==NULL)
        return;
    p=*bt;
    EnterLinkQueue(queue,p);
    max=p->data;
    while(!IsNullLinkQueue(queue))
    {
        p=FrontLinkQueueReturn(queue);
        ExitLinkQueue(queue);
        tempwidth++;    //某层宽度加1

        printf("%d ",p->data);
        count++;   //元素个数

        if(p->data<=max)             //到达该层最后一个
        {
            width[i]=tempwidth;   //数组记录每层宽度
            i++;
            tempwidth=0;  //换层 宽度置0
        }
        max=p->data;

        if(p->leftchild!=NULL)
        {
            EnterLinkQueue(queue,p->leftchild);
        }

        if(p->rightchild!=NULL)
        {
            EnterLinkQueue(queue,p->rightchild);
        }

    }
    tempwidth++;
    width[i]=tempwidth;
    len=i;

    printf("\n各层含有的元素个数为 ");   //输出ASL公式及结果
    for(i=1;i<=len;i++)
    {
        printf("%d ",width[i]);
    }

    float sum=0;
    printf("\nASL= \(");
    for(i=1;i<=len;i++)
    {
        printf("%d*%d+",i,width[i]);
        sum+=i*width[i];
    }
    printf(")/%.0f = %.2f\n",count,sum*1.0/count);
}