二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构如下：

left

weight

right

        其中叶结点的weight域保存该结点的非负权值 。设root为指向T的根结点的指针，请设计求T的WPL的算法。要求：

        （1）给出算法的基本思想。

算法的基本思想如下：
    采用先序遍历的思想，引用传递参数wpl来记录树的WPL，参数deep用于记录树的每个结点深度，递归实现。
具体步骤如下：
    （1）如果当前结点为空，返回。
    （2）如果当前结点是叶子结点，那么wpl加上此结点的权值与深度乘积。
    （3）递归调用左子树，递归调用右子树。

        （2）使用C或C++语言，给出二叉树结点的数据类型定义。

typedef struct BiTNode
{
	int weight;
	BiTNode* left;
	BiTNode* right;
}BiTNode, * BiTree;

        （3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

void WPL(BiTree root, int& wpl)
{
	wpl = 0;//防止wpl未初始化为0
	WPLPreOrder(root, 0, wpl);//deep初始值为0
}

void WPLPreOrder(BiTree root, int deep, int& wpl)
{
	if (root == NULL)//结点为空，返回
		return;
	else if (root->left == NULL && root->right == NULL)//如果root为叶结点，更新wpl值
		wpl += root->weight * deep;
	else
	{
		WPLPreOrder(root->left, deep + 1, wpl);//递归求左子树
		WPLPreOrder(root->right, deep + 1, wpl);//递归求右子树
	}
}

给出一个完整测试代码如下(可运行)：

#include<iostream>
using namespace std;

typedef struct BiTNode
{
	int weight;
	BiTNode* left;
	BiTNode* right;
}BiTNode, * BiTree;

//输入先序序列创建二叉树
void createBT(BiTree& T)
{
	int weight;
	cin >> weight;//本例中非叶结点输入0吧(反正也用不到)
	if (weight == -1)//-1代表结点为空
		T = NULL;
	else
	{
		T = new BiTNode;
		T->weight = weight;
		createBT(T->left);
		createBT(T->right);
	}
}
//销毁二叉树
void deleteBT(BiTree& T)
{
	if (T)
	{
		deleteBT(T->left);
		deleteBT(T->right);
		delete T;
	}
}

void WPLPreOrder(BiTree root, int deep, int& wpl)
{
	if (root == NULL)//结点为空，返回
		return;
	else if (root->left == NULL && root->right == NULL)//如果root为叶结点，更新wpl值
		wpl += root->weight * deep;
	else
	{
		WPLPreOrder(root->left, deep + 1, wpl);//递归求左子树
		WPLPreOrder(root->right, deep + 1, wpl);//递归求右子树
	}
}
void WPL(BiTree root, int& wpl)
{
	wpl = 0;//防止wpl未初始化为0
	WPLPreOrder(root, 0, wpl);//deep初始值为0
}

int main()
{
	BiTree T;
	cout << "按先序序列创建二叉树：" << endl;
	//测试输入，这棵树很容易画出来，0代表非叶结点，-1代表孩子为空
	//0 0 0 5 -1 -1 -1 7 -1 -1 0 13 -1 -1 9 -1 -1 -1
	createBT(T);
	cout << endl;

	int wpl = 0;
	WPL(T, wpl);
	cout << "该二叉树的WPL为：" << wpl << endl;

	deleteBT(T);
	return 0;
}

运行结果：