【数据结构】求二叉树的带权路径长度

/*
    求二叉树的带权路径长度
    从树根到任意结点的路径长度(所经过的边数)与该结点上权值的乘积,用全局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
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
上一篇:图的邻接矩阵和深度优先遍历


下一篇:Python学习整理记录之OPP面向对象(类)