10-哈夫曼编码及综合
题目描述
计算一棵二叉树的带权路径总和,即求赫夫曼树的带权路径和。
已知一棵二叉树的叶子权值,该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数,然后求总和。如下图中,叶子都用大写字母表示,权值对应为:A-7,B-6,C-2,D-3
树的带权路径和 = 71 + 62 + 23 + 33 = 34
本题二叉树的创建参考前面的方法
输入
第一行输入一个整数t,表示有t个二叉树
第二行输入一棵二叉树的先序遍历结果,空树用字符‘0’表示,注意输入全是英文字母和0,其中大写字母表示叶子
第三行先输入n表示有n个叶子,接着输入n个数据表示n个叶子的权值,权值的顺序和前面输入的大写字母顺序对应
以此类推输入下一棵二叉树
输出
输出每一棵二叉树的带权路径和
输入样例
2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20
34
40
#include<iostream>
#include<string>
using namespace std;
class btnode
{
public:
char data;
int weight;//权值
int height;//高度
btnode *lchild;
btnode *rchild;
btnode():weight(0),height(0),lchild(NULL),rchild(NULL){}
~btnode(){}
};
class bitree //二叉树
{
btnode *root;
int pos,p;
int APL;
string strtree;
btnode *createbitree(int *w,int h)
{
btnode *T;
char ch;
ch=strtree[pos++];
if(ch=='0') //空树
T=NULL;
else
{
T=new btnode();
T->data=ch;
T->height=h+1;//高度加一
if(T->data>='A'&&T->data<='Z')
T->weight=w[p++];//记录权值的数组
T->lchild=createbitree(w,T->height);
T->rchild=createbitree(w,T->height);
}
return T;
}
void preorder(btnode *t)//先序遍历
{
if(t)
{
APL += t->weight*t->height;//这个结点的路径和
preorder(t->lchild);
preorder(t->rchild);
}
}
public:
bitree(){APL=0;};
~bitree(){};
void createbitree(string treearray,int *w)
{
pos=0;
p=0;
strtree.assign(treearray);
root=createbitree(w,-1);
}
void preorder()
{
root->height=1;//根结点的高度是1
preorder(root);
cout<<APL<<endl;
}
};
int main()
{
int t,n,i;
cin>>t;
while(t--)
{
string tree;
int w[100];
bitree T;
cin>>tree>>n;
for(i=0;i<n;i++)
cin>>w[i];//n个叶子的权值
T.createbitree(tree,w);
T.preorder();//cout<<APL
}
return 0;
}