最优二叉树算法

练习做一下构造最优二叉树的算法，不过如何计算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;
}