104
最优二叉树算法
练习做一下构造最优二叉树的算法，不过如何计算WPL呢？
本次未能实现，希望懂的人可以帮我解决一下这个问题，不胜感激！
//
// 头文件：HuffmanTree.h
//
// 叶子结点的最大数量
#define LEAVES_COUNT 4
//
// 二叉树的最大结点总数
#define NODES_COUNT (2 * LEAVES_COUNT - 1)
//
// 哈夫曼树的结点结构体
typedef struct tagHuffmanTreeNode
{
float weight; // 权值，假设权值都是大于零的值
int parent; // 指示双亲
int lchild; // 指示左孩子
int rchild; // 指示右孩子
}HuffmanNode;
//
// 哈夫曼树定义为二维数组
typedef HuffmanNode HuffmanTree[NODES_COUNT];
//
// 构造一棵哈夫曼树
void CreateHuffmanTree(HuffmanTree tree);
//
// 初始化
void InitHuffmanTree(HuffmanTree tree);
//
// 输入叶子的权值
void InputWeightsOfLeaves(HuffmanTree tree);
//
// 选择两个权最小的结点生成新的结点
void SelectMin(HuffmanTree tree, int maxValue, int *left, int *right);
//
// 计算哈夫曼树的最小带权路径长度之和
int ComputeWPL(HuffmanTree tree);
//
// 测试哈夫曼树的构造，译码
// HuffmanTree.c
#include <stdio.h>
#include <stdlib.h>
#include "HuffmanTree.h"
int main()
{
HuffmanTree tree;
// 构造哈夫曼树
CreateHuffmanTree(tree);
printf("WPL=%d\n", ComputeWPL(tree));
return 0;
}
//
// 构造一棵哈夫曼树
void CreateHuffmanTree(HuffmanTree tree)
{
int i;
int left, right;
InitHuffmanTree(tree); // 初始化
printf("输入%d个结点值：\n", LEAVES_COUNT);
InputWeightsOfLeaves(tree); // 输入叶子权值至T[0．．n-1]的weight域
// 共进行n-1次合并，新结点依次存于T[i]中
for (i = LEAVES_COUNT; i < NODES_COUNT; i++)
{
// 在tree中0~i-1中选择最小的两个根结点
SelectMin(tree, i - 1, &left, &right);
// 在i个结点作为新合成结点的双亲
tree[left].parent = i;
tree[right].parent = i;
tree[i].lchild = left; // 最小权的根结点是新结点的左孩子
tree[i].rchild = right; // 次小权的根结点是新结点的右孩子
// 新结点的权值
tree[i].weight = tree[left].weight + tree[right].weight;
}
}
//
// 初始化
// 因为C语言数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，
// 它们分别是该结点的左、右孩子和双亲结点在向量中的下标。这里设置parent域有两个作用：其一是使查找
// 某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。
// 将T[0．．m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。
void InitHuffmanTree(HuffmanTree tree)
{
int i = 0;
for (i = 0; i < NODES_COUNT; i++)
{
tree[i].lchild = -1;
tree[i].rchild = -1;
tree[i].parent = -1;
tree[i].weight = 0;
}
}
//
// 输入叶子的权值
// 读人n个叶子的权值存于向量的前n个分量(即T[0．．n-1])中。它们是初始森林中n个孤立的根结点上的权值。
void InputWeightsOfLeaves(HuffmanTree tree)
{
char ch;
int i;
for (i = 0; i < LEAVES_COUNT; i++)
{
scanf("%c", &tree[i].weight);
}
}
//
// 选择两个权最小的结点生成新的结点
void SelectMin(HuffmanTree tree, int maxValue, int *left, int *right)
{
int i, j;
int const MAX_VALUE = 10000;
int m1, m2;
for (i = 0; i < maxValue; i++)
{
m1 = m2 = MAX_VALUE;
*left = 0;
*right = 0;
for (j = 0; j < LEAVES_COUNT + 1; j++)
{
if (tree[j].weight < m1 && tree[i].parent == -1) // 要求此结点还没有构造
{
m2 = m1; // 较大者给m2
*right = *left;
m1 = tree[j].weight; // 取较小者
*left = j;
}
else if (tree[j].weight < m2 && tree[i].parent == -1)
{
m2 = tree[j].weight;
*right = j;
}
}
}
}
//
// 计算哈夫曼树的最小带权路径长度之和
int ComputeWPL(HuffmanTree tree)
{
int i = 0;
int wpl = 0;
for (i = 0; i < NODES_COUNT; i++)
{
if (IsLeaf(tree[i]))
{
wpl += tree[i].weight * (i + 1); // 这里不正确，该如何获取结点所有的层数呢？
}
}
return wpl;
}
//
// 判断是否为叶子结点
int IsLeaf(HuffmanNode node)
{
return node.lchild == -1 && node.rchild == -1;
}
最后更新：2017-04-03 18:51:56