DS树+图综合练习--带权路径和

题目描述

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

已知一棵二叉树的叶子权值，该二叉树的带权案路径和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个叶子的权值，权值的顺序和前面输入的大写字母顺序对应

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

输出

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

样例输入

2

xA00tB00zC00D00

4 7 6 2 3

ab0C00D00

2 10 20

样例输出

34

40

 

 原理很简单，在树节点中添加两个属性 weight 和 hight 用来记录每个节点的权值和高度，如果不是叶子节点权值就为0。如果当前节点是大写字母则给它赋值相应的权值，递归创建树的时候每次传入父节点的高度，子节点的高度等于父节点高度加一就可以得到每个节点的高度了，这些都是在创建树的时候就完成的工作，而计算APL是使用先序遍历 把输出改成APL+=t->weight*t->high 最后输出APL即可

#include<iostream>

#include<string>

using namespace std;

class BitreeNode

{

public:

    char data;

    int weight;

    int hight;

    BitreeNode *left;

    BitreeNode *right;

    BitreeNode() :hight(),weight(),left(NULL), right(NULL) {}

    ~BitreeNode() {}

};

class Bitree

{

private:

    BitreeNode *Root;

    int pos,po;

    int APL;

    string strtree;

    BitreeNode *CreateBitree(int w[],int fatherhigh);

    void preorder(BitreeNode *t);

public:

    Bitree() { APL = ; };

    ~Bitree() {};

    void CreateTree(string TreeArray,int w[]);

    void preorder();

};

void Bitree::CreateTree(string treearray,int w[])

{

    pos = ;

    po = ;

    strtree.assign(treearray);

    Root = CreateBitree(w,-);

}

BitreeNode *Bitree::CreateBitree(int w[],int fatherhigh)

{

    BitreeNode *T;

    char ch;

    ch = strtree[pos++];

    if (ch == '')

        T = NULL;

    else

    {

        T = new BitreeNode();

        T->data = ch;

        T->hight = fatherhigh + ;

        if (T->data >= 'A'&&T->data <= 'Z')

            T->weight = w[po++];

        T->left = CreateBitree(w,T->hight);

        T->right = CreateBitree(w,T->hight);

    }

    return T;

}

void Bitree::preorder()

{

    Root->hight = ;

    preorder(Root);

    cout << APL << endl;

}

void Bitree::preorder(BitreeNode *t)

{

    if (t)

    {

        //cout << t->data << "-" << t->weight << "-" << t->hight << endl;

        APL = APL + t->weight*t->hight;

        preorder(t->left);

        preorder(t->right);

    }

}

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        string str;

        cin >> str;

        Bitree *tree;

        int n,*w;

        cin >> n;

        w = new int[n];

        for (int i = ; i < n; i++)

            cin >> w[i];

        tree = new Bitree();

        tree->CreateTree(str,w);

        tree->preorder();

    }

}