计算二叉树的WPL

二叉树的WPL"/>

计算二叉树的WPL

• WPL：Weighted Path Length of Tree，带权路径长度
• 从树根到某结点经过的边数与该结点权值的乘积，称为该结点的带权路径长度
• 树中所有叶结点的带权路径长度之和称为该树的带权路径长度

算法思想

• 用一个static变量记录WPL，基于先序遍历算法，找到叶结点并将该叶结点的带权路径长度累加到WPL上。每个结点的深度作为递归函数的一个参数传递
• 传入的deep初始值为0

算法实现

//结点定义
typedef struct BiTNode{int weight;struct BiTNode* left, * right;
}BiTNode,*BiTree;int preOrderToGetWPL(BiTree T,int deep) {static int WPL = 0;if (T != NULL) {if (T->left == NULL && T->right == NULL) {WPL += (T->weight * deep);}preOrderToGetWPL(T->left, deep + 1);preOrderToGetWPL(T->right, deep + 1);}return WPL;
}//另解：后序遍历(更简洁)
int WPL = 0; //全局变量
int postOrderToGetWPL(BiTree T,int deep) {if(T==NULL) return 0;if (T->left == NULL && T->right == NULL) return WPL += (T->weight * deep);else return postOrderToGetWPL(T->left, deep + 1)+postOrderToGetWPL(T->right, deep + 1);
}