E (1052) : DS树--带权路径和

一、题目描述

计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。

已知一棵二叉树的叶子权值，该二叉树的带权路径和APL等于叶子权值乘以根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3

树的带权路径和 = 7 * 1 + 6 * 2 + 2 * 3 + 3 * 3 = 34

二、输入与输出

1.输入

第一行输入一个整数t，表示有t个二叉树

第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子

第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应

以此类推输入下一棵二叉树

2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20

2.输出

输出每一棵二叉树的带权路径和

34
40

三、参考代码

#include<iostream>
#include<string>
using namespace std;

class TreeNode
{
public:
	char data;
	int w;
	int h;
	TreeNode* lchild;
	TreeNode* rchild;
	TreeNode() { w = 0; h = 0; lchild = NULL; rchild = NULL; }
	~TreeNode(){}
};

class Tree
{
	TreeNode* root;
	int pos, index;
	int sum;
	string str;
	
public:
	Tree() { sum = 0; }
	~Tree() {}
	TreeNode* CreatTree(int* arr, int h)
	{
		TreeNode* r;
		char ch;
		ch = str[pos++];
		if (ch == '0')
		{
			r = NULL;
		}
		else
		{
			r = new TreeNode();
			r->data = ch;
			r->h = h + 1;
			if (r->data >= 'A' && r->data <= 'Z')
			{
				r->w = arr[index++];
			}
			r->lchild = CreatTree(arr, r->h);
			r->rchild = CreatTree(arr, r->h);
		}
		return r;
	}
	void pre(TreeNode* r)
	{
		if (r)
		{
			sum += r->w * r->h;
			pre(r->lchild);
			pre(r->rchild);
		}
	}
	void CreatTree(string s, int* arr)
	{
		pos = 0;
		index = 0;
		str.assign(s);
		root = CreatTree(arr, -1);
	}
	void pri()
	{
		root->h = 1;
		pre(root);
		cout << sum << endl;
	}
};

int main() {
	int sum;
	string s;
	int ss;
	cin >> sum;
	while (sum--)
	{
		cin >> s;
		cin >> ss;
		int arr [100];
		for (int i = 0; i < ss; i++)
		{
			cin >> arr[i];
		}
		Tree r;
		r.CreatTree(s, arr);
		r.pri();

	}
	return 0;
}



/**********************************************************************
	Problem: 1052
	Language: C++
	Result: AC
	Time:14 ms
	Memory:2232 kb
**********************************************************************/