树和叉树_数据结构.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * DDD * * * 概念 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 哈夫曼树的概念 路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。 路径长度：路径上的分支数目称为路径长度。 树的路径长度：树的根结点到树中每一个结点的路径长度的和。 * * 结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积 树的带权的路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(Weighted Path Length)。 由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（ Huffman）树。 哈夫曼树的概念（续） * * 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 d c a b 2 4 7 5 * * 哈夫曼树的性质 1、哈夫曼树只有度为0和2的结点，无度为1的结点； 2、权值大的结点离根结点近； 3、n个叶子的哈夫曼树的形态一般不唯一，但WPL是相同的； 4、n个叶子的哈夫曼树共有2n-1个结点。 * * 根据给定的n个权值{w1,w2,…,wn}，构造n棵只有根结点的二叉树，令其权值为wj; 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和; 在森林中删除这两棵树，同时将新得到的二叉树加入森林中; 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树 。 构造Huffman树步骤 * * d c b a 9 6 5 3 b a 9 6 3 5 8 a 9 6 14 3 5 8 9 6 23 14 5 3 8 a b c d c b d 哈夫曼树的构造举例 * * 例 w={5, 29, 7, 8, 14, 23, 3, 11} 5 14 29 7 8 23 3 11 14 29 7 8 23 11 5 3 8 8 7 15 14 29 23 5 3 8 11 11 5 3 8 19 14 29 23 8 7 15 11 5 3 8 19 29 23 14 8 7 15 29 29 14 8 7 15 29 11 5 3 8 19 23 42 11 5 3 8 19 23 42 29 14 8 7 15 29 58 11 5 3 8 19 23 42 29 14 8 7 15 29 58 100 哈夫曼树的形态是不唯一的 * * 自测题 27 给定权值7，6，3，32，5，26，12，9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。 哈夫曼树的类型定义 typedef struct {int weight; int parent, lchild, rchild; } HufmTree; * * 哈夫曼树的构造算法 viod CreatHuffman(HufmTree tree[]，int n) {?? 构造哈夫曼树，n为初始森林中的结点数 int i,j,t1,t2； if (n=1) return; m=2*n; //下标为0的单元不用 for (i=1; im ; i++) ?? 对数组初始化 {tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0; } * * 哈夫曼树的构造算法 for (i=1; i=n ; i++) ?? 读入叶结点权值 scanf(tree[i].weight; for (i=n+1; im; i++) ?? 进行合并，产生n-1个新结点 {Select(tree,i-1, t1,t2) ??选出parent 的值为0且权值最小的两个结点,序号为t1,t2 tree[t1].parent=i; tree[t2].parent=i;