题目描述

 二叉树的带权路径长度WPL是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树，采用二叉链表存储，叶子结点的weight域为该结点的权值。请设计一个算法，求二叉树的带权路径长度。

算法思想

可以使用先序遍历或层次遍历解决问题。
<1>算法思想一：基于先序递归遍历。
用一个static变量记录WPL，把每个结点的深度作为递归函数的一个参数传递。

• 若该结点是叶结点，则变量WPL加上该结点的深度与权值之和。
• 若该结点是非叶结点，则左子树不为空时，对左子树调用递归算法，右子树不为空时，对右子树调用递归算法，深度参数均为本结点的深度参数加1。

<2>算法思想二：基于层序遍历。
使用队列进行层次遍历，并记录当前的层数。

• 当遍历到叶结点时，累计WPL。
• 当遍历到非叶结点时，把该结点的子树加入队列。
• 当某结点为该层最后一个结点时，层数自增1。
• 队列空时遍历结束，返回WPL。

实现代码

<1> 算法一的函数代码实现：

int WPL_PreOrder(BTree root, int deep){
    static int wpl = 0;
    if(root->lchild==NULL && root->rchild==NULL){ //若为叶结点，累积
        wpl += deep*root->weight;
    }
    if(root->lchild != NULL){  //若左子树不空，对左子树递归遍历
        WPL_PreOrder(root->lchild, deep+1);
    }
    if(root->rchild != NULL){  //若右子树不空，对右子树递归遍历
        WPL_PreOrder(root->rchild, deep+1);
    }
    return wpl;
}

<2>算法二的函数代码实现：

int WPL_Level(BTree root){
    queue<BNode *> treenode; //队列
    int wpl = 0;
    int deep = 0;  //初始化深度
    BNode *lastNode; //记录当前最后一个结点
    BNode *newlastNode; //记录下一层最后一个结点
    lastNode = root;  //初始化为根结点
    newlastNode = NULL;  //初始化为空
    treenode.push(root); //根结点入队
    while(!treenode.empty()){ //栈不空时循环
        BNode *top = treenode.front(); //取出队首元素
        treenode.pop();
        if(top->lchild==NULL && top->rchild==NULL){
            wpl += deep*top->weight;
        }//若为叶结点，累加
        if(top->lchild != NULL){ //若为非叶结点则把左孩子结点入队
            treenode.push(top->lchild);
            newlastNode = top->lchild; //设置下一层最后一个结点
        }
        if(top->rchild != NULL){  //右孩子结点入队
            treenode.push(top->rchild);
            newlastNode = top->rchild;
        }
        if(top == lastNode){  //若该结点为本层最后一个结点
            lastNode = newlastNode;  //更新
            deep+=1; //深度加1
        }
    }
    return wpl;
}

二叉树计算带权路径长度（WPL）的算法

更多内容请访问点击我的主页

题目 :

二叉树的带权路径长度是二叉树中所有叶子结点的带权路径长度之和。给定二叉链表的存储的结点结构为

left	weight	right

weight存储的是叶子结点的非负权值。设计算法求二叉树的带权路径长度WPL。

WPL = ∑ 叶子结点的权值 × 结点到根结点的分支个数 ¹

例如：

非递归算法

1. 算法思想：根据公式，需要记录每个结点到根结点的分支个数，这个过程通过对树进行广度遍历（借助队列）进行记录。
   在非叶子结点weight初值为-1，叶子结点初值设为非负权值。
   最后对队列进行逐个访问，如果weight != -1，那就计算该点。

wpl += (Q[i].p->weigth) * (Q[i].p->lno - 1);  //WPL公式代码

这里改造队列的结点结构

typedef struct
{
	LBTree* p;   //树的结点
	int lno;     //结点深度
}Queue;

2. 伪代码

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;
}

递归算法 （推荐）

1. 算法描述：本算法采用的是统计叶子结点算法基础上改造而来的。只是在参数列表定义了结点到根的分支个数。进行一个递归计算。统计结点数在个人主页有相关算法。
2. 代码如下：

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;
}

计算Huffman树的带权路径长度WPL

编程背景

Huffman编码是通信系统中常用的一种不等长编码，它的特点是：能够使编码之后的电文长度最短。

• 输入：第一行为要编码的符号数量n，第二行～第n+1行为每个符号出现的频率
• 输出：对应哈夫曼树的带权路径长度WPL
• 测试用例举例：
  

思路

因为要完成对应的输入输出，我首先想到的就是通过最简单的一维数组的方式。因为本题只要求计算WPL，观察其输入输出，故我并没有考虑使用链表。

借鉴

通过网站上浏览资料，发现一个好技巧：
WPL 为所有叶节点的带权路径长度之和，同时也是所有非叶子结点的权值之和。
详细解释见：哈夫曼树的WPL值的计算

程序实现

m函数：返回一维数组S中最小的数，并将其从数组中剔出

int m(){
    int min, position=0;
    min = S[0];
    int i=0;
    for(i=0; i<len; i++){
        if(min > S[i]){
            min = S[i];
            position = i;
        }
    }
    for(i=position; i<len-1;i++) S[i] = S[i+1];
    S[(len--)-1]=0;
    return min;
}

main函数

int main(){    
	int n; int i, temp;
	scanf("%d", &n);
	len = n;
	for(i=0; i<n; i++) scanf("\n%d", &S[i]);
	while(len>1){
		temp = m() + m();
		WPL += temp;
		S[len++] = temp;
	}
    	printf("WPL=%d\n",WPL);
    	return 0;
}

后记

• 作为一个步入C殿堂不久的小白，如今开始在CSDN上记录自己的学习到的一些零碎。
• 前人栽树，后人乘凉。我也要努力成为一个前人！不做一个只会伸手的懒虫！
• 欢迎大家指出我的不足！【作揖】