【数据结构与算法】二叉树——哈夫曼编码

#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
struct TreeNode {//树节点的构造
	int val;
	char ch;
	struct TreeNode *left, *right;
	TreeNode(int v, char c) :val(v), ch(c), left(NULL), right(NULL) {}
};
struct Node {//链节点的构造
	TreeNode tree;//树节点
	struct Node *next;
	Node(int v,char c):tree(v,c),next(NULL) {}
};
Node* sort(Node *list,Node *item) {//链表排序
	Node *p = list, *r;
	if (p->tree.val > item->tree.val) {
		item->next = p;
		list = item;
	}
	else {
		r = p; p = p->next;
		while (p != NULL) {
			if (p->tree.val > item->tree.val) {
				r->next = item;
				item->next = p;
				break;
			}
			r = p; p = p->next;
		}
		r->next = item;
	}
	return list;
}
void code(TreeNode *t, string &cd) {//运用递归实现哈夫曼编码的生成
	if (t->left != NULL || t->right != NULL) {
		cd.push_back('0'); code(t->left, cd);
		cd.pop_back();
		cd.push_back('1'); code(t->right, cd);
		cd.pop_back();
	}
	else
		cout << t->ch << ' ' << cd << endl;
}
void getpower(string &str) {//获取权值并创建有序链表生成哈夫曼树
	vector<int>recode(129, 0);//129位的数组记录每个字符的出现次数
	Node *list = NULL, *p, *r=NULL;
	for (int i = 0; i < int(str.length()); i++)
		recode[str[i]]++;
	int n = 0;
	for (int i = 0; i < int(recode.size()); i++) {//对每一个链节点进行初始化
		if (recode[i]){
			if (list == NULL) {
				list = (Node*)malloc(sizeof(Node));
				list->tree.val = recode[i];
				list->tree.ch = i;
				list->tree.left = NULL;
				list->tree.right = NULL;
				list->next = NULL;
			}
			else {
				p = (Node*)malloc(sizeof(Node(recode[i], i)));
				p->tree.val = recode[i];
				p->tree.ch = i;
				p->tree.left = NULL;
				p->tree.right = NULL;
				p->next = NULL;
				list = sort(list, p);//排序
			}
			n++;
		}
	}
	p = list;
	while (p != NULL) {//输出检验
		cout << p->tree.ch << ":" << p->tree.val << endl;
		p = p->next;
	}
	while (n != 1) {
		p = list->next;
		r = (Node*)malloc(sizeof(Node));
		r->next = NULL;
		r->tree.val = list->tree.val + p->tree.val;
		r->tree.ch = 0;
		r->tree.left = &list->tree;
		r->tree.right = &p->tree;
		list = p->next;
		if(list!=NULL)
			list = sort(list, r);
		n--;
	}
	string s;
	cout << "\n生成编码：\n";
	code(&r->tree,s);
}
int main() {
	string str="Create HaffmanCode!";
	getpower(str);
	return 0;
}