当前位置 博文首页 > ice_elephant的博客：通过二叉树来实现哈夫曼编码树
4.1 哈夫曼编码 哈夫曼（Huffman）编码算法是基于二叉树构建编码压缩结构的，它是数据压缩中经典的一种算 法。算法根据文本字符出现的频率，重新对字符进行编码。 首先请大家阅读下面两段中外小学作文： 中国 - 今天天气晴朗，我和小明出去玩！小明贪玩，不小心摔了一跤，小明被摔得哇哇哭了，小明的爸爸闻 声赶来，又把小明痛扁了一阵。小明的小屁屁都被揍扁了，因为小明把妈妈刚买给他的裤子弄破了！ 外国 - 今天天气晴朗，我和乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔 尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿出去玩！乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥 特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿贪玩，不小心摔了一跤，乔伊·亚 历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普 雷斯顿被摔得哇哇哭了，乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅 尔斯·帕特森·汤普森·华莱士·普雷斯顿的爸爸闻声赶来，又把乔伊·亚历山大·比基·卡利斯勒·达夫·埃 利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿痛扁了一阵。乔伊·亚历 山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普 雷斯顿的小屁屁都被揍扁了，因为乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马 尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿把妈妈刚买给他的裤子弄破了！
哈夫曼编码举例： 假设要对“we will we will r u”进行压缩。
压缩前,使用 ASCII 码保存:119 101 32 119 105 108 108 32 119 101 32 119 105 108 108 32 114 32 117
#pragma once
#include<stdio.h>
#define MAX_SIZE 1024
#define isLess(a,b) (a<b)
#define isEqual(a,b) (a==b)
typedef int ElemType;
typedef struct _Bnode{
ElemType date;
_Bnode *lchild,*rchild;
}Bnode,Btree;
//数据结构算法之二叉树，二叉树就是分成两叉的树
//
typedef Bnode Elemdate;
typedef struct _Stack{
Elemdate *base;
Elemdate *top;
}Stack;
//栈的初始化
bool initStack(Stack &stack){
stack.base = new Elemdate[MAX_SIZE];
if(!stack.base){
printf("栈初始化失败!\n");
return false;
}
stack.top = stack.base;
return true;
}
//获取栈顶元素
Elemdate* getTop(Stack &stack){
return stack.top-1;
}
//入栈
bool PushStack(Stack &stack,Elemdate date){
if(stack.top-stack.base==MAX_SIZE){
printf("栈空间已满，入栈失败!\n");
return false;
}
*(stack.top++) = date;
return true;
}
//出栈
bool PopStack(Stack &stack,Elemdate &date){
if(stack.base==stack.top){
printf("无元素可出栈!\n");
return false;
}
date = *(--stack.top);
return true;
}
//判断栈是否为空
bool isEmpty(Stack&stack){
if(stack.base==stack.top){
return true;
}
return false;
}
//判断栈是否已满
bool isFully(Stack &stack){
if(stack.top-stack.base==MAX_SIZE){
return true;
}
return false;
}
//销毁栈
void destoyedStack(Stack &stack){
if(!&stack) return;
delete [MAX_SIZE] stack.base;
stack.base = stack.top = NULL;
}
//获取以元素个数
int getElemdateCount(Stack &stack){
return (stack.top-stack.base);
}
在这里插入代码片
#include"Stack.h"
#include<stdio.h>
#include<Windows.h>
//树的插入，找到最大值、树的删除、树的前序遍栈实现，以及递归实现
//1、树的插入
bool InsertBnode(Bnode **root,Bnode *node){
if(!node)return false;//防御性编程
//插入元素，分为两种情况，如果没有父节点时直接把node变为父节点即可
node->lchild = NULL;
node->rchild = NULL;
Bnode *tmp = NULL;
Bnode *parent = NULL;
if(!*root){
*root = node;
return false;
}else{
tmp = *root;
}
//开始不断查找合适位置插入，比较node->date和tmp->date大小，若node->date>tmp->date,就将tmp=tmp->rchild,反之同理
while(tmp){
parent = tmp;
if(isLess(node->date,tmp->date)){//和当前根节点比较 is ok，parent是一定存在的
tmp = tmp->lchild;
}else{
tmp = tmp->rchild;
}
}
if(isLess(node->date,parent->date)){
parent->lchild = node;
}else{
parent->rchild = node;
}
}
//2、找最大值结点
//Btree *findMax(Btree *root){
//
// /*if(!root) return NULL;
//
// Btree *tmp = root;
//
// while(tmp->rchild) tmp =tmp->rchild;
//
// return tmp;*/
//
// if(root->rchild==NULL){
// return root;
// }else{
//
// return findMax(root->rchild);
// }
//
//}
int findMax(Btree *root){
if(root->rchild==NULL){
return root->date;
}
return findMax(root->rchild);
}
//树删除特定值的结点，略微复杂一点
/*
分为四种情况
1、如果查到的结点左右子节点都不存在那么就把这个东西置为NULL赋值给上面
2、如果查到的结点存在左子结点那么就把左子结点给当前这个结点
3、如果查到的结点存在右子结点那么就把左子结点给当前这个结点
4、如果左右子节点都存在的话，还找先找到左侧最大的那个结点与当前这个结点的值交换，然后删掉那个最大的结点
*/
Btree *DeleNode(Bnode *root,int key,Bnode *&delenode){//delenode记录一下干点的结点
if(!root) return NULL;
if(root->date>key){
root->lchild = DeleNode(root->lchild,key,delenode);
return root;
}
if(root->date<key){
root->rchild = DeleNode(root->rchild,key,delenode);
return root;
}
//找到了与key值相等的元素
delenode = root;
//左右结点都不存在
if(root->lchild==NULL&&root->rchild==NULL) return NULL;
//存在左子结点
if(root->lchild!=NULL&&root->rchild==NULL) return root->lchild;
//存在右子节点
if(root->lchild==NULL&&root->rchild!=NULL) return root->rchild;
//左右子节点都存在时候
//先找该key结点左子节点一侧的最大值
int Val = findMax(root->lchild);
root->date = Val;
//此时干掉那个最大值原有的结点
