演算法 樹

 avatar
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]];
}