btree.cpp

本工程编写了一个对任意文件进行 Huffman 编码的类.

// BTree.cpp: implementation of the CBTree class.
//
//////////////////////////////////////////////////////////////////////

#include "BTree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBTree::CBTree()
{
	m_lpTreeHead = NULL;
}

CBTree::~CBTree()
{

}

//////////////////////////////////////////////////////////////////////////
// value: Ansi char
// data: weight
// nNum: length
void CBTree::MakeBTree(BYTE *value, LONG *data, int nNum)
{
	// 1. 将给定的 nNum 个节点的集合构成 nNum 棵二叉树的集合
	int i;

	LPBTreeNode *head = new LPBTreeNode[nNum];
	for (i = 0; i < nNum; i ++)
	{
		head[i]			= new BTreeNode;
		head[i]->left	= NULL;
		head[i]->right	= NULL;
		head[i]->nValue	= data[i];
		head[i]->data	= value[i];
	}

	// 2. 选择两棵根节点权值最小的树构成一棵新的二叉树
	int nRemain = nNum;			// 剩余的节点的个数
	LPBTreeNode lpLeft, lpRight, lpTemp, lpNew;
	int nPos1, nPos2, nTemp;	// 待合并的两个节点存放的位置
	nPos1 = 0;
	while (nRemain > 1)
	{
		nRemain --;
		// 找到第一个非空的节点
		for (i = 0; i < nNum; i ++)
		{
			if (head[i])
			{
				lpLeft = head[i];
				nPos1 = i;
				i ++;
				break;
			}
		}

		// 找到第二个非空的节点
		for (; i < nNum; i ++)
		{
			if (head[i])
			{
				lpRight = head[i];
				nPos2 = i;
				i ++;
				break;
			}
		}

		// 找到集合中最小的两个元素，分别存放到 lpLeft, lpRight 中
		if (lpLeft->nValue > lpRight->nValue)
		{
			lpTemp = lpLeft;
			lpLeft = lpRight;
			lpRight = lpTemp;

			nTemp = nPos1;
			nPos1 = nPos2;
			nPos2 = nTemp;
		}
		for (; i < nNum; i ++)
		{
			if (head[i] == NULL)
				continue;
			 
			if (head[i]->nValue < lpLeft->nValue)
			{
				lpRight = lpLeft;
				nPos2 = nPos1;
				lpLeft = head[i];
				nPos1 = i;
			}
			else if (head[i]->nValue >= lpLeft->nValue && head[i]->nValue < lpRight->nValue)
			{
				lpRight = head[i];
				nPos2 = i;
			}
		}

		// 生成新的二叉树
		lpNew = new BTreeNode;
		lpNew->left = lpLeft;
		lpNew->right = lpRight;
		lpNew->nValue = lpLeft->nValue + lpRight->nValue;
		lpNew->data	= ' ';

		// 3. 将这个新节点加入到集合中，并删除原来两个节点
		head[nPos1] = lpNew;
		head[nPos2] = NULL;
	}

	// 4. 保存二叉树的头结点
	m_lpTreeHead = head[nPos1];
	delete []head;
}

void CBTree::SearchForCode(LPBTreeNode head, char *szCode, char szCodeTable[][200])
{
	// 采用先序遍历
	if (head == NULL)
		return;
	
	if (head->left == NULL && head->right == NULL)
	{
		// 叶子结点
		strcpy(szCodeTable[head->data], szCode);
		return;
	}

	int nLen = strlen(szCode);
	szCode[nLen + 1] = 0;
	szCode[nLen] = '0';
	SearchForCode(head->left, szCode, szCodeTable);
	szCode[nLen + 1] = 0;
	szCode[nLen] = '1';
	SearchForCode(head->right, szCode, szCodeTable);
	szCode[nLen + 1] = 0;
}

void CBTree::GetHuffmanCode(char szCodeTable[][200])
{
	char szCode[255] = {0};
	SearchForCode(m_lpTreeHead, szCode, szCodeTable);
}