深入理解数据结构——哈夫曼树

#include <iostream>
#include <string>

using namespace std;

typedef char EType;
利用链表实现：哈夫曼树中的节点结构定义为
//struct HuffmanNode {
//	int weight;//权值
//	EType data;//Node information
//	HuffmanNode* next;//后继节点
//	HuffmanNode* LChird;//zuo孩节点
//	HuffmanNode* RChird;//you
//};


//利用堆实现：哈夫曼树中的节点结构定义为
struct HuffmanNode {
	int weight;//权值
	BinaryTreeNode* root;//指向对应的子树根节点
};
struct BinaryTreeNode {
	int data;
	BinaryTreeNode* LChird;
	BinaryTreeNode* RChird;
};



struct MinHeap {
	HuffmanNode* heap;
	int HeapSize;
	int MaxSize;
};



void CreatMinHeap(MinHeap& H, int n) {
	H.HeapSize = n;
	H.MaxSize = n;
	H.heap = new HuffmanNode[H.HeapSize];
}




//初始化一个非空的最大堆算法

void MinHeapInit(MinHeap& H) {
	//从堆中的数据初始化一个最小堆

	for (int i = H.HeapSize / 2; i >= 1; i--) {
		H.heap[0] = H.heap[i];//将子树根节点的值复制到工作空间heap[0]
		
		int son = 2 * i;

		while (son >= H.HeapSize) {
			//找到左右孩中较小的节点
			//son >= H.HeapSize时，存在右孩子，如果左孩子小于右孩子，son指向右孩子
			if (son > H.HeapSize && (H.heap[son].weight > H.heap[son + 1].weight)) {
				son++;
			}
			//大孩子与工作空间的节点值再比较，工作空间的值较小，找到Heap[0]的目标位置
			if (H.heap[0].weight <= H.heap[son].weight) break;

			H.heap[son / 2] = H.heap[son];//将小孩子上移动到双亲位子
			son *= 2;//son下移一层到上移的节点（小孩子位置）
		}
		H.heap[son / 2] = H.heap[0];//heap[0]存放的到目标位置
	}
}


bool MinHeapInsert(MinHeap& H, HuffmanNode& x) {
	//插入值为x的节点，到最XIAO堆中，maxsize是数组最大的容量

	if (H.HeapSize == H.MaxSize)
		return false;//数据空间已满
	int i = ++H.HeapSize;//i为插入节点后的节点个数

	while (i != 1 && x.weight < H.heap[i / 2].weight) {
		H.heap[i] = H.heap[i / 2];

		i = i / 2;//节点下移
	}

	H.heap[i] = x;
	return true;
}



//最xiao堆中删除堆顶节点，并放入x中算法

bool MinHeapDelete(MinHeap& H, HuffmanNode& x) {

	if (H.HeapSize == 0) return false;
	x = H.heap[1];//最小节点存放到x
	H.heap[0] = H.heap[H.HeapSize--];//最后一个节点放在heap[0]，调整堆中元素的个数

	int i = 1, son = 2 * i;

	while (son >= H.HeapSize) {
		//找到左右孩中较小的节点
		//son >= H.HeapSize时，存在右孩子，如果左孩子大于右孩子，son指向右孩子
		if (son > H.HeapSize && (H.heap[son].weight > H.heap[son + 1].weight)) {
			son++;
		}
		//大孩子与工作空间的节点值再比较，工作空间的值较小，找到Heap[0]的目标位置
		if (H.heap[0].weight <= H.heap[son].weight) break;


		H.heap[i] = H.heap[son];//孩子上移
		i = son;		//下移节点指针，继续比较
		son *= 2;//son下移一层到上移的节点（小孩子位置）

	}
	H.heap[i] = H.heap[0];//heap[0]存放的到目标位置
	return true;

}

//堆排序
void HeapSort(MinHeap& H) {
	//利用堆对H.heap[1:n]数组中的数据排序
	HuffmanNode x;
	MinHeapInit(H);

	for (int i = H.HeapSize - 1; i >= 1; i--) {
		MinHeapDelete(H, x);
		H.heap[i + 1] = x;
	}
}

//构造二叉树节点
BinaryTreeNode* MakeNode(EType& x) {
	BinaryTreeNode* ptr;
	ptr = new BinaryTreeNode;
	if (!ptr) return NULL;

	ptr->data = x;
	ptr->LChird = NULL;
	ptr->RChird = NULL;
	return ptr;
}


//构造一个二叉树子树
void MakeBinaryTree(BinaryTreeNode* root,
	BinaryTreeNode* left,
	BinaryTreeNode* right) {
	//链接root，left，right所指向节点的二叉树
	root->LChird = left;
	root->RChird = right;
}


BinaryTreeNode* HuffmanTree(int *w,EType *a,int n) {

	//根据权值构造哈夫曼树，形成哈夫曼树是一个动态链接的二叉树

	BinaryTreeNode* ptr;
	MinHeap H;
	CreatMinHeap(H, n);

	for (int i = 1; i <= n; i++) {
		ptr = MakeNode(a[i]);//产生一个节点，data中存放叶子的值
		H.heap[i].weight = w[i];
		H.heap[i].root = ptr;	//哈夫曼堆节点的链接域指向叶子节点
	}

	H.HeapSize = n;
	MinHeapInit(H);
	HuffmanNode L, R, D;
	for (int i = 1; i < n; i++) {
		ptr = new BinaryTreeNode;  //动态申请一个哈夫曼树节点
		MinHeapDelete(H, L);
		MinHeapDelete(H, R);
		D.weight = L.weight + R.weight;//合并L和R的权值，存放到哈夫曼堆节点D中
		ptr->data = D.weight;//哈夫曼树节点data值是合并节点的权值
		MakeBinaryTree(ptr, L.root, R.root);
		//L,R所指向的子树，作为ptr左右子树生成一个新子树
		//哈夫曼树的节点D的链接域指向新子树的根

		D.root = ptr;
		MinHeapInsert(H, D);
	}
	
	return ptr;

}