imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:31Z

New page

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <math.h>
using namespace std;

typedef struct data * data_pointer;
struct data
{
string name;
int value;
vector<data> nodes;
data_pointer left_child, right_child;
};

bool comapare(data & a, data & b)
{
return a.name < b.name;
}

void init(data_pointer dp)
{
dp->left_child = dp->right_child = NULL;
}

void createABT(data_pointer dp)
{
if(dp)
{

int left_sum = 0, right_sum= 0, min_index = 0;
double min_total_weight_sum, temp;
for(int i = 1; i < dp->nodes.size(); i++)
{
right_sum +=dp->nodes[i].value;
}

min_total_weight_sum = right_sum*sqrt(dp->nodes.size()-1);
for(i = 1; i < dp->nodes.size(); i++)
{
left_sum += dp->nodes[i-1].value;
right_sum -= dp->nodes[i].value;
temp = left_sum*sqrt(i-1) + right_sum*sqrt(dp->nodes.size() - i - 1);
if(temp < min_total_weight_sum)
{
min_total_weight_sum = temp;
min_index = i;
}
}
dp->name = dp->nodes[min_index].name;
dp->value = dp->nodes[min_index].value;
// 왼쪽 자식이 있을때
if(min_index != 0)
{
dp->left_child = new data;
init(dp->left_child);
for(int i = 0; i < min_index; i++)
dp->left_child->nodes.push_back(dp->nodes[i]);
createABT(dp->left_child);
}

// 오른쪽 자식이 있을때
if(min_index != dp->nodes.size()-1)
{
dp->right_child = new data;
init(dp->right_child);
for(int i = min_index +1; i < dp->nodes.size(); i++)
dp->right_child->nodes.push_back(dp->nodes[i]);
createABT(dp->right_child);
}
dp->nodes.clear();
}
}

void show(data_pointer dp)
{
if(dp)
{
show(dp->left_child);
cout << dp->name << " ";
show(dp->right_child);
}
}

int cost(data_pointer dp, int level)
{
if(dp)
{
return cost(dp->left_child, level + 1) + cost(dp->right_child, level + 1) + dp->value * level;
}
return 0;
}

int main()
{
int nodeNum, value;
data temp;
string name;
data_pointer root = new data;
init(root);
cin >> nodeNum;
for(int i = 0; i < nodeNum; i++)
{
cin >> name >> value;
temp.name = name;
temp.value = value;
root->nodes.push_back(temp);
}
sort(root->nodes.begin(),root->nodes.end(),comapare);
createABT(root);
show(root);
cout << endl;
cout << cost(root,1) << endl;
return 0;
}

AproximateBinaryTree/김상섭 - Revision history

imported>Unknown at 05:22, 7 February 2021