7-3 C. DS树--带权路径和

题目描述

二叉树的创建使用含空树表示的先序遍历序列，计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。

已知一棵二叉树的叶子权值，该二叉树的带权路径和WPL等于叶子权值乘于根节点到叶子的分支数，然后求总和。

如下图中，叶子都用大写字母表示，权值对应为：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个叶子的权值，权值的顺序和前面输入的大写字母顺序对应

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

输入样例：

2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20

输出

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

输出样例：

34
40

代码

#include <iostream>
using namespace std;

struct Node{
    char data;
    int weight;
    int height;
    Node *left;
    Node *right;
};

class HuffmanTree{
public:
    Node *root;
    int sum=0;
    void create(Node *&t,int height){  //建树 + 求每个结点的高度
        char c;
        cin >> c;
        if(c == '0'){
            t = NULL;
        }else{
            t= new Node;
            t->data = c;
            t->height = height;
            create(t->left,height+1);
            create(t->right,height+1);
        }
    }

    void getWeight(Node *t){  //匹配权重
        if(t == NULL){
            return;
        }else{
            if(t->data >= 'A' && t->data <= 'Z'){
                int num;
                cin >> num;
                t->weight = num;
            }
        }
        getWeight(t->left);
        getWeight(t->right);
    }

    void comb(Node *t){  //计算带权路径和
        if(t == NULL){
            return;
        }else{
            if(t->data >= 'A' && t->data <= 'Z'){
                sum += t->height * t->weight;
            }
            comb(t->left);
            comb(t->right);
        }
    }
};

int main()
{
    int t;
    cin >> t;
    while(t--){
        HuffmanTree tree;
        tree.create(tree.root,0);
        int k;
        cin >> k;
        tree.getWeight(tree.root);
        tree.comb(tree.root);
        cout << tree.sum << endl;
    }
    return 0;
}