网站开发的目的实习报告必应站长平台

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

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

思想：使用先序遍历递归的方式实现。使用一个变量len，初始值为0，每向下遍历一层，len加1.如果当前结点是叶子结点的话，那么就计算（len-1）*weight，并加入到总权值中。

代码：

typedef struct BiTNode{ElemType data;struct BiTNode *left，*right;
}BiTNode, *BiTree;void TWPL(BiTree root,int len,int &wpl){if(root == NULL) return;//树空 len++;if(root->left==NULL && root->right==NULL){//叶结点 wpl += (len-1)*root->weight;}else{//递归处理左右子树 wpl(root->left,len,wpl);wpl(root->right,len,wpl);}
}
int WPL(BiTree root){int wpl=0;TWP(root,0,wpl);return wpl;
}