数据结构与算法.ppt

文档介绍：树和二叉树第8讲数据结构与算法授课教师:曾晓东答疑群:——二叉链表表示法typedefstructCSNode{ElemTypedata;structCSNode*firstChild,*nextSibling;}CSNode,*CSTree;树二叉树对应存储存储解释解释树的存储结构——,编写函数,先序遍历以R为根的树函数原型为: voidPreOrderTraverse(CSTreeR)使用visit(CSTreex)访问结点x提示:先访问根:visit(R)对R的所有孩子p进行循环:for(p=R->firstChild;!p; p=p->nextSibling)先序遍历当前子树:PreOrderTraverse(p)在远程通讯中,要将待传字符转换成二进制的字符串,怎样编码才能使它们组成的报文在网络中传得最快?DA000110010101100000011010哈夫曼树应用实例--哈夫曼编码出现次数较多的字符采用尽可能短的编码关键:要设计长度不等的编码,则必须使任一字符的编码都不是另一个字符的编码的前缀-DA000011010哈夫曼树应用实例--哈夫曼编码ACBD000111采用二叉树设计前缀编码左分支用“0”右分支用“1”A—0B—110C—10D—DA哈夫曼树应用实例--哈夫曼编码分解接收字符串:遇“0”向左,遇“1”向右;一旦到达叶子结点,则译出一个字符,反复由根出发,直到译码完成。DA特点:每一码都不是另一码的前缀,绝不会错译!称为前缀码哈夫曼编码的译码过程