数据结构-树的概念和二叉树.ppt

第四章 树的概念和二叉树;4.1 树的基本概念;;1. 树的定义(递归版);;定义4.2 （非递归版）;2. 树的相关术语;;;树作为无向图的性质;树的等价定义;3、树在计算机领域有广泛的应用;4.2 二叉树;树与二叉树的主要区别;;引理4.1 ;引理4.2 ;引理4.3 ;;满二叉树;满二叉树的特点;完全二叉树;完全二叉树的特点;引理4.4 ;引理4.5 ;2 二叉树的顺序存储;完全二叉树的顺序存储;;二叉树的链接存储;;;三叉链;二叉树的遍历;先根遍历 (前/先序遍历);先根遍历算法;中根遍历(中序遍历);中根遍历算法;后根遍历 (后序遍历);后根遍历算法;练习;非递归的中根遍历算法;;非递归的后根遍历算法;;算法思想;;算法NPostOrder(t);二叉树的层次遍历;;算法LevelOrder ( t );创建二叉树;;;练习;带空指针的先根序列;;算法CBT (tostop . t );复制二叉树;算法 CopyTree (t . p );有哪些信誉好的足球投注网站父结点;有哪些信誉好的足球投注网站数据;删除给定结点及其左右子树;;插入结点作为某结点的左儿子;压缩和哈夫曼树;4.5.1 文件编码;;;;4.5.2 扩充二叉树;;定义4.10 扩充二叉树的外通路长度定义为从根到每个外结点的路径长度之和，内通路长度定义为从根到每个内结点的路径长度之和。;定义4.11 给扩充二叉树中n个外结点赋上一个实数，称为该结点的权。树的加权外通路长度定义为WPL： ;加权外通路长度分别是4*2+2*3+3*3+11*1=343*2+4*3+11*3+2*1=53 2*2+11*2+3*2+4*2=40;最优二叉树;哈夫曼树与哈夫曼编码;哈夫曼算法基本思想; [例]: F={7},{5},{2},{4} ;文件编码;;哈夫曼编码;[例] 哈夫曼编码 报文：CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }， 各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 } ;在构造哈夫曼树的过程中，没有一片树叶是其他树叶的祖先，所以每个叶结点对应的编码不可能是其他叶结点对应的编码的前缀，由此可知哈夫曼编码是二进制的前缀码。 哈夫曼编码是否唯一？;哈夫曼树中每个结点的结构为： 其中，LLINK和RLINK为链接域，INFO为信息域，Weight为该结点的权值。;Huffman算法;算法Huffman(H, m) Huffman1. [初始化] FOR i?1 TO m DO LLINK(H[i]) ? RLINK(H[i]) ? Λ. Huffman2. [组合过程] FOR i?1 TO m-1 DO ( t AVAIL. P1 ? H[i]. P2 ? H[i+1]. Weight(t) ? Weight(P1 ) ? Weight(P2 ). LLINK(t) ? P1 . RLINK(t) ? P2 .; p ? t . /*把新结点p插入到数组H中H[j]位置*/ j ? i ? 2 . WHILE Weight(p)Weight(H[j]) DO ( H[j-1] ? H[j] . j ? j ? 1. ) H[j-1] ? p. )?;编码：依次将数据文件中的字符按哈夫曼树转换成哈夫曼编码。 解码：依次读入文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向其左孩子，否则走向其右孩子，到达某一叶结点时，便可以译出相应的字符。