云大《数据结构》课程教学课件-第6章 树和二叉树(147P).pptVIP

4a 6b 1c 9d 5 4a 1c 9d 6b 11 5 4a 1c 6b 9d 20 11 5 4a 1c 6b 9d 1）哈夫曼算法思想 (1)根据给定的n个权值w1,w2,……,wn构造n棵二叉树的森林F={T1,T2, ……,Tn}，其中每棵二叉树Ti中仅有一个权值为Wi的根结点，其左右子树为空。 (2) 在F中任选出两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。 (3) 在F中删除这两棵二叉树并将新得到的二叉树加入到F中。 (4) 重复(2)和(3) ,直到F只含一棵二叉树为止，这棵二叉树便是哈夫曼树。 严格二叉树 * 数据结构 * 2）哈夫曼算法的具体实现 分析：哈夫曼树中只有0度和2度结点，不可能有1度结点，因此具有n个叶结点的哈夫曼树其所含结点数必为2n-1。对于n个权值，若构造哈夫曼树，所需存储空间为2n-1个结点所需的空间。若采用顺序存储结构存放哈夫曼树，则可用一个元素个数为2n-1的一维结构数组。 存储结构描述： #define m 2*n-1 typedef struct { float weight; int lchild,rchild,parent; } hufmtree; hufmtree tree[m]; lchild,rchild分别存放左右 子树的根结点的下标值 parent存放双亲结点的下标值 初始时每个结点的lchild,rchild和parent均为-1 * 数据结构 * 算法描述： huffman(tree) huffman *tree; { int i,j,p1,p2; float small1,small2,f; p1,p2分别存放当前扫描到的权值最小和次小结点 的下标。small1,small2分别存放当前扫描到的权 值最小和次小结点的权值。 for (i=0;im;i++) {tree[i].parent=-1;tree[i].lchild=-1;tree[i].rchild=-1; tree[i].weight=0.0;} for (i=0;in;i++) {scanf(“%f”,f); tree[i].weight=f;} for (i=n;im;i++)/*对森林中的树进行n-1次合并,产生n-1个新结点*/ {p1=p2=-1;small1=small2=maxval; for (j=0;j=i-1;j++) if (tree[j].parent==-1) if (tree[j].weightsmall1)  {small2=small1;small1=tree[ j].weight;p2=p1;p1=j;} else if (tree[j].weightsmall2){small2=tree[j].weight;p2=j;} tree[p1].parent=i;tree[p2].parent=i; tree[i].lchild=p1;tree[i].rchild=p2; tree[i].weight=small1+small2; } } 初始化结构数组 读入前n个结点的权值 求权值最小和次小 结点的下标 构造双亲结点(同时意味从森林中 删除原来两棵二叉树） * 数据结构 * 例：已知权值{6,4,1,9},根据上述算法，哈夫曼树的构造过程如下： n=4 m=7 下标 lchild rchild parent weight 0 1 2 3 4 5 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 4 1 9 0 0 0 初始情况 p1=2,p2=1,small1=1,small2=4 下标 lchild rchild parent weight 0 1 2 3 4 5 6 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1