哈夫曼树的构造.doc

哈夫曼树的构造构造哈夫曼树的过程是这样的一、构成初始集合对给定的 n 个权值{W1,W2,W3,...,Wi,...,Wn} 构成 n 棵二叉树的初始集合 F={T1, T2,T3,...,Ti,...,Tn} , 其中每棵二叉树 Ti 中只有一个权值为 Wi 的根结点, 它的左右子树均为空。( 为方便在计算机上实现算法, 一般还要求以 Ti 的权值 Wi 的升序排列。) 二、选取左右子树在F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树, 新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、删除左右子树从F 中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合 F中。四、重复二和三两步, 重复二和三两步,直到集合 F 中只有一棵二叉树为止。举个例子有个序列是(7,9,2,6,32,3,21,10) 叫你求哈夫曼树步骤一:把这些点都看成是一个只有根结点的树的集合 F 步骤二,选 2 个值最小的树步骤三:在这些树的集合 F 中删除这 2 棵树然后把构成一颗二叉树变成了(5=2+3 ) 然后把这个树加入到集合 F 5 代表这棵树的权值然后继续上述步骤肯定是选 5和6 把这 2 个构成二叉树在F 中删除 56 加入 11 这棵树变成了继续上述步骤选7和9在F 中删除 7和9 加入 16 这棵树变成了继续上述步骤选 10和 11 在F 中删除 10和 11 加入 21 这棵树继续上述步骤选 16和 21 (有 2个 21 ,随便选哪个) 我选那个只有一个根结点的 21 好了 16和 21 构成二叉树在F 中删除这 16和 21 这两棵树加入 37 这棵树继续上述步骤选 21和 32 构成二叉树在F 中删除 21和 32这2 两棵树加入 53 这棵树还是继续上面步骤把F 中的两棵树合并成一棵树完成了! 这个就是哈夫曼树