哈夫曼树毕业论文

#include using namespace std;typedef struct Element{ Element* next; int value;}Element,*Link,*Position;class SortedUnion{private: Link sorted_link;public : SortedUnion() { //创建单链表的头节点 sorted_link = (Link)malloc(sizeof(Element)); sorted_link->next = NULL; } void addValue(int value) { Position pos = insertPosition(value); if(pos!=NULL) { Link tmp = (Link)malloc(sizeof(Element)); tmp->value = value; tmp->next = pos->next; pos->next = tmp; } } void deleteValue(int value) { Position pos,pre=sorted_link; for(pos=sorted_link->next; pos; pos=pos->next) { if(pos->value == value) { pre->next = pos->next; free(pos); break; } pre = pos; } } Position insertPosition(int value) { Position pos; for(pos = sorted_link; pos->next; pos=pos->next) { if(pos->next->value > value) break; if(pos->next->value == value) return NULL; } return pos; } void print() { Link ptr; for(ptr=sorted_link; ptr->next; ptr=ptr->next) cout << ptr->next->value << " "; } friend SortedUnion Intersection(SortedUnion A, SortedUnion B) { SortedUnion C; Position posA = >next, posB = >next; while(posA && posB) { if(posA->value < posB->value) posA = posA->next; else if(posB->value < posA->value) posB = posB->next; else{ (posA->value); posA = posA->next; posB = posB->next; } } return C; }};int main(){ SortedUnion u1,u2,u3; (2); (3); (1); (4); (1); (2); u3 = Intersection(u1, u2); ();}

哈夫曼树的定义是构造一棵最短的带权路径树，所以这种树为最优二叉树。最优二叉树的度只有0或者2。

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

扩展资料：

1951年，当霍夫曼在麻省理工学院攻读博士学位时，他和他的学生们在一门信息理论课程上必须选择是完成一篇学期论文还是参加期末考试。

导师罗伯特·法诺的学期论文题目是：找到最有效的二进制代码。由于无法证明哪些现有代码是最有效的，霍夫曼放弃了对现有代码的研究，转向了新的探索。最后，他发现了基于有序频率的二叉树编码的思想，并很快证明了这种方法是最有效的。

树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。

树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

这句话是错的。书上说过是带权路径最短的二叉树，以树表达与以二叉树表达完全不同。

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

扩展资料：

哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。

对给定的n个权值构造k叉哈夫曼树时，可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式，然后再按照哈夫曼树的方法进行构造即可。

不是结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。数的带权路径长度为所有叶子节点的带权路径长度之和。而不是单纯的权值之和。

大家可能有一个思维惯性就是在visit()时得到的序列为路径，其实正确的思想应该是观察栈中的序列。遍历一棵二叉树时会使用栈，当利用后序遍历到目标结点n时，栈中的序列就为n结点的全部父结点（栈为一个数组）。可以自己画一个二叉树来后序遍历一遍注意观察栈中的元素而不是visit()的元素！

四、遍历二叉树二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。1、按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面6种可能：TLR（根左右）,TRL（根右左）LTR（左根右）,RTL（右根左）LRT（左右根）,RLT（右左根）其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法voidPreOrder(BTreeBT){if(BT){Visit(BT);PreOrder(BT->Lchild);PreOrder(BT->Rchild);}（2）中序遍历递归算法voidInOrder(BTreeBT){if(BT){InOrder(BT->Lchild);Visit(BT);InOrder(BT->Rchild);}}（3）后序遍历递归算法voidPostOrder(BTreeBT){if(BT){PostOrder(BT->Lchild);PostOrder(BT->Rchild);Visit(BT);}}2、按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。voidLevelOreder(QBTreeBT){for(i=1;iLchild){Visite(p->Lchild);EnQueue(&Q,p->Lchild);//处理左孩子if(!p->Rchild){Visite(p->Rchild);EnQueue(&Q,p->Rchild);//处理右孩子}}五、典型二叉树的操作算法1、输入一个二叉树的先序序列，构造这棵二叉树为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。算法：BTreePre_Create_BT(){getch(ch);if(ch=='#')returnNULL;//构造空树else{BT=(BTree)malloc(sizeof(BTLinklist));//构造新结点BT->data=ch;BT->lchild=Pre_Create_BT();//构造左子树BT->rchild=Pre_Create_BT();//构造右子树returnBT;}}2、计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：voidLeaf(BTreeBT,int*count){if(BT){Leaf(BT->child,&count);//计算左子树的叶子结点个数if(BT->lchild==NULL&&BT->rchild==NULL)(*count)++;Leaf(BT->rchild,&count);//计算右子树的叶子结点个数}}3、交换二叉树的左右子树许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：voidchange_left_right(BTreeBT){if(BT){change_left_right(BT->lchild);change_left_right(BT->rchild);BT->lchildBT->rchild;}}4、求二叉树的高度这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：inthight(BTreeBT){//h1和h2分别是以BT为根的左右子树的高度if(BT==NULL)return0;else{h1=hight(BT->lchild);h2=hight(BT->right);returnmax{h1,h2}+1;}}六、树、森林与二叉树的转换1、树、森林转换成二叉树将一棵树转换成二叉树的方法：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。特点：一棵树转换成二叉树后，根结点没有右孩子。将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。2、二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。第3节哈夫曼树及其应用1、哈夫曼树的定义及特点在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。2、构造哈夫曼树的过程：（1）将给定的n个权值{w1,w2,,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。例如：假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if(socre<60)printf("bad");elseif(socre<70)printf("pass");elseif(score<80)printf("general");elseif(score<90)printf("good");esleprintf("verygood");在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：4．前缀编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。（1）等长编码这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{}，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。最后得出每个字符的编码为：比如，发送一段编码：0000011011010010，接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。