什么是哈夫曼树？
哈夫曼树（Huffman Tree）是一种用于数据压缩的树形数据结构，由David A. Huffman在1952年发明。哈夫曼树通常用于无损数据压缩中，将出现频率高的字符编码成较短的二进制序列，从而减少数据的存储空间。
哈夫曼树的构建过程是基于贪心算法，即每次选择出现频率最低的两个节点合并为一个新的节点，并将它们的权值相加作为新节点的权值，直到最终只剩下一个节点为止。在构建过程中，需要保证所有节点的左子树的权值总和小于右子树的权值总和。
最终生成的哈夫曼树是一棵带权路径长度最小的二叉树，可以根据哈夫曼树来生成每个字符的编码，从而实现数据压缩。
哈夫曼树构建过程从数组中选择权值最小的两个结点，作为子结点，生成一棵树。
他们父结点的权值是他们两结点的权值之和。
然后再以此类推，重复两步，当数组中只剩下一棵树的时候，就已经构建好哈夫曼树了。
构建哈夫曼树代码（C++）下面是使用c++实现的构建哈夫曼树的代码
代码语言：javascript复制//哈夫曼树构建
BTreeNode *CreateHuffman(ElemType a[],int n) {
BTreeNode **b,*q;
b=new BTreeNode*[n];
int i,j;
for(i=0; i b[i]=new BTreeNode; b[i]->data=a[i]; b[i]->left=b[i]->right=NULL; } for(i=1; i int k1=-1,k2; for(j=0; j if(b[j]!=NULL&&k1==-1) { k1=j; continue; } if(b[j]!=NULL) { k2=j; break; } } for(j=k2; j if(b[j]!=NULL) { if(b[j]->data.weight k2=k1; k1=j; } else if(b[j]->data.weight k2=j; } } } q=new BTreeNode; q->data.weight=b[k1]->data.weight+b[k2]->data.weight; q->left=b[k1]; q->right=b[k2]; b[k1]=q; b[k2]=NULL; } delete []b; return q; }哈夫曼前中后、层次遍历这里和二叉树是一样的，就不过多赘述了。都是采用了递归的算法。 c++实现： 代码语言：javascript复制//前序遍历 void PreOrder(BTreeNode* BT) { if(BT==NULL){ return; } cout PreOrder(BT->left); PreOrder(BT->right); } //中序遍历 void InOrder(BTreeNode* BT) { if(BT==NULL){ return; } InOrder(BT->left); cout InOrder(BT->right); } //后序遍历 void PostOrder(BTreeNode* BT) { if(BT==NULL){ return; } PostOrder(BT->left); PostOrder(BT->right); cout }层次遍历： 需要使用队列，首先根节点入队列，只要队列不是空的时候，头结点出队，并且访问出队结点，然后出队结点的左右孩子结点入队列。 一直重复上述步骤，最终即可实现层次遍历。 代码语言：javascript复制//层次遍历 void LevelOrder(BTreeNode* BT) { const int MaxSize=30; BTreeNode* q[MaxSize]; int front=0,rear=0; BTreeNode* p; if(BT!=NULL) { rear = (rear+1)%MaxSize; q[rear] = BT; } while(front!=rear) { front=(front+1)%MaxSize; p=q[front]; cout if(p->left!=NULL) { rear=(rear+1)%MaxSize; q[rear]=p->left; } if(p->right!=NULL) { rear=(rear+1)%MaxSize; q[rear]=p->right; } } }哈夫曼树编码很多时候，再通讯的时候会使用到，需要对信息进行编码，这个时候哈夫曼树就可以对这些通讯实现最优的编码。 下面是哈夫曼树编码的实现算法： 通过递归调用实现哈夫曼编码，函数首先判断当前结点是否由孩子结点，如果没有孩子结点，就直接遍历静态数组，输出，此时数组就是当前结点的哈夫曼编码。如果有孩子结点，就继续递归，左孩子结点就给数组赋值为0，右孩子结点就给结点赋值为1。 c++: 代码语言：javascript复制//哈夫曼树编码，len传入的时候是0，因为根节点的是0 void HuffManCoding(BTreeNode *FBT,int len){ static int a[10]; if(FBT!=NULL){ if(FBT->left==NULL&&FBT->right==NULL){ //这里证明已经到了叶子结点，可以开始将a数组进行遍历输出即可形成编码 cout for(int i=0;ileft,len+1); a[len]=1; HuffManCoding(FBT->right,len+1); } } }