Huffman3

/*
algorithm library中的sort功能之一
參考網站 https://cplusplus.com/reference/algorithm/sort/
*/
bool compare(Node* a, Node* b) {
	return a->value < b->value;
}
/*
使用遞迴紀錄每個數經Huffman的二進位
當搜到的LNode與RNode皆為NULL時，表示是輸入的資料
	使用map紀錄下來
	map參考網站 https://cplusplus.com/reference/map/map/
若LNode與RNode不是NULL時，表示需要繼續搜，分左邊與右邊搜
若是左邊，則binaryStr最後方加0，表是往左走
若是右邊，則binaryStr最後方加1，表是往右走
*/
void GenerateHuffmanBinary(Node* node, map<int, string>& HuffmanBinary, string binaryStr) {
	if (node->LNode == NULL && node->RNode == NULL) {
		HuffmanBinary[node->value] = binaryStr;
		//45 13 12 16 9 5
		// 下次過來時 int 45 對到的 string="0" 
	}
	else {
		// 100會到這 得到 binaryStr="0" 
		GenerateHuffmanBinary(node->LNode, HuffmanBinary, binaryStr + "0");
		GenerateHuffmanBinary(node->RNode, HuffmanBinary, binaryStr + "1");
	}
}
/*
猜猜我是誰
6
45 13 12 16 9 5
我叫測資
*/
int main() {
	// 輸入陣列大小 
	int size;
	cin >> size;
	/*
	symbols array表示存放測資
	deque是雙向queue 參考用法 : https://cplusplus.com/reference/deque/
	deque是宣告Node *，表示要存取多個Node結構
	*/
	int symbols[size] = { 0 };
	//雙向柱列 型態為node* 
	deque<Node*> HuffmanTree;
	Node* tmp;
	// 存放資料而已 
	for (int i = 0; i < size; i++) {
		cin >> symbols[i];
		tmp = new Node;
		tmp->value = symbols[i];
		tmp->LNode = NULL;
		tmp->RNode = NULL;
		HuffmanTree.push_back(tmp);
	}

	/*
	簡單來說就是將存取好很多Node結構依照value排序
	然後先建立一個新的Node結構，將最小兩個數字相加放到新建立的Node
	然後最小數字紀錄在新結構的LNode，第二小的紀錄在新結構的RNode
	最後砍掉最小兩個數字結構並加入新建好的結構
	之後重複動作
	*/
	for (int i = 0; i < size - 1; i++) {
		sort(HuffmanTree.begin(), HuffmanTree.end(), compare);
		//new 自行配置一個記憶體給tmp 
		tmp = new Node;
		//tmp指到的地方的value=最小的兩個相加 
		tmp->value = HuffmanTree[0]->value + HuffmanTree[1]->value;
		tmp->LNode = HuffmanTree[0];
		tmp->RNode = HuffmanTree[1];
		//移除前兩個元素 
		HuffmanTree.pop_front();
		HuffmanTree.pop_front();
		//把tmp塞到柱列裡 
		HuffmanTree.push_back(tmp);
	}
	// 從上面做完後會剩下一個，稱為root 
	// 其他都刪光光了 
	Node* root = HuffmanTree.front();

	// 將Huffman Tree轉為Binary，並記錄和印出 
	// 做出一個空的map (叫做 HuffmanBinary) 
	map<int, string> HuffmanBinary;
	GenerateHuffmanBinary(root, HuffmanBinary, "");
	for (int i = 0; i < size-1; i++) {
		cout << HuffmanBinary[symbols[i]] << " ";
	}
	cout << HuffmanBinary[symbols[size]] ;
}