0 结果
1 题目
2 思路
二叉树的带权路径长度(WPL)的计算方法有两种:
- 1,定义:
W
P
L
=
所有叶结点的权值
W
i
∗
该结点深度
D
i
求和
WPL=所有叶结点的权值W_i*该结点深度D_i求和
WPL=所有叶结点的权值Wi∗该结点深度Di求和。
- 2,在哈夫曼树中,
W
P
L
=
所有非叶结点的权值和
WPL=所有非叶结点的权值和
WPL=所有非叶结点的权值和。
本题只能使用方法1,代码如下所示:
#include <cstdio>
#include <cstdlib>
#include <vector>
using std::vector;
typedef struct BTNode{
int weight;
struct BTNode *left, *right;
}BTNode;
int WPL = 0;
void preOrder(BTNode* p, int d){
if(p == nullptr) return;
if(p->left == nullptr && p->right == nullptr)
WPL += d*p->weight;
preOrder(p->left, d + 1);
preOrder(p->right, d + 1);
}
void ans(BTNode* root){
preOrder(root, 0);
}
int in[] = {45, 100, 12, 25, 13, 55, 5, 14, 9, 30, 16};
BTNode* Create4(vector<int> layer, int inL, int inR){
if(layer.size() == 0){
return NULL;
}
BTNode* root = new BTNode;
root->weight = layer[0];
int k;
for (k = inL; k <= inR; ++k) {
if(in[k] == root->weight){
break;
}
}
vector<int> leftLayer;
vector<int> rightLayer;
for (int i = 1; i < layer.size(); ++i) {
bool isLeft = false;
for (int j = inL; j < k; ++j) {
if(layer[i] == in[j]){
isLeft = true;
break;
}
}
if(isLeft == true){
leftLayer.push_back(layer[i]);
}else{
rightLayer.push_back(layer[i]);
}
}
root->left = Create4(leftLayer,inL, k - 1);
root->right = Create4(rightLayer,k + 1, inR);
return root;
}
int main(){
vector<int> layer;
layer.push_back(100);
layer.push_back(45);
layer.push_back(55);
layer.push_back(25);
layer.push_back(30);
layer.push_back(12);
layer.push_back(13);
layer.push_back(14);
layer.push_back(16);
layer.push_back(5);
layer.push_back(9);
BTNode * root = Create4(layer, 0, sizeof(in)/sizeof(in[0]));
ans(root);
printf("%d", WPL);
return 0;
}
例子中的二叉树如下图所示:
附录
408历年真题算法题解析
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)