最优二叉树、赫尔曼树（学习记录）
#include<vector>
#include<iostream>
#include<string>
#include<set>
using namespace std;
struct node {
string data;
int w;//权值或概率
string ma;
node *l, *r;
int flag;
node() { l = r = NULL;ma = "";flag = 0; }
bool operator<(const node b) const {
return w < ;
}
};
multiset<node> all;
vector<node> resault;//最终的所有节点
int N;
void dfs(node *&root)//赫尔曼编码
{
if (root->l) {
root->l->ma = root->ma + "0";dfs(root->l);
}
if (root->r) {
root->r->ma = root->ma + "1";dfs(root->r);
}
}
int main()
{
int cnt = 0;
cout << "请输入节点的个数" << endl;
cin >> N;
(2 * N - 1);
cout<<"请依次输入各节点的名字和权值"<<endl;
while (N--)
{
node tem;
cin >> >> ;
= 1;
(tem);
}
while (() != 1)//选2个最小的到resault中，并创建一个最小合并的节点到all
{
node tem;
auto it2 = (), it = ();
it2++;
resault[cnt++] = *it;
resault[cnt++] = *it2;
= &resault[cnt - 2]; = &resault[cnt - 1];
= "(" + ->data + "+" + ->data + ")";
= ->w + ->w;
it2++;
(it, it2);
(tem);
/*for (auto x : all)
cout << << " ";
cout << endl;*/
}
resault[cnt++] = *();
//遍历，求所求//比如赫尔曼码
node *root = &resault[() - 1];
dfs(root);
for (auto x : resault)
if ( == 1) cout << << " " << << endl;
}