题目描述
计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。
已知一棵二叉树的叶子权值，该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3
树的带权路径和 = 7*1 6*2 2*3 3*3 = 34
本题二叉树的创建参考前面的方法
输入
第一行输入一个整数t，表示有t个二叉树
第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子
第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应
以此类推输入下一棵二叉树
输出
输出每一棵二叉树的带权路径和
输入样例1
2 xA00tB00zC00D00 4 7 6 2 3 ab0C00D00 2 10 20
输出样例1
34 40
思路分析
实际上要解决两个问题？
一个是求树节点的深度，即根节点到叶子的分支数，一个是知道哪个是叶子节点，对于哪个权重。
求节点的深度可以在递归建树的时候搞定，孩子的深度（如果有孩子的话）必定比自己多一，见代码，一目了然。
先序遍历树，左右孩子都是空的说明这个是叶子节点，读取权重进来，乘以叶子节点深度，累加即可。
AC代码
代码语言：javascript复制#include <iostream>
#include <string>
using namespace std;
class BiTreeNode {
public:
char data; //数据域
int depth=0;
BiTreeNode *leftChild, *rightChild; //左右子树指针
BiTreeNode():leftChild(NULL), rightChild(NULL){}
~BiTreeNode() {}
};
class BiTree {
private:
BiTreeNode *root; //根结点指针
string sTree; //建树字符串
int pos; //标识建树字符串的当前字符位置
BiTreeNode * CreateTree(int depth=0);//建树私有函数
public:
int sum=0;
BiTree():root(NULL) {};
void Create(string vArray); //建树公有接口，参数是特定的先序遍历字符串
void Sum(BiTreeNode*T){
if(T){
if(!T->leftChild&&!T->rightChild){
int weight;
cin>>weight;
sum =weight*T->depth;
}
Sum(T->leftChild);
Sum(T->rightChild);
}
}
void Show(){
int n;
cin>>n;
Sum(root);
cout<<sum<<endl;
}
};
void BiTree::Create(string vArray)
{ pos=0;
sTree.assign(vArray); //把参数保存到内部字符串
root = CreateTree(); //建树成功后root指向根结点
}
BiTreeNode* BiTree::CreateTree(int depth) {
if(pos==sTree.size()||sTree[pos]=='0'){
pos ;
return NULL;
}
BiTreeNode*T=new BiTreeNode();
T->depth=depth;
T->data=sTree[pos ];
T->leftChild=CreateTree(depth 1);
T->rightChild=CreateTree(depth 1);
return T;
}
int main()
{ int t;
string temp;
cin>>t;
while(t--)
{ cin >> temp;
BiTree tree;
tree.Create(temp);
tree.Show();
}
return 0;
}
