第10章非线性结构.

第十章非线性结构本章内容（树形结构）树的基本概念二叉树的基本概念和性质二叉树的存储结构二叉树的遍历树、森林与二叉树的转换哈夫曼树树的基本概念1.树的特点2.树的定义树是n(n0)个数据元素的有限集合Ｔ。它满足以下两个条件：②其余元素分为ｍ（ｍ≥0）个互不相交的有限集合Ｔ1、Ｔ2、……、Ｔｍ，其中每个集合又都是一棵树并称其为根的子树。树形结构是一类非常重要的非线性结构，适合于描述数据元素之间的层次关系树的常用术语举例Ｃ是Ｇ的双亲，Ｇ是Ｃ的子女，〈Ｃ，Ｇ〉是从Ｃ到Ｇ的边。Ｂ、Ｃ、Ｄ互为兄弟，而Ｆ和Ｇ不是兄弟。ADIN是从结点Ａ到结点Ｎ的一条路径，其长度为３。层数为０的结点有Ａ，层数为１的结点有Ｂ、Ｃ、Ｄ。树的深度为３。Ａ、Ｃ、Ｅ、Ｊ的度数分别为３、１、２、0；树的度数为３。Ｋ、Ｌ、Ｆ、Ｍ、Ｈ、Ｎ、Ｊ都是树叶，其余结点都是分支结点。森林双亲、子女、边:若结点ｙ是结点ｘ的一棵子树的根，则ｘ称做ｙ的“双亲”;ｙ称做ｘ的“子女”；有序对〈ｘ，ｙ〉称做从ｘ到ｙ的“边”。兄弟：具有同一双亲的结点。路径、路径长度：若树中存在着一个结点的序列ｋ1ｋ2……ｋj，使ki是ki+1（１≤ｉ＜ｊ）的双亲，则称该结点序列为从k1到kj的一条路径；路径长度等于ｊ-１，它是该路径所经过的边的数目。结点的层数：根结点层数为０，其余结点层数等于其双亲结点层数加１。树的深度（高度）：即树中层数最大的结点的层数。结点的度数、树的度数：一个结点子女的个数称为该结点的“度数”。树中度数最大的结点的度数叫做“树的度数”。树叶、分支结点：度数为0的结点叫做“树叶”；度数大于0的结点叫做“分支结点”或“内结点”。森林：ｍ（ｍ≥0）棵互不相交的树的集合称为森林。二叉树的基本概念二叉树是ｎ（ｎ≥0）个结点的有限集合。它或者是空集（ｎ＝0），或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。1.二叉树的定义Φ2.二叉树五种基本形态二叉树可以是空，而树不能为空。二叉树中任意结点的度数不超过2，而树无此限制。•二叉树的子树有左、右之分，树的子树是相同的。3.树和二叉树的差别二叉树的性质性质１二叉树第ｉ层上的结点数目最多为2i（ｉ≥0）。性质２深度为ｋ的二叉树至多有2k+1-1个结点（ｋ≥0）。性质３在任意一棵二叉树中，若终端结点的个数为n0、度数为２的结点的个数为n2，则n0=n2+1。1.二叉树的性质2.两种特殊的二叉树满二叉树完全二叉树完全二叉树性质性质4具有ｎ个结点的完全二叉树的深度为log2n性质5若对一棵有ｎ个结点的完全二叉树，按自顶向下、同层由左到右顺序依次为其每个结点从0开始编号，则对编号为ｉ的结点ki（0≤ｉ≤n-1）则有：①若ｉ0，则ki双亲结点的编号为(i-1)/2②若ｉ=0，则ki是根结点。③若2i+1n，则ki左子女结点的编号是2i+1，否则ki无左子女。④若2i+2n，则ki右子女结点的编号为2i+2，否则ki无右子女。二叉树的存储结构对完全二叉树，利用性质5，将其所有结点按编号顺序依次存储在一维数组里。对一般二叉树，需要加上一些并不存在的“虚结点”，转换为完全二叉树的形式。1.顺序存储结构完全二叉树一般的二叉树二叉树的存储结构2.链式存储结构二叉树的遍历先序遍历若二叉树非空，访问根结点，先序遍历左子树，先序遍历右子树中序遍历若二叉树非空，中序遍历左子树，访问根结点，中序遍历右子树后序遍历若二叉树非空，后序遍历左子树，后序遍历右子树，访问根结点层次遍历按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点先序访问序列：中序访问序列：后序访问序列：层次访问序列：GDEBFCAABDGECFDGBEAFCABCDEFG如何根据遍历序列得到一颗二叉树？由先序遍历和中序遍历序列，可以得出该二叉树的形态由后序遍历和中序遍历序列，可以得出该二叉树的形态由层序遍历和中序遍历序列，可以得出该二叉树的形态其他情况下，不能得出该二叉树的形态。如，由先序遍历和后序遍历序列，不能得出该二叉树的形态先序遍历序列：中序遍历序列：ABDGECFDGBEAFC例：树、森林与二叉树的转换将树转换成二叉树：①在所有的兄弟之间加一条连线；②对每个结点，除了保留与最左边子女的连线外，去掉与其他子女连线；③将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边。树、森林到二叉树的转换树、森林与二叉树的转换将一个森林转换成二叉树：先将森林中的每一棵树变为二叉树，然后将各二叉树的根结点看成兄弟，用线把它们连到一起，经整理后可得到相应的二叉树。树、森林与二叉树的转换（续）若结点ｘ是其双亲ｙ的左子女，则把ｘ的右子女、右子女的右子女……都与ｙ连线，最后去掉所有双亲到右子女的连线。二叉树到树、森林的转换哈夫曼树基本概念１．扩充二叉树的定义：假设｛W0，W1，…，Wn-1｝是ｎ个实数的集合，其中Wi≥0（0≤ｉ≤ｎ-１）。若Ｔ是一棵有ｎ个叶结点的二叉树，而且将W0，W1，…，Wn-1分别赋给Ｔ的ｎ个叶结点作为它们的权，则称Ｔ是权值为W0，W1，…，Wn-1的扩充二叉树。带有权值的叶结点叫做扩充二叉树的外结点，其余的分支结点叫做内结点。哈夫曼树基本概念例如：权值集合{2，4，6，8}，则可构造出以下扩充二叉树。哈夫曼树基本概念WPL=其中，ｎ为外结点数，Wi为外结点ｉ所带的权值；li为从根结点到外结点ｉ的路径长度。inil10iW(a)WPL=40(b)WPL=50(c)WPL=382．扩充二叉树的带权路径长度（ＷＰＬ）哈夫曼树基本概念（续）3．最优二叉树通常，把权值取为｛W0，W1，…，Wn-1｝的所有扩充二叉树中ＷＰＬ为最小的扩充二叉树称为最优二叉树。4．哈夫曼树利用哈夫曼提出的方法构造出的最优二叉树称为哈夫曼树。哈夫曼树基本概念（续）5．哈夫曼树构造方法①由给定的ｎ个权值｛W0，W1，…，Wn-1｝构造含有ｎ棵扩充二叉树的森林Ｆ，森林中的每棵二叉树都只有一个根结点，且每个根结点都取一个各不相同的Wi作为权值；②用森林Ｆ中根结点的权值为最小和次小的两棵二叉树作为左、右子树构造出一棵新的二叉树，并将新二叉树的根结点的权值取为左、右子树根结点权值之和；③从森林Ｆ中删去作为新二叉树左、右子树的两棵二叉树，将新构造的二叉树加入到森林Ｆ中；④哈夫曼树的构造问题ASCII编码是等长编码如果字符X不常用，为什么还用同样的长度对它进行编码呢？如：a：01000001b：01000010Huffman编码Huffman编码就是一种可变长度的编码，广泛用于各种数据压缩技术中。哈夫曼树的应用哈夫曼编码例设电文字符集为{a，b，c，d，e，f}，各字符发送频率是{6，2，3，3，4，9}，要求用0、1为各个字符进行编码，使报文总长度最短。各字符的哈夫曼编码是a：01b：000c：001d：100e：101f：11以字符发送频率为权值构造哈夫曼树哈夫曼编码的特点霍夫曼编码的思想是，对于出现频率高的字符，用较少的位数表示，而对于出现频率低的字符，用稍多的位数表示，希望在总长度上达到最短。任何一个字符的编码不能是另一个字符的前缀。例如：以下编码有二义性：a:0b:1c:010010可被解释为：aaba或aca霍夫曼编码是一种不等长的编码，广泛用于各种数据压缩技术中。