数据结构（c清华版）课件

数据结构（C+版）二,第四章 广义线性表,本章的基本内容是： 数组的逻辑结构特征 数组的存储方式及寻址方法 特殊矩阵和稀疏矩阵的压缩存储方法 广义表的基本概念和存储结构,第四章 广义线性表,线性表具有相同类型的数据元素的有限序列。,限制插入、删除位置,线性表具有相同类型的数据元素的有限序列。,限制元素类型为字符,串零个或多个字符组成的有限序列 。,第四章 广义线性表,线性表具有相同类型的数据元素的有限序列。,将元素的类型进行扩充,数组的定义,数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、in称为该元素的下标，并称该数组为 n 维数组。,数组的特点,元素本身可以具有某种结构，属于同一数据类型； 数组是一个具有固定格式和数量的数据集合。,广义线性表多维数组,广义线性表多维数组,a11 a12 a1n a21 a22 a2n am1 am2 amn,A=,例如，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。,数组示例,a11 a12 a1n a21 a22 a2n am1 am2 amn,A=,数组线性表的推广,二维数组是数据元素为线性表的线性表。,广义线性表多维数组,数组的基本操作,广义线性表多维数组,在数组中插入（或）一个元素有意义吗？,将元素 x 插入 到数组中第1行第2列。,删除数组中 第1行第2列元素。,数组的基本操作, 存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的数组元素。 存取和修改操作本质上只对应一种操作寻址,数组应该采用何种方式存储？,数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。,广义线性表多维数组,数组的存储结构与寻址一维数组,设一维数组的下标的范围为闭区间l，h，每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定： Loc(ai)Loc(al)(il)c,广义线性表多维数组,常用的映射方法有两种： 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,广义线性表多维数组,数组的存储结构与寻址二维数组,广义线性表多维数组,l2,h2,l1,h1,(a) 二维数组,aij前面的元素个数 =阴影部分的面积 =整行数每行元素个数+本行中aij前面的元素个数 =(i -l1)(h2 -l21)(j -l2),按行优先存储的寻址,广义线性表多维数组,第l1行,第l1+1行,(i -l1)(h2 -l21)(j -l2)个元素,Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c,按行优先存储的寻址,按列优先存储的寻址方法与此类似。,Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c,广义线性表多维数组,n（n2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址的计算方法。,数组的存储结构与寻址多维数组,矩阵的压缩存储,特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。 稀疏矩阵：矩阵中有很多零元素。,压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零元素不分配存储空间。,特殊矩阵和稀疏矩阵,特殊矩阵的压缩存储对称矩阵,3 6 4 7 8 6 2 8 4 2 4 8 1 6 9 7 4 6 0 5 8 2 9 5 7,A,对称矩阵特点：aij=aji,如何压缩存储？,只存储下三角部分的元素。,矩阵的压缩存储,(a) 下三角矩阵 (b) 存储说明 (c) 计算方法,aij在一维数组中的序号 =阴影部分的面积 = i(i+1)/2+ j+1 一维数组下标从0开始 aij在一维数组中的下标 k= i(i+1)/2+ j,0 i n-1,0 j n-1,aij,对称矩阵的压缩存储,矩阵的压缩存储,对于下三角中的元素aij（ij），在数组SA中的下标k与i、j的关系为：ki(i1)/2j 。 上三角中的元素aij（ij），因为aijaji，则访问和它对应的元素aji即可，即：kj(j1)/2i 。,对称矩阵的压缩存储,矩阵的压缩存储,特殊矩阵的压缩存储三角矩阵,3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7,(a) 下三角矩阵,3 4 8 1 0 c 2 9 4 6 c c 5 7 c c c 0 8 c c c c 7,(b) 上三角矩阵,如何压缩存储？,只存储上三角（或下三角）部分的元素。,矩阵的压缩存储,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,下三角矩阵的压缩存储,矩阵的压缩存储,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,上三角矩阵的压缩存储,矩阵的压缩存储,特殊矩阵的压缩存储对角矩阵,对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。,a00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 a43 a44,A=,矩阵的压缩存储,将带状区 域立起来,对角矩阵的压缩存储,矩阵的压缩存储,按行 存储,元素aij在一维数组中的序号 =2 + 3(i1)+( ji + 2) =2i+ j+1 一维数组下标从0开始 元素aij在一维数组中的下标 =2i+ j,(b) 寻址的计算方法,矩阵的压缩存储,对角矩阵的压缩存储,稀疏矩阵的压缩存储,如何只存储非零元素？,矩阵的压缩存储,注意：稀疏矩阵中的非零元素的分布没有规律。,template struct element int row, col; /行号，列号 T item /非零元素值 ;,将稀疏矩阵中的每个非零元素表示为： (行号，列号，非零元素值)三元组,矩阵的压缩存储,稀疏矩阵的压缩存储,定义三元组：,三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。,矩阵的压缩存储,稀疏矩阵的压缩存储,三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) ),如何存储三元组表？,稀疏矩阵的压缩存储三元组顺序表,采用顺序存储结构存储三元组表,矩阵的压缩存储,三元组顺序表是否 需要预留存储空间？,稀疏矩阵的修改操作,三元组顺序表的插入/删除操作,稀疏矩阵的压缩存储三元组顺序表,采用顺序存储结构存储三元组表,矩阵的压缩存储,7（非零元个数）,是否对应惟一的稀疏矩阵？,存储结构定义： const int MaxTerm=100; template struct SparseMatrix T dataMaxTerm; /存储非零元素 int mu, nu, tu; /行数，列数，非零元个数 ;,矩阵的压缩存储,稀疏矩阵的压缩存储三元组顺序表,三元组顺序表操作转置操作,例：,矩阵的压缩存储,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,三元组顺序表转置算法算法,基本思想：直接取，顺序存。即在A的三元组顺序表中依次找第0列、第1列、直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。,矩阵的压缩存储,矩阵的压缩存储,设置矩阵B的行数、列数、非零元个数,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第0列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第1列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第2列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第3列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第4列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第5列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第6列非零元，顺序存储到矩阵B中,1. 设置转置后矩阵B的行数、列数和非零元个数； 2. 在B中设置初始存储位置pb； 3. for (col=最小列号; col=最大列号; col+) 3.1 在A中查找列号为col的三元组； 3.2 交换其行号和列号，存入B中pb位置； 3.3 pb+；,矩阵的压缩存储,三元组顺序表转置算法伪代码,分析：A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B中后面连续的位置上，那么第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数，以此类推。,基本思想：顺序取，直接存。即在A中依次取三元组，交换其行号和列号放到B 中适当位置。,矩阵的压缩存储,三元组顺序表转置算法算法,如何确定当前从A中取出的三元组在B中的位置？,矩阵的压缩存储,三元组顺序表转置算法算法,第0列第1个非零元素,第0列有2个非零元素,第1列第1个非零元素,引入两个数组作为辅助数据结构： numnu：存储矩阵A中某列的非零元素的个数； cpotnu：初值表示矩阵A中某列的第一个非零元素在B中的位置。,数据结构设计：,num与cpot存在如下递推关系：,矩阵的压缩存储,三元组顺序表转置算法算法,矩阵的压缩存储,根据矩阵A计算num和cpot,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot1,cpot2,cpot3,cpot4 cpot5,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot1,cpot2,cpot4 cpot5,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot1,cpot2,cpot4,cpot5,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot2,cpot4,cpot1,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot2,cpot4,cpot1,cpot1,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot4,cpot1,cpot3,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,5（矩阵的行数）,矩阵的压缩存储,将矩阵A中col列元素存放在B中下标为cpotcol的位置,row col item,0 1 2 3 4 5 6,6（矩阵的行数）,cpot4,cpot1,cpot3,1. 设置转置后矩阵B的行数、列数和非零元素的个数； 2. 计算A中每一列的非零元素个数； 3. 计算A中每一列的第一个非零元素在B中的下标； 4. 依次取A中的每一个非零元素对应的三元组； 4.1 确定该元素在B中的下标pb； 4.2 将该元素的行号列号交换后存入B中pb的位置； 4.3 预置该元素所在列的下一个元素的存放位置；,矩阵的压缩存储,三元组顺序表转置算法伪代码,采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：,row：存储非零元素的行号 col：存储非零元素的列号 item：存储非零元素的值 right：指针域，指向同一行中的下一个三元组 down：指针域，指向同一列中的下一个三元组,矩阵的压缩存储,稀疏矩阵的压缩存储十字链表,矩阵的压缩存储,稀疏矩阵的压缩存储十字链表,广义表：n（n0）个数据元素的有限序列，记作： LS(a1，a2，an) 其中：LS是广义表的名称，ai（1in）是LS的成员（或直接元素），它可以是单个的数据元素，也可以是一个广义表，分别称为LS的单元素（或原子）和子表。,广义线性表广义表,广义表的逻辑结构：直接元素之间是线性关系。,广义表的基本概念,通常用大写字母表示广义表，用小写字母表示单元素。,长度：广义表LS中的直接元素的个数； 深度：广义表LS中括号的最大嵌套层数。 表头：广义表LS非空时，称第一个元素为LS的表头； 表尾：广义表LS中除表头外其余元素组成的广义表。,广义线性表广义表,广义表( )和广义表( )不同？,广义表的基本概念,A ( ) B (e) C (a, (b，c，d) D (A, B, C) E (a, E) F ( ),广义线性表广义表,广义表的示例,长度？深度？表头？表尾？,A ( ) B (e) C (a, (b，c，d) D (A, B, C) E (a, E) F ( ),广义线性表广义表,广义表的图形表示,广义线性表广义表,广义表可以采用顺序存储结构吗？,由于广义表中的数据元素的类型不统一，因此难以采用顺序存储结构来存储。,若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。,采用头尾表示法存储广义表,如何采用链接存储结构存储广义表？,广义表的存储结构头尾表示法,广义线性表广义表,广义表中的数据元素既可以是广义表也可以是单元素,头尾表示法中的结点结构？,表结点存储广义表；元素结点存储单元素,tag：区分表结点和元素结点的标志； hp：指向表头结点的指针； tp：指向表尾结点的指针； data：数据域，存放单元素。,广义表的存储结构头尾表示法,广义线性表广义表,结点结构,enum Elemtag Atom, List; template struct GLNode Elemtag tag; union T data; struct GLNode *hp, *tp; ptr; ; ;,广义线性表广义表,广义表的存储结构头尾表示法,定义结点结构,广义线性表广义表,广义表的存储结构头尾表示法,A ( ) B (e) C (a, (b，c，d),广义线性表广义表,广义表的存储结构头尾表示法,A ( ) B (e) C (a, (b，c，d) D (A, B, C),广义线性表广义表,广义表的存储结构头尾表示法,E (a, E) F ( ),template class Lists public: Lists( ) ; Lists(Lists ls1, Lists ls2); Lists( ); int Length( ); int Depth(GLNode *ls); GLNode *Head( ); GLNode *Tail( ); private: GLNode *ls; ;,广义表类的声明,广义线性表广义表,广义表的操作建立广义表,template Lists:Lists(Lists ls1,Lists ls2) ls = new GLNode ls-tag = 1; ls-ptr.hp = ls1; ls-ptr.tp = ls2; ,广义线性表广义表,广义表的操作求广义表的深度,template int Lists:Depth(GLNode *ls) if (ls=NULL) return 1; if (ls-tag=0) return 0; max=0; p = ls; while (p) dep = Depth(p-ptr.hp); if (depmax) max = dep; p = p-ptr.tp; return max+1; ,广义线性表广义表,第四章 广义线性表,树的逻辑结构 树的存储结构 二叉树的逻辑结构 二叉树的存储结构及实现 树、森林与二叉树的转换 哈夫曼树,第 5 章 树和二叉树,本章的主要内容是,树的定义,树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点； 当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2, ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。,5.1 树的逻辑结构,树的定义是采用递归方法,(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构,5.1 树的逻辑结构,树的定义,树的应用举例文件结构,5.1 树的逻辑结构,树的基本术语,结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。,5.1 树的逻辑结构,5.1 树的逻辑结构,叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。,树的基本术语,孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。,5.1 树的逻辑结构,树的基本术语,路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1, n2, , nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,5.1 树的逻辑结构,树的基本术语,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,5.1 树的逻辑结构,树的基本术语,结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度。,5.1 树的逻辑结构,树的基本术语,层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,5.1 树的逻辑结构,树的基本术语,有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,5.1 树的逻辑结构,树的基本术语,森林：m (m0)棵互不相交的树的集合。,5.1 树的逻辑结构,树的基本术语,同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。,5.1 树的逻辑结构,树的基本术语,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,5.1 树的逻辑结构,树的抽象数据类型定义,ADT Tree Data 树是由一个根结点和若干棵子树构成， 树中结点具有相同数据类型及层次关系 Operation InitTree 前置条件：树不存在 输入：无 功能：初始化一棵树 输出：无 后置条件：构造一个空树,5.1 树的逻辑结构,DestroyTree 前置条件：树已存在 输入：无 功能：销毁一棵树 输出：无 后置条件：释放该树占用的存储空间 Root 前置条件：树已存在 输入：无 功能：求树的根结点 输出：树的根结点的信息 后置条件：树保持不变,树的抽象数据类型定义,5.1 树的逻辑结构,Parent 前置条件：树已存在 输入：结点x 功能：求结点x的双亲 输出：结点x的双亲的信息 后置条件：树保持不变 Depth 前置条件：树已存在 输入：无 功能：求树的深度 输出：树的深度 后置条件：树保持不变,树的抽象数据类型定义,5.1 树的逻辑结构,PreOrder 前置条件：树已存在 输入：无 功能：前序遍历树 输出：树的前序遍历序列 后置条件：树保持不变 PostOrder 前置条件：树已存在 输入：无 功能：后序遍历树 输出：树的后序遍历序列 后置条件：树保持不变 endADT,树的抽象数据类型定义,5.1 树的逻辑结构,树的遍历操作,树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。,如何理解访问?,抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。,如何理解次序?,树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。,5.1 树的逻辑结构,树结构（非线性结构）线性结构。,遍历的实质?,前序遍历,树的前序遍历操作定义为： 若树为空，则空操作返回；否则 访问根结点； 按照从左到右的顺序前序遍历根结点的每一棵子树。,5.1 树的逻辑结构,前序遍历序列： A B D E H I F C G,后序遍历,树的后序遍历操作定义为： 若树为空，则空操作返回；否则 按照从左到右的顺序后序遍历根结点的每一棵子树； 访问根结点。,5.1 树的逻辑结构,后序遍历序列： D H I E F B G C A,层序遍历,树的层序遍历操作定义为： 从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。,5.1 树的逻辑结构,层序遍历序列： A B C D E F G H I,5.2 树的存储结构,实现树的存储结构，关键是什么?,什么是存储结构?,树中结点之间的逻辑关系是什么?,思考问题的出发点：如何表示结点的双亲和孩子,如何表示树中结点之间的逻辑关系。,数据元素以及数据元素之间的逻辑关系在存储器中的表示。,双亲表示法,基本思想：用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。,5.2 树的存储结构,template struct PNode T data; /数据域 int parent; /指针域，双亲在数组中的下标 ;,5.2 树的存储结构,树的双亲表示法实质上是一个静态链表。,双亲表示法,下标 data parent,5.2 树的存储结构,如何查找双亲结点？时间性能？,双亲表示法,5.2 树的存储结构,双亲表示法,如何查找孩子结点？时间性能？,下标 data parent,firstchild,下标 data parent,rightsib,5.2 树的存储结构,双亲表示法,如何查找兄弟结点？时间性能？,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构？,5.2 树的存储结构,孩子链表表示法,5.2 树的存储结构,缺点：浪费空间,A,B,C,D,E,F,G,H,I,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构？,5.2 树的存储结构,孩子链表表示法,方案二： 指针域的个数等于该结点的度,其中：data：数据域，存放该结点的数据信息； degree：度域，存放该结点的度； child1childd：指针域，指向该结点的孩子。,5.2 树的存储结构,缺点：结点结构不一致,A 2,B 3,C 2,E 1,I 0,G 0,H 0,F 0,D 0,孩子链表表示法,基本思想：把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，为了便于进行查找采用顺序存储。最后，将存放 n 个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。,5.2 树的存储结构,如何确定链表中的结点结构？,将结点的所有孩子放在一起，构成线性表。,struct CTNode int child; CTNode *next; ;,5.2 树的存储结构,template struct CBNode T data; CTNode *firstchild; ;,孩子链表表示法,0 1 2 3 4 5 6 7 8,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,如何查找孩子结点？时间性能？,0 1 2 3 4 5 6 7 8,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,如何查找双亲结点？时间性能？,双亲孩子表示法,5.2 树的存储结构,孩子兄弟表示法,5.2 树的存储结构,某结点的第一个孩子是惟一的 某结点的右兄弟是惟一的,template struct TNode T data; TNode *firstchild, *rightsib; ;,5.2 树的存储结构,结点结构,data：数据域，存储该结点的数据信息； firstchild：指针域，指向该结点第一个孩子； rightsib：指针域，指向该结点的右兄弟结点。,孩子兄弟表示法,5.2 树的存储结构,孩子兄弟表示法,如何查找兄弟结点？时间性能？,5.2 树的存储结构,孩子兄弟表示法,如何查找孩子结点？时间性能？,二叉树的定义,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.3 二叉树的逻辑结构,问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。,研究二叉树的意义？,二叉树的特点：, 每个结点最多有两棵子树； 二叉树是有序的，其次序不能任意颠倒。,5.3 二叉树的逻辑结构,注意：二叉树和树是两种树结构。,二叉树的基本形态,5.3 二叉树的逻辑结构,5.3 二叉树的逻辑结构,具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。,特殊的二叉树,斜树 1 .所有结点都只有左子树的二叉树称为左斜树； 2 .所有结点都只有右子树的二叉树称为右斜树； 3.左斜树和右斜树统称为斜树。,1. 在斜树中，每一层只有一个结点； 2.斜树的结点个数与其深度相同。,5.3 二叉树的逻辑结构,斜树的特点：,满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层； 只有度为0和度为2的结点。,5.3 二叉树的逻辑结构,特殊的二叉树,满二叉树,5.3 二叉树的逻辑结构,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多,特殊的二叉树,完全二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,5.3 二叉树的逻辑结构,特殊的二叉树,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,5.3 二叉树的逻辑结构,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,特殊的二叉树,1. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。,完全二叉树的特点,5.3 二叉树的逻辑结构,特殊的二叉树,二叉树的基本性质,性质5-1 二叉树的第i层上最多有2i-1个结点（i1）。,证明：当i=1时，第1层只有一个根结点，而 2i-1=20 =1，结论显然成立。 假定i=k（1ki）时结论成立，即第k层上至多有2k-1个结点， 则 i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即22k-12k。结论成立。,5.3 二叉树的逻辑结构,性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,证明：由性质1可知，深度为k的二叉树中结点个数最多 = =2k-1； 每一层至少要有一个结点，因此深度为k的二叉树， 至少有k个结点。,5.3 二叉树的逻辑结构,二叉树的基本性质,性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0n21。,证明: 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有： nn12n21 因此可以得到：n0n21 。,5.3 二叉树的逻辑结构,二叉树的基本性质,5.3 二叉树的逻辑结构,在有n个结点的满二叉树中，有多少个叶子结点？,二叉树的基本性质,性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0n21。,性质5-4 具有n个结点的完全二叉树的深度为 log2n +1。,5.3 二叉树的逻辑结构,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,最少结点数,最多结点数,完全二叉树的基本性质,5.3 二叉树的逻辑结构,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,完全二叉树的基本性质,性质5-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点（简称为结点i），有： （1）如果i1，则结点i的双亲结点的序号为 i/2；如果i1，则结点i是根结点，无双亲结点。 (2)如果2in，则结点i的左孩子的序号为2i； 如果2in，则结点i无左孩子。 (3)如果2i1n，则结点i的右孩子的序号为2i1；如果2i1n，则结点 i无右孩子。,5.3 二叉树的逻辑结构,完全二叉树的基本性质,对一棵具有n个结点的完全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2； 结点i的左孩子为2i； 结点i的右孩子为2i1。,5.3 二叉树的逻辑结构,性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,完全二叉树的基本性质,二叉树的抽象数据类型定义,ADT BiTree Data 由一个根结点和两棵互不相交的左右子树构成， 结点具有相同数据类型及层次关系 Operation InitBiTree 前置条件：无 输入：无 功能：初始化一棵二叉树 输出：无 后置条件：构造一个空的二叉树,5.3 二叉树的逻辑结构,DestroyBiTree 前置条件：二叉树已存在 输入：无 功能：销毁一棵二叉树 输出：无 后置条件：释放二叉树占用的存储空间 InsertL 前置条件：二叉树已存在 输入：数据值x，指针parent 功能：将数据域为x的结点插入到二叉树中，作为结点parent的左孩子。如果结点parent原来有左孩子，则将结点parent原来的左孩子作为结点x的左孩子 输出：无 后置条件：如果插入成功，得到一个新的二叉树,二叉树的抽象数据类型定义,5.3 二叉树的逻辑结构,DeleteL 前置条件：二叉树已存在 输入：指针parent 功能：在二叉树中删除结点parent的左子树 输出：无 后置条件：如果删除成功，得到一个新的二叉树 Search 前置条件：二叉树已存在 输入：数据值x 功能：在二叉树中查找数据元素x 输出：指向该元素结点的指针 后置条件：二叉树不变,二叉树的抽象数据类型定义,5.3 二叉树的逻辑结构,PreOrder 前置条件：二叉树已存在 输入：无 功能：前序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 InOrder 前置条件：二叉树已存在 输入：无 功能：中序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变,二叉树的抽象数据类型定义,5.3 二叉树的逻辑结构,PostOrder 前置条件：二叉树已存在 输入：无 功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在 输入：无 功能：层序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 endADT,二叉树的抽象数据类型定义,5.3 二叉树的逻辑结构,二叉树的遍历操作,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,5.3 二叉树的逻辑结构,二叉树的遍历方式： DLR、LDR、LRD、 DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种： 前序：DLR 中序：LDR 后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,5.3 二叉树的逻辑结构,考虑二叉树的组成：,前序（根）遍历 若二叉树为空，则空操作返回；否则： 访问根结点； 前序遍历根结点的左子树； 前序遍历根结点的右子树。,5.3 二叉树的逻辑结构,前序遍历序列：A B D G C E F,二叉树的遍历操作,中序（根）遍历 若二叉树为空，则空操作返回；否则： 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。,5.3 二叉树的逻辑结构,中序遍历序列：D G B A E C F,二叉树的遍历操作,后序（根）遍历 若二叉树为空，则空操作返回；否则： 后序遍历根结点的左子树； 后序遍历根结点的右子树。 访问根结点；,5.3 二叉树的逻辑结构,后序遍历序列：G D B E F C A,二叉树的遍历操作,层序遍历 二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,5.3 二叉树的逻辑结构,层序遍历序列：A B C D E F G,二叉树的遍历操作,5.3 二叉树的逻辑结构,-,-,/,+,*,a,b,c,d,e,f,二叉树遍历操作练习,前序遍历结果：- + a * b - c d / e f 中序遍历结果：a + b * c - d - e / f 后序遍历结果：a b c d - * + e f / -,5.3 二叉树的逻辑结构,若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？,例：已知前序序列为ABC，则可能的二叉树有5种。,二叉树的遍历操作,5.3 二叉树的逻辑结构,例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。,若已知一棵二叉树的前序序列和后序序列，能