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