教育改变生活

标题: 【数据结构】哈弗曼树的算法实现 [打印本页]

作者: wander    时间: 2023-10-17 18:16
标题: 【数据结构】哈弗曼树的算法实现
哈弗曼树中结点结构构建哈夫曼树时,首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始,不断地构建新的父结点,直至树根,所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始,根据需求遍历树中的结点,因此每个结点需要有指向其左孩子和右孩子的指针。

所以,哈夫曼树中结点构成用代码表示为:


构建哈弗曼树的算法实现构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后构建二叉树。

查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:


实现代码:


注意:s1和s2传入的是实参的地址,所以函数运行完成后,实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。
构建哈弗曼树的代码实现如下:


注意,如果使用此程序,对权重值分别为 2、8、7、6、5 的节点构建哈夫曼树,最终效果如图1(A) 所示。但其实,图 1(B) 中显示的哈夫曼树也满足条件,这两棵树的带权路径长度相同。



图 1 两种哈夫曼树


之所以使用此程序构建的哈夫曼树,是图 1(A) 而不是 4(B),是因为在构建哈夫曼树时,结点 2 和结点 5 构建的新的结点 7 存储在动态树组中位置,比权重值为 7 节点的存储位置还靠后,所以,在程序继续选择两个权值最小的结点时,直接选择了的叶子结点 6 和 7 。





欢迎光临 教育改变生活 (http://bbs.goldoar.com/) Powered by Discuz! X3.2