哈夫曼树Huff的创建

①定义以及作用
哈夫曼树：哈夫曼树是字符的编码，目的是为了获取最小的WPL，即最小的代价(表达能力有限，不知道咋说)，顾名思义来理解吧，就是为了编码！！！
哈夫曼的创建
哈夫曼树的创建是基于堆来实现的，所以事先需要对堆有所了解，查看上篇博客QAQ。。
哈夫曼树树的建树原理，想必大家都知道，就是根据权值数组来建立的：

过程是：1.从权值数组中挑选出两个最小的权值，建立两个树节点，作为左右儿子，父节点的值为左右儿子值的和。
2.将父节点的权值放入权值数组中，然后从步骤1继续开始，直到权值数组为空。

那么，哪里会用到堆？？？？
①利用堆，来存储权值数组，实现最小权值的获取和新的权值的插入，时间复杂度为logn
------>也许有的童鞋会想 (因为我这个童鞋也在想，QAQ，到底为什么？)

假如我用结构体数组来存储权值，在插入新权值，用二分插入，时间复杂度也是logn呀！！

-------------------大家原谅我的无知，因为堆的实现就是数组TvT！----------------------
②大家应该知道，堆的Insert()插入函数，插入的一个数据data，对于哈夫曼树的创建，则插入的是一个哈夫曼树节点，即如下的一个节点：（也就是平常无奇的一个树节点而已）

typedef struct Huff_Node *huff;
struct Huff_Node{huff left; //右儿子huff right; //左儿子int w; //该节点的权值
};

看到这里，小伙伴们应该知道了，哈夫曼树，其实就是利用堆来搭建起来的(简言之，利用堆来找节点的左儿子和右儿子，然后遍历完数组就完事了！然后整棵树就建立完成，返回根节点，具体看下面代码来深入理解，一言不合就撸代码(→ .→))
Huff树构建
如前面所说，堆存储的哈夫曼节点，故堆heap结构体的定义如下：

typedef struct Heap_Node *heap;
struct Heap_Node{huff data; //哈夫曼节点指针变量int size;
};

创建空堆heap的代码如下：

heap creat_empty_heap(int n){heap tmp = (heap)malloc(sizeof(struct Heap_Node));    //开辟大小为n+1个哈夫曼结构体大小的数组  tmp->data = (huff)malloc(sizeof(struct Hudd_Node) * (n + 1))tmp->size = 0;    tmp->data[0].w = -999; //哨兵return tmp;
}

向堆中插入huff哈夫曼节点代码如下：

void Insert(heap h,struct Huff_Node hu){ //简单的insert操作，堆的插入操作int i= ++h->size;    int w = hu.w;    for (; h->data[i / 2].w > w;i = i/2){h->data[i] = h->data[i / 2];}    h->data[i] = hu;
}

获取最小堆中权值最小的哈夫曼节点，即根节点：

huff delete_minheap(heap h){huff ans = (huff)malloc(sizeof(struct Huff_Node));    *ans = h->data[1];    struct Huff_Node x=  h->data[h->size--];    int parent = 1, child;    for (; parent * 2 <= h->size;parent = child){child = parent *2;        if(child + 1 <=h->size && h->data[child + 1].w < h->data[child].w)            child++;        if(h->data[child] >= x.w)            break;        h->data[parent] = h->data[child];}    h->data[parent] = x;    return ans;
}

创建哈夫曼树，过程如下:

1.定义一个huff节点，左儿子为堆中最小权值节点，右儿子为删除最小权值节点后，二次获取的最小权值节点，该huff节点的权值为两儿子节点权值之和。
2.将生成的新的huff节点插入堆中，继续步骤1，进行h->size - 1步，因为最后堆中只剩一个哈夫曼节点，也就是传说总的huff树根节点
3.最后获取堆中最后一个节点，直接原地返回

代码如下:

huff create_huff(heap h){huff tmp;    int len = h->size;    for (int i = 1; i <len; i++){tmp = (huff)malloc(sizeof(struct Huff_Node));        tmp ->left = delete_minheap(h);        tmp ->right = delete_minheap(h);        tmp->w = tmp->left->w + tmp->right->w;        Insert(h, *tmp);}    tmp = delete_minheap(h);    return tmp;
}

主函数如下:

int main(){int n,data;    heap h;    huff hu;    cin >> n;    h = creat_empty_heap(n);    for (int i = 1; i<=n; i++){cin>>data;hu = (huff)malloc(sizeof(struct Huff_Node));        hu->w = data;        hu->left = NULL;        hu->right = NULL;        Insert(h, *hu);    }    hu = create_huff(p);    return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！