什么是哈夫曼树 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+ WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。 构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示： 哈夫曼树的算法实现 #include<iostream>#include<iomanip>#include<cfloat>using namespace std; const int n=5; const int m=2*n-1; typedef struct{ float weight; int parent,lchild,rchild; }nodetype; typedef nodetype hftree[m]; hftree T; void huffman(hftree T){ int p1,p2,i,j; float small1,small2; for(i=0;i<n;i++){ T[i].parent=T[i].lchild=T[i].rchild=-1; } for(i=0;i<n;i++){ cin>>T[i].weight; } for(i=n;i<m;i++){ p1=p2=-1; small1=small2=FLT_MAX; for(j=0;j<=i-1;j++){ if(T[j].parent!=-1)continue; if(T[j].weight<small1){ small2=small1; small1=T[j].weight; p2=p1; p1=j; } else if(T[j].weight<small2){ small2=T[j].weight; p2=j; } } T[p1].parent=T[p2].parent=i; T[i].parent=-1; T[i].lchild=p1; T[i].rchild=p2; T[i].weight=small1+small2; } } 输出哈夫曼树 这里用到了头文件，主要是运用setw()控制一下输出的格式……

阅读全文

算法的基本思想：依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点；若新结点是第1个结点，则令其为根节点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直到输入字符“#”为止 核心代码： Bitree level_create(){ char ch; pointer Q[maxsize+1]; int front,rear; pointer root,s; root=NULL; front=rear=0; while(cin>>ch,ch!='#'){ if(ch!='@'){ s=new node; s->data=ch; s->lchild=s->rchild=NULL; } else s=NULL; rear++;//不管结点是否为虚，都要入队 Q[rear]=s; if(rear==1){//第一个结点是根，要修改头指针，它不是孩子 root=s; front=1; } else{ if(s&&Q[front]){ if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; } if(rear%2==1)front++;//不论是否为虚，右孩子入队后，双亲出队 } } return root; } ……

阅读全文

对着书本敲了一个钟的二叉树，被二叉树建立时的输入问题困扰了很久。二叉树的建立一般使用递归算法，将所有节点的数据猛的输入，递归无法停止，二叉树就无法建立。 自己对着书本敲了一次也没发现怎么回事，最后看了一篇博文之后，豁然开朗。我们在输入节点数据的时候，必须输入空闲叶子结点，并用特殊符号标记。 最后自己终于实现了最终的二叉链表的构造及其三种顺序遍历的实现 PS：输入的时候得适当制造一定数量的空节点才能结束二叉树的输入，这个需要个人自己体会。 代码如下： #include <iostream> using namespace std; typedef struct node* pointer; typedef char datatype; typedef struct node { datatype data; pointer left, right; }BinTNode;//定义结构体BinTNode typedef BinTNode* BinTree;//结构体指针BinTree BinTree Create_Tree()//二叉树的创建 { BinTree p; char c; cin >> c; if (c == '#')//如果遇到字符串"#"，则设该结点值为空 p = NULL; else { p = new node; p->data = c; p->left = Create_Tree(); p->right = Create_Tree(); } return p;//返回二叉树结构体指针 } void preorder(BinTree T) {//先序遍历 if (T !……

阅读全文