当前位置: 代码迷 >> 综合 >> 深入理解数据结构——哈夫曼树
  详细解决方案

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

热度:41   发布时间:2024-01-17 05:08:28.0
#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];//最小节点存放到xH.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;}