/*
求二叉树的带权路径长度
从树根到任意结点的路径长度(所经过的边数)与该结点上权值的乘积,用全局sum变量进行累加
调用函数时,weight和sum都初始化为0,
比如 : int sum = 0;
WPL(T,0,sum);
*/
void WPL(node* T , int edges ,int &sum) {
node* p = T;
if (p) {
edges++; //计算所经过的边数
WPL(p->lchirld, edges,sum);
WPL(p->rchirld, edges,sum);
if (!p->lchirld && !p->rchirld) {//判断是否是叶子结点,若是叶子结点,则进行求和
sum += (edges - 1) * p->data; //边数乘以权值(减 1 是因为最后计算的边数多了 1 )
}
edges--; //回溯到父亲结点前,边数减1
}
}
作者:爱冲浪的awake啊
链接:https://www.jianshu.com/p/3f5539071895
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。