第10章 非线性结构

1、第十章第十章 非线性结构非线性结构 本章内容（树形结构）本章内容（树形结构） 树的基本概念 二叉树的基本概念和性质 二叉树的存储结构 二叉树的遍历 树、森林与二叉树的转换 哈夫曼树 树的基本概念树的基本概念 1. 树的特点树的特点 2. 树的定义树的定义 树树是是n(n0)个数据元素的有限集合。它满足以下两个数据元素的有限集合。它满足以下两 个条件：个条件： 有且仅有一个特定的称为根的元素；有且仅有一个特定的称为根的元素； 其余元素分为（其余元素分为（ 0）个互不相交的有限集）个互不相交的有限集 合合1、2、，其中每个集合又都是一棵树并、，其中每个集合又都是一棵树并 称其为根的称其为根的子树子

2、树。 树形结构是一类非常重要的树形结构是一类非常重要的 非线性结构，适合于描述数据元非线性结构，适合于描述数据元 素之间的层次关系素之间的层次关系 树的常用术语举例树的常用术语举例 是的是的双亲双亲，是的，是的子女子女，是从到的，是从到的边边。 l 、互为、互为兄弟兄弟，而和不是兄弟，而和不是兄弟 。 l ADIN是从结点到结点的一条是从结点到结点的一条路径路径，其，其长度长度为为 。 层数层数为的结点有，为的结点有，层数层数为的结点有、为的结点有、 。 树的深度树的深度为为 。 、的、的度度数分别为、数分别为、0；树的度数树的度数为为 。 、都是、都是树叶树叶，其余结点都是，其余结点都是分支

3、结点分支结点 。 森 林 双亲、子女、边双亲、子女、边:若结点是结点若结点是结点 的一棵子树的根，则称做的一棵子树的根，则称做 的的“双亲双亲”; 称做的称做的“子女子女 ”； 有序对，称做从到有序对，称做从到 的的“边边” 。 兄弟兄弟：具有同一双亲的结点具有同一双亲的结点 。 路径、路径长度路径、路径长度：若树中存在若树中存在 着一个结点的序列着一个结点的序列12j ，使，使ki是是ki+1（）的双）的双 亲，则称该结点序列为从亲，则称该结点序列为从k1到到kj 的一条路径；的一条路径；路径长度路径长度等于等于 -，它是该路径所经过的边，它是该路径所经过的边 的数目的数目 。 结点的层数结

4、点的层数：根结点层数为根结点层数为 ，其余结点层数等于其双亲结，其余结点层数等于其双亲结 点层数加点层数加 。 树的深度（高度）树的深度（高度）：即树中层数即树中层数 最大的结点的层数最大的结点的层数 。 结点的度数、树的度数结点的度数、树的度数：一个结一个结 点子女的个数称为该结点的点子女的个数称为该结点的“度度 数数”。 树中度数最大的结点的度数叫做树中度数最大的结点的度数叫做 “树的度数树的度数” 。 树叶、分支结点树叶、分支结点：度数为度数为0的结的结 点叫做点叫做“树叶树叶” ；度数大于；度数大于0的的 结点叫做结点叫做“分支结点分支结点”或或“内内 结点结点” 。 森林森林：（0）

5、棵互不相交）棵互不相交 的树的集合称为森林的树的集合称为森林 。 二叉树的基本概念二叉树的基本概念 二叉树二叉树是（是（0）个结点的有限集合。它或者是空集）个结点的有限集合。它或者是空集 （0），或者由一个根结点及两棵互不相交的、分别称为这），或者由一个根结点及两棵互不相交的、分别称为这 个根的左子树和右子树的二叉树组成。个根的左子树和右子树的二叉树组成。 1.二叉二叉树的定义树的定义 2. 二叉树五种基本形态二叉树五种基本形态 二叉树可以是空，而树不能为空。二叉树可以是空，而树不能为空。 二叉树中任意结点的度数不超过二叉树中任意结点的度数不超过2，而树无此限制。，而树无此限制。 二叉树的子树

6、有左、右之分，树的子树是相同的。二叉树的子树有左、右之分，树的子树是相同的。 3.树和二叉树的差别树和二叉树的差别 二叉树的性质二叉树的性质 性质性质 二叉树第层上的结点数目最多为二叉树第层上的结点数目最多为2i（ 0）。）。 性质性质 深度为的二叉树至多有深度为的二叉树至多有2k+1-1个结点（个结点（ 0）。）。 性质性质 在任意一棵二叉树中，若终端结点的个数为在任意一棵二叉树中，若终端结点的个数为n0、度数为的、度数为的 结结 点的个数为点的个数为n2，则，则n0=n2+1。 1. 二叉树的性质二叉树的性质 2. 两种特殊的二叉树两种特殊的二叉树 满二叉树满二叉树 完全二叉树完全二叉树

7、完全二叉树性质完全二叉树性质 性质性质4 具有个结点的完全二叉树的深度为具有个结点的完全二叉树的深度为 log2n 性质性质5 若对一棵有个结点的完全二叉树，按自顶向下、同层由左到右顺序依次若对一棵有个结点的完全二叉树，按自顶向下、同层由左到右顺序依次 为其每个结点从为其每个结点从0开始编号，则对编号为的结点开始编号，则对编号为的结点ki（0 n-1）则有：）则有： 若若 0，则，则ki双亲结点的编号为双亲结点的编号为 (i-1)/2 若若= 0，则，则ki是根结点。是根结点。 若若2i+1n，则，则ki左子女结点的编号是左子女结点的编号是2i+1，否则，否则ki无左子女。无左子女。 若若2i

8、+2n，则，则ki右子女结点的编号为右子女结点的编号为2i+2，否则，否则ki无右子女。无右子女。 二叉树的存储结构二叉树的存储结构 对完全二叉树，利用性质对完全二叉树，利用性质5，将其所有结点按编号顺序依次存储在一维数组里。，将其所有结点按编号顺序依次存储在一维数组里。 对一般二叉树，需要加上一些并不存在的对一般二叉树，需要加上一些并不存在的“虚结点虚结点”，转换为完全二叉树的形式，转换为完全二叉树的形式 。 1. 顺序存储结构顺序存储结构 完全二叉树完全二叉树 一般的二叉树一般的二叉树 二叉树的存储结构二叉树的存储结构 2. 链式存储结构链式存储结构 链式存储时结点的结构链式存储时结点的结

9、构 二叉树的遍历二叉树的遍历 先序遍历先序遍历 若二叉树非空，访问根结点，先序遍历左子树，先序遍历右子树若二叉树非空，访问根结点，先序遍历左子树，先序遍历右子树 中序遍历中序遍历 若二叉树非空，中序遍历左子树，访问根结点，中序遍历右子树若二叉树非空，中序遍历左子树，访问根结点，中序遍历右子树 后序遍历后序遍历 若二叉树非空，后序遍历左子树，后序遍历右子树，访问根结点若二叉树非空，后序遍历左子树，后序遍历右子树，访问根结点 层次遍历层次遍历 按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点 先序访问序列先序访问序列 ： 中序访问

10、序列中序访问序列 ： 后序访问序列后序访问序列 ： 层次访问序列层次访问序列 ： GDEBFCA ABDGECF DGBEAFC ABCDEFG 如何根据遍历序列得到一颗二叉树？如何根据遍历序列得到一颗二叉树？ n由先序遍历和中序遍历序列，可以得出该二叉树的形态由先序遍历和中序遍历序列，可以得出该二叉树的形态 n由后序遍历和中序遍历序列，可以得出该二叉树的形态由后序遍历和中序遍历序列，可以得出该二叉树的形态 n由层序遍历和中序遍历序列，可以得出该二叉树的形态由层序遍历和中序遍历序列，可以得出该二叉树的形态 n其他情况下，其他情况下，不能不能得出该二叉树的形态。如，由先序遍历和得出该二叉树的形态

11、。如，由先序遍历和 后序遍历序列，后序遍历序列，不能不能得出该二叉树的形态得出该二叉树的形态 先序遍历序列：先序遍历序列： 中序遍历序列：中序遍历序列： ABDGECF DGBEAFC 例：例： 树、森林与二叉树的转换树、森林与二叉树的转换 将树转换成二叉树将树转换成二叉树： 在所有的兄弟之间加一条连线；在所有的兄弟之间加一条连线； 对每个结点，除了保留与最左边子女的连线外，去掉与其他对每个结点，除了保留与最左边子女的连线外，去掉与其他 子女连线；子女连线； 将保留下来的边作为左子树的边，兄弟间的连线作为右子树将保留下来的边作为左子树的边，兄弟间的连线作为右子树 的边。的边。 树、森林到二叉树

12、的转换树、森林到二叉树的转换 树、森林与二叉树的转换树、森林与二叉树的转换 将一个森林转换成二叉树：将一个森林转换成二叉树： 先将森林中的每一棵树变为二叉树，然后将各二叉树的根结先将森林中的每一棵树变为二叉树，然后将各二叉树的根结 点看成兄弟，用线把它们连到一起，经整理后可得到相应的二点看成兄弟，用线把它们连到一起，经整理后可得到相应的二 叉树。叉树。 树、森林与二叉树的转换树、森林与二叉树的转换 （续）（续） 若结点是其双亲的左子女，则把的右子女、右子女的若结点是其双亲的左子女，则把的右子女、右子女的 右子女右子女都与连线，最后去掉所有双亲到右子女的连线。都与连线，最后去掉所有双亲到右子女的

13、连线。 二叉树到树、森林的转换二叉树到树、森林的转换 哈夫曼树基本概念哈夫曼树基本概念 扩充二叉树的定义：扩充二叉树的定义： 假设假设W0，W1，Wn-1是个实数的集合，是个实数的集合， 其中其中Wi0（0-）。若是一棵有个叶结点）。若是一棵有个叶结点 的二叉树，而且将的二叉树，而且将W0，W1，Wn-1分别赋给的分别赋给的 个叶结点作为它们的权，则称是权值为个叶结点作为它们的权，则称是权值为W0，W1， ，Wn-1的的扩充二叉树扩充二叉树。带有权值的叶结点叫做扩充二叉。带有权值的叶结点叫做扩充二叉 树的树的外结点外结点，其余的分支结点叫做，其余的分支结点叫做内结点内结点。 哈夫曼树基本概念哈

14、夫曼树基本概念 例如：权值集合例如：权值集合2，4，6，8，则可构造出以下扩充，则可构造出以下扩充 二叉树。二叉树。 哈夫曼树基本概念哈夫曼树基本概念 WPL= 其中，为外结点数，其中，为外结点数，Wi为外结点所带的权值；为外结点所带的权值；li为为 从根结点到外结点的路径长度。从根结点到外结点的路径长度。 i n i l 1 0 i W (a) WPL=40 (b) WPL=50(c) WPL=38 2扩充二叉树的带权路径长度扩充二叉树的带权路径长度（）（） 哈夫曼树基本概念哈夫曼树基本概念 （续）（续） 3最优二叉树最优二叉树 通常，把权值取为通常，把权值取为W0，W1，Wn-1的所有扩的

15、所有扩 充二叉树中为最小的扩充二叉树称为充二叉树中为最小的扩充二叉树称为最优二叉树最优二叉树。 4哈夫曼树哈夫曼树 利用哈夫曼提出的方法构造出的最优二叉树称为利用哈夫曼提出的方法构造出的最优二叉树称为哈夫哈夫 曼树曼树。 哈夫曼树基本概念哈夫曼树基本概念 （续）（续） 5哈夫曼树构造方法哈夫曼树构造方法 由给定的个权值由给定的个权值W0，W1，Wn-1构造含有棵构造含有棵 扩充二叉树的森林，森林中的每棵二叉树都只有一个根结扩充二叉树的森林，森林中的每棵二叉树都只有一个根结 点，且每个根结点都取一个各不相同的点，且每个根结点都取一个各不相同的Wi作为权值；作为权值； 用森林中根结点的权值为最小和

16、次小的两棵二叉树作为用森林中根结点的权值为最小和次小的两棵二叉树作为 左、右子树构造出一棵新的二叉树，并将新二叉树的根结点左、右子树构造出一棵新的二叉树，并将新二叉树的根结点 的权值取为左、右子树根结点权值之和；的权值取为左、右子树根结点权值之和； 从森林中删去作为新二叉树左、右子树的两棵二叉树，从森林中删去作为新二叉树左、右子树的两棵二叉树， 将新构造的二叉树加入到森林中；将新构造的二叉树加入到森林中； 重复步骤重复步骤和和，直到中仅剩下一棵二叉树为止。，直到中仅剩下一棵二叉树为止。 哈夫曼树的构造哈夫曼树的构造 问题问题 ASCII编码是等长编码编码是等长编码 如果字符X不常用，为什么还用

17、同样的长 度对它进行编码呢？ 如：如： a：01000001 b： 01000010 Huffman Huffman编码就是一种可变长度的编码，广泛广泛 用于各种数据压缩技术中。用于各种数据压缩技术中。 哈夫曼树的应用哈夫曼树的应用 哈夫曼编码哈夫曼编码 例例 设电文字符集为设电文字符集为 a，b，c，d，e，f ，各字符发送频率是，各字符发送频率是 6，2，3，3，4，9 ，要求用，要求用0、1为各个字符进行编码，使报为各个字符进行编码，使报 文总长度最短。文总长度最短。 各字符的哈夫曼编码是各字符的哈夫曼编码是 a：01 b：000 c：001 d：100 e：101 f：11 以字符发送频率为权值构造哈夫曼树以字符发送频率为权值构造哈夫曼树 哈夫曼哈夫曼编码的特点编码的特点 霍夫曼编码的思想是，对于出现频率高的字符，霍夫曼编码