文章

13

粉丝

168

获赞

13

访问

16.4k

头像
哈夫曼树 题解:构建哈夫曼树(笨办法)
P1382 北京邮电大学/兰州大学2019年机试
发布于2023年6月15日 13:15
阅读数 1.1k

没有使用 运算符重载 和 优先队列 来维护树集合的有序性,用了笨办法实现有序插入(先排序后逐个对比)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int i=s;i<e;i++)
#define per(i,s,e) for(int i=s;i>e;i--)

typedef struct Tnode {
    int data;
    Tnode* lchild=NULL;
    Tnode* rchild=NULL;
} Tnode;

void INSERT(vector<Tnode*> &tree_set,Tnode* c){
	rep(i,0,tree_set.size()){
		if(tree_set[i]->data >= c->data){
			tree_set.insert(tree_set.begin()+i,c);
			return;
		}
	}
	tree_set.push_back(c); // 如果找不到比插入节点大的,就直接插入到最后面
}

Tnode* build_hfmtree(vector<int> w){
	vector<Tnode*> tree_set;
	sort(w.begin(),w.end());
	rep(i,0,w.size()){
		Tnode* a=new Tnode; 
		a->data=w[i];	
		tree_set.push_back(a);
	}
	while(tree_set.size()!=1){
		Tnode* a=tree_set[0];
		Tnode* b=tree_set[1];
		Tnode* c=new Tnode; c->data=a->data+b->data;
		c->lchild=a;c->rchild=b;
		tree_set.erase(tree_set.begin(),tree_set.begin()+2);
		INSERT(tree_set,...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发