wpl计算方法_C++二叉树计算带权路径长度（WPL）的算法
二叉树的带权路径长度等于其所有终端节点（leaf nodes）到根节点的距离与其权重的乘积之总和。给定二叉链表所采用的数据结构及其结点存储格式如下
left | weight| right
存储的是叶子结点的非负权值。设计算法求二叉树的带权路径长度WPL。
WPL = ∑ 叶子结点的权值 × 结点到根结点的分支个数
例如：
非递归算法的算法思想：按照公式必须记录每个节点到根节点之间的分支数量。这一过程可通过使用广度优先搜索（借助队列）来完成。
在非叶子结点weight初值为-1，叶子结点初值设为非负权值。
最后对队列进行逐个访问，如果weight != -1，那就计算该点。
wpl += (Q[i].p->weigth) * (Q[i].p->lno - 1); //WPL公式代码
这里改造队列的结点结构
typedef struct {
LBTree* p; //树的结点
int lno; //结点深度
}Queue;
伪代码
typedef struct
{
LBTree* p;
int lno;
}Queue;
int WPL(LBTree* lbt)
{
Queue Q[maxSize];
int front,rear;
front = rear = 0;
int Lno = 1;
LBTree* q = lbt;
Q[rear].p = q;
Q[rear].lno = Lno;
rear++;
while (front != rear)
{
q = Q[front].p;
Lno = Q[front].lno;
front++;
if (q->lchild != NULL)
{
Q[rear].p = q->lchild;
Q[rear].lno = Lno + 1;
rear++;
}
if (q->rchild != NULL)
{
Q[rear].p = q->rchild;
Q[rear].lno = Lno + 1;
rear++;
}
}
int wpl = 0;
for (int i = 0; i < rear; i++)
{
if (Q[i].p->weigth != -1)
wpl += (Q[i].p->weigth) * (Q[i].p->lno - 1);
}
return wpl;
}
递归算法 (推荐)
算法描述：该算法基于统计叶子结点的方法进行了改造。其参数列表中明确了节点到根节点分支的数量，并通过递归的方式完成计算过程。代码如下：
int WPLrec(LBTree* lbt,int n)
{
int wpl = 0;
if (lbt != NULL)
{
if (lbt->lchild == NULL && lbt->rchild == NULL)
wpl += n * lbt->weigth;
wpl += WPLrec(lbt->lchild, n + 1);
wpl += WPLrec(lbt->rchild, n + 1);
}
return wpl;
}