严蔚敏数据结构 (11).ppt

1、第1，6章树和二叉树(Tree i=10，a=110，n=111 )，为了实现哈夫曼编码化，首先建构哈夫曼树，进行讨论：明确哈夫曼树有什么作用，权重大的节点是短路径，权重小的节点是长路径。对WPL最小的树、频度高的信息用短查询密码、频度低的长查询密码、传输效率确实高的WP L2=1比特72比特53比特(24 )=35、最小冗余码化、信息效率传输、5，2.huffman树进行建构的步骤(即Huffman算法) 以f中两根根结点权重最小的树作为左右的子树来建构新的二叉树，以使新的二叉树的根结点权重等于该左右的子树的根结点权重之和。 (3)在f中删除这些个2棵树的同时，将新得到的二叉树添加到f中。

2、(4)反复(2)和(3)直到f只包含一棵树。 这棵树是Huffman树。 如何证明WPL是最小的最佳二叉树？ 参照原代码，即一次合并当前值最小的两个权重。 (该树的特征：度不为1的节点)，6，step1:合并、删除、置换权重集7，5，2，4中，始终合并当前值最小的2个权重，具体的操作步骤：a .初始，框表示外节点.不规定则并非唯一step2:将huffman树的所有分支编号向左“0”右“1”推一推，huffman编码结果： d=0，i=10，a=110， n Huffman编码也被称为前缀代码，其将Huffman树与Huffman编码相链接，并且8、2、Huffman编码、哈夫曼编码化的基本思

3、想是用于出现概率大的信息的短码、用于概率小的长码、最小冗馀、Huffman编码、不相等长度编码，如9、本节中的建议1:Huffman树中的节点结构可以修改为4或5分量形式。 将整个Huffman树的节点保存在一个数组HT1.n.m中(Huffman树内外结点总数m=2n-1 )各叶子结点的查询密码保存在另一个“复合”组HC1.n中。 (n个权重是n个叶，对应于n个不同的查询密码列)。建议2: Huffman树的存储结构可以采用这样的顺序存储结构，其中，在建构Huffman树HT之后，确定n个权重/字符的Huffman查询密码HC 例1【严格问题集6.26】:假设用于通讯的电文仅由8个字符的a、

4、b、c、d、e、f、g、h构成，它们出现在电文中的概率分别为0.07、0.19、0.02、6.26。 使用07的二进制编码方式会怎么样？ 【类同P148例2】、11、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0 13、12、1011、9、8、7、6、5、4、3、2、1、 小盆友lchild，rchild，12，2，7，对应哈夫曼编码：12，40，60，100，父代，左右的。 Huffman码的WP L2 (0. 19.32 )3(0. 190.320.210.070.060.10.020.03 )=3、二进制等长查询密码的WPL用左0右1来表示、1

5、3、另一个表示：14、自动机练习说明：字符定径套为26阿尔法、请求：建构Huffman树后，使用该树对任意字符串文件进行查询密码和查询密码后，将设定Huffman编译码器、15、类型树未绑定权重。 /权重成分(可扩大取得) unsigned int parent，lchild，rchild； /父母和小盆友的分量HTNode，*HuffmanTree； 胡夫曼树类型树* *胡夫曼代码； /动态数组存储Huffman查询密码表，Huffman树和Huffman树查询密码的存储表示：父母，* Huffman树或HT矢量模式：HT3.parent=9，指针类型指针，16，voidhuffmancod

6、ing (hoidhuffmancoding /n个叶的Huffman树一共有2n-1个结点。 ht=树形大小(m1) *大小(htnode ) )/0未使用针织面料，for(p=HT 1，i=1； i=n； I，p，w)*p=*w，0，0，0。 /初始化前n个用户针织面料(原教材有错误) for (； i=m； I，p ) * p=0，0，0，0。 /叶后的存储单元清零for(i=n 1； i=m； i)/huffman树(从n个叶子之后存储内结点) Select(HT，i-1，s1，s2)； 选择HT1i-1中父节点为0且权重最小的两个节点，其编号分别为s1和s2 (教材中未列出该函数的原

7、代码) HTs1.parent=i； HTS2.伙伴=I； /对父母的分量分配HTi.lchild=s1。 S2 :天空飞行器； /将小盆友值hti.weight=h ts1. weight HTS2. weight赋予合并的内结点。 存储*wn字符的权重int *w表示w是指向int数组的指针，*w取int，w之后*w取下一个要素w等同于数组名(即指向该int数组的指针)。 17，sizeof ()可以运算变量或变量类型。 sizeof(char* )是char型指针的空间大小，如果定义了char *p，则sizeof(p )为结果和sizeof (续) n个字符的Huffman关查询密码字

8、HC，HC=(Huffman代码) malloc (n1) * sizeon /n字符查询密码的头指针矢量(一维度数组)，cd=(char*) malloc(n*sizeof(char ) )； /求编码的临时最长空间cdn-1=“0”； /编码终端查询密码(从cd0cdn-1到合法空间) for(i=1； i=n； i) /对每个字符求出Huffman查询密码start=n-1。 /查询密码终端查询密码位置for(c=i，f=HTi.parent； f！=0； c=f，f=HTf.parent) /从叶子到根向相反方向查询密码定if(HTf.lchild=c) cd-start=“0”； e

9、lse CD-开始=“1”； HCI=(char * ) malloc (n-start ) * sizeof (char ) )/为第I个字符查询密码分配空间，每个查询密码列指针strcpy(HCi， /释放临时空间/HuffmanCoding，p 149，18，以数组形式存储二叉树的若干示例性算法(练习题) 4的算法构想：利用队列存储指向每个子树节点的指针是最好的方法，因为既然要求从上到下、从左到右技巧：将根结点入队后，将左、右小盆友节点入队，将左小盆友入队后，将左右小盆友节点入队，从而按级别进行输出。 1 .如何获得二叉树的深度或从一个节点开始的子树的深度？算法构想：仅检查每个节点的后续

10、网络链接表指针，如果左(右)小盆友的左(右)指针不为空，则为分层数加1，否则函数返回。 算法为附件1，算法为附件2，20，算法构想：如果不递归，则在实现二叉树扫描的“嵌套”规则时，必须使用栈内存(迭代方式)。 可通过推/pop与while语句直接操作。 参见教材P130-131普通堆计程仪。 用4顺序扫描的非递归算法是如何实现的？ 3、如何判断给定二叉树是否完全二叉树的算法构想：完全二叉树的特征是，左子树空，右子树不可能单独存在(前k-1层全部填满，第k层左侧也填满)。 在技巧：分层遍历方案中，首先对所有节点(不管当前节点是否有左右小盆友)进行排队。 在完全二叉树的情况下，在分层扫描中获得的序

11、列不总是包括连续的空指针。 如果序列中出现空指针，则表示不是完全二叉树。算法为附件3，算法为附件4、21，Void ABC(Bitree p、int l、int，法1 :从根向下修正层次(比从叶向上修正简单)，l、h分别表示二叉树的层次数和深度。想一想。 l和h的初始值应该是多少？ 在开始调用时，使用ABC(p，0，0 )删除h关残奥字计数器的“/左右两个深度/层次计数器if (Bt=空)返回(0)”。 /如果当前节点指针为空，则立即返回深度=树深度(Bt-left )； /当前节点的左侧子树right dep=树深度(Bt-right )； /当前节点的右侧子树if (leftdeprigh

12、tdep )返回(left dep1)； 从叶子返回(right dep1)； /BTreeDepth，法2 :递归地从叶子向上计数，留下深层的东西。 二十三、语音层次顺序/层序扫描二叉树入队列(q )； /创建空工作团队(初始化队列)枚举(q，t )。 /将一个节点插入队列末尾的函数while (！ QueueEmpty(Q) ) DeQueue(Q，/p的右小盆友入队/LayerOrder，附件2 :分层遍历算法(需要使用队列)严格问题集6.47，当小盆友为空时不要将空指针入队。 /建设队列(初始化队列) flag=0； /标志初始化EnQueue(Q，t )； /节点t入队(空指针也入队) while (！ QueueEmpty(Q) DeQueue(Q，/执行到目前为止在队列空间中没有空指针的完全二叉/IsFull_Bitree，25，statusinordertrav p=T； /初始化关栈内存字while(p |！ 堆栈进度(s ) )/如果树不为空或堆栈内存不为空，则开始老虎吧定if (p )推式(s，p )。