# 演算法 樹

user_6817964
c_cpp
2 years ago
1.2 kB
0
Indexable
Never
```#include <iostream>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <map>
using namespace std;

struct Node{
int value;
Node *LNode;
Node *RNode;
};

bool compare(Node *i, Node *j){
return i -> value < j -> value;
}

void search(Node *node, map<int, string> &htmap, string binary){
if (node->LNode == NULL && node->RNode == NULL){
htmap[node->value] = binary;
}
else{
search(node->LNode, htmap, binary + "0");
search(node->RNode, htmap, binary + "1");
}
}

main(){
int size;
cin >> size;

int s[size];
deque<Node *> ht;
Node *temp;

for (int i = 0; i < size; i++){
cin >> s[i];
temp = new Node;
temp->value = s[i];
temp->LNode = NULL;
temp->RNode = NULL;
ht.push_back(temp);
}

for (int i = 0; i < size-1; i++){
sort(ht.begin(), ht.end(), compare);
temp = new Node;
temp->value = ht[0]->value + ht[1]->value;
temp->LNode = ht[0];
temp->RNode = ht[1];
ht.pop_front();
ht.pop_front();
ht.push_back(temp);
}
Node *root = ht.front();

map<int, string> htmap;
search(root, htmap,"");

cout << size;
cout << "\n";
for (int i = 0; i < size-1; i++){
cout << htmap[s[i]] << " ";
}
cout << htmap[s[size-1]];
}```