第5章树和二叉树f.ppt
《第5章树和二叉树f.ppt》由会员分享,可在线阅读,更多相关《第5章树和二叉树f.ppt(200页珍藏版)》请在三一文库上搜索。
1、树的逻辑结构 树的存储结构 二叉树的逻辑结构 二叉树的存储结构及实现 树、森林与二叉树的转换 哈夫曼树,第 5 章 树和二叉树,本章的主要内容是,树的定义,树:n(n0)个结点的有限集合。 当n0时,称为空树; 任意一棵非空树满足以下条件: 有且仅有一个特定的称为根的结点; 当n1时,除根结点之外的其余结点被分成m(m0)个互不相交的有限集合T1,T2, ,Tm,其中每个集合又是一棵树,并称为这个根结点的子树。,5.1 树的逻辑结构,树的定义是采用递归方法,(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构,5.1 树的逻辑结构,树的定义,树的应用举例文件结构,5.1 树的逻辑结构,树
2、的基本术语,结点的度:结点所拥有的子树的个数。 树的度:树中各结点度的最大值。,5.1 树的逻辑结构,5.1 树的逻辑结构,叶子结点:度为0的结点,也称为终端结点。 分支结点:度不为0的结点,也称为非终端结点。,树的基本术语,孩子、双亲:树中某结点子树的根结点称为这个结点的孩子结点,这个结点称为它孩子结点的双亲结点; 兄弟:具有同一个双亲的孩子结点互称为兄弟。,5.1 树的逻辑结构,树的基本术语,路径:如果树的结点序列n1, n2, , nk有如下关系:结点ni是ni+1的双亲(1=ik),则把n1, n2, , nk称为一条由n1至nk的路径;路径上经过的边的个数称为路径长度。,5.1 树的
3、逻辑结构,树的基本术语,祖先、子孙:在树中,如果有一条路径从结点x到结点y,那么x就称为y的祖先,而y称为x的子孙。,5.1 树的逻辑结构,树的基本术语,结点所在层数:根结点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。 树的深度:树中所有结点的最大层数,也称高度。,5.1 树的逻辑结构,树的基本术语,层序编号:将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,5.1 树的逻辑结构,树的基本术语,有序树、无序树:如果一棵树中结点的各子树从左到右是有次序的,称这棵树为有序树;反之,称为无序树。,数据结构中讨论的一般都是有序树,5.1 树
4、的逻辑结构,树的基本术语,森林:m (m0)棵互不相交的树的集合。,5.1 树的逻辑结构,树的基本术语,同构:对两棵树,若通过对结点适当地重命名,就可以使这两棵树完全相等(结点对应相等,结点对应关系也相等),则称这两棵树同构。,5.1 树的逻辑结构,树的基本术语,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,5.1 树的逻辑结构,树的遍历操作,树的遍历:从根结点出发,按照某种次序访问树中所有结点,使得每个结点被访问一次且仅被访问一次。,如何理解访问?,抽象操作,可以是对结点进行的各种处理,这里简化为输出结点的数
5、据。,如何理解次序?,树通常有前序(根)遍历、后序(根)遍历和层序(次)遍历三种方式。,5.1 树的逻辑结构,树结构(非线性结构)线性结构。,遍历的实质?,前序遍历,树的前序遍历操作定义为: 若树为空,则空操作返回;否则 访问根结点; 按照从左到右的顺序前序遍历根结点的每一棵子树。,5.1 树的逻辑结构,前序遍历序列: A B D E H I F C G,后序遍历,树的后序遍历操作定义为: 若树为空,则空操作返回;否则 按照从左到右的顺序后序遍历根结点的每一棵子树; 访问根结点。,5.1 树的逻辑结构,后序遍历序列: D H I E F B G C A,层序遍历,树的层序遍历操作定义为: 从树
6、的第一层(即根结点)开始,自上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。,5.1 树的逻辑结构,层序遍历序列: A B C D E F G H I,5.2 树的存储结构,实现树的存储结构,关键是什么?,树中结点之间的逻辑关系是什么?,一对多的关系 存储结构的关键:如何表示结点的双亲和孩子,如何表示树中结点之间的逻辑关系。,双亲表示法,基本思想: 用一维数组来存储树的各个结点(一般按层序存储), 数组中的一个元素对应树中的一个结点, 每个结点记录两类信息:结点的数据信息以及该结点的双亲在数组中的下标。,5.2 树的存储结构,template struct PNode T data
7、; /数据域 int parent; /指针域,双亲在数组中的下标 ; PNode TreeMaxSize;,5.2 树的存储结构,树的双亲表示法实质上是一个静态链表。,双亲表示法中结点数据类型的定义,下标 data parent,5.2 树的存储结构,如何查找双亲结点?时间性能?,双亲表示法,5.2 树的存储结构,双亲表示法,如何查找孩子结点?时间性能?,下标 data parent,firstchild,下标 data parent,rightsib,5.2 树的存储结构,双亲表示法,如何查找兄弟结点?时间性能?,链表中的每个结点包括一个数据域和多个指针域,每个指针域指向该结点的一个孩子结
8、点。,如何确定链表中的结点结构?,5.2 树的存储结构,孩子表示法-多重链表表示法,5.2 树的存储结构,缺点:浪费空间,链表中的每个结点包括一个数据域和多个指针域,每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构?,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,基本思想: 把每个结点的
9、孩子排列起来,看成是一个线性表,且以单链表存储,则n个结点共有 n 个孩子链表。 这 n 个单链表共有 n 个头指针,这 n 个头指针又组成了一个线性表。 为了便于进行查找采用顺序存储。 最后,将存放 n 个头指针的数组和存放n个结点的数组结合起来,构成孩子链表的表头数组。,5.2 树的存储结构,特点:将每个结点的所有孩子放在一起,构成线性表。,孩子表示法-孩子链表表示法,0 1 2 3 4 5 6 7 8,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,struct CTNode int child; CTNode *next; ;,5.2 树
10、的存储结构,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 树的存储结构,如何查找双亲结点?,0 1 2 3 4 5 6 7 8,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,如何查找兄弟结点?,双亲孩子表
11、示法,孩子兄弟表示法,5.2 树的存储结构,某结点的第一个孩子是惟一的 某结点的右兄弟是惟一的,template struct TNode T data; TNode *firstchild, *rightsib; ;,5.2 树的存储结构,结点结构,data:数据域,存储该结点的数据信息; firstchild:指针域,指向该结点第一个孩子; rightsib:指针域,指向该结点的右兄弟结点。,孩子兄弟表示法,5.2 树的存储结构,孩子兄弟表示法,5.2 树的存储结构,孩子兄弟表示法,如何查找孩子结点?,树的存储结构小结,双亲表示法 孩子表示法:多重链表表示法、孩子链表表示法 双亲孩子表示法
12、 孩子兄弟表示法 顺序存储:本质上是静态指针 双亲表示法 双亲孩子表示法 链式存储: 多重链表示法 孩子链表表示法 孩子兄弟表示法,二叉树的定义,二叉树是n(n0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.3 二叉树的逻辑结构,结构简单,适合于计算机处理 问题转化:将树转换为二叉树,从而利用二叉树解决树的有关问题。,研究二叉树的意义?,二叉树的特点:, 每个结点最多有两棵子树; 二叉树是有序的,其次序不能任意颠倒。,5.3 二叉树的逻辑结构,注意:二叉树和树是两种树结构。,二叉树的基本形态,5.3 二
13、叉树的逻辑结构,5.3 二叉树的逻辑结构,具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。,特殊的二叉树,斜树 1 .所有结点都只有左子树的二叉树称为左斜树; 2 .所有结点都只有右子树的二叉树称为右斜树; 3.左斜树和右斜树统称为斜树。,1. 在斜树中,每一层只有一个结点; 2.斜树的结点个数与其深度相同。,5.3 二叉树的逻辑结构,斜树的特点:,满二叉树 在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上。,满二叉树的特点:,叶子只能出现在最下一层; 只有度为0和度为2的结点。,5.3 二叉树的逻辑结构,特殊的二叉树,满二叉树,5.3 二叉
14、树的逻辑结构,不是满二叉树,虽然所有分支结点都有左右子树,但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多,特殊的二叉树,完全二叉树 对一棵具有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不是同一个
15、结点,特殊的二叉树,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个
16、孩子,故在第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 在二叉树中,除了根结点外,其余结点都有唯一
17、的一个分枝进入,由于这些分枝是由度为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 2
18、k,最少结点数,最多结点数,完全二叉树的基本性质,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
19、 二叉树的逻辑结构,完全二叉树的基本性质,对一棵具有n个结点的完全二叉树中从1开始按层序编号,则 结点i的双亲结点为 i/2; 结点i的左孩子为2i; 结点i的右孩子为2i1。,5.3 二叉树的逻辑结构,性质5表明,在完全二叉树中,结点的层序编号反映了结点之间的逻辑关系。,二叉树的遍历操作,二叉树的遍历是指从根结点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的目的?,5.3 二叉树的逻辑结构,二叉树的遍历方式: DLR、LDR、LRD、 DRL、RDL、RLD,如果限定先左后右,则二叉树遍历方式有三种: 前序:DLR 中序:LDR 后序:LR
20、D,层序遍历:按二叉树的层序编号的次序访问各结点。,5.3 二叉树的逻辑结构,考虑二叉树的组成:,前序(根)遍历 若二叉树为空,则空操作返回;否则: 访问根结点; 前序遍历根结点的左子树; 前序遍历根结点的右子树。,5.3 二叉树的逻辑结构,前序遍历序列:A B D G C E F,二叉树的遍历操作,中序(根)遍历 若二叉树为空,则空操作返回;否则: 中序遍历根结点的左子树; 访问根结点; 中序遍历根结点的右子树。,5.3 二叉树的逻辑结构,中序遍历序列:D G B A E C F,二叉树的遍历操作,后序(根)遍历 若二叉树为空,则空操作返回;否则: 后序遍历根结点的左子树; 后序遍历根结点的
21、右子树。 访问根结点;,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 二
22、叉树的逻辑结构,若已知一棵二叉树的前序(或中序,或后序,或层序)序列,能否唯一确定这棵二叉树呢?,例:已知前序序列为ABC,则可能的二叉树有5种。,二叉树的遍历操作,5.3 二叉树的逻辑结构,例:已知前序遍历序列为ABC,后序遍历序列为CBA,则下列二叉树都满足条件。,若已知一棵二叉树的前序序列和后序序列,能否唯一确定这棵二叉树呢?,二叉树的遍历操作,若已知一棵二叉树的前序序列和中序序列,能否唯一确定这棵二叉树呢?怎样确定?,例如:已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI,如何构造该二叉树呢?,5.3 二叉树的逻辑结构,二叉树的遍历操作,前序:A
23、 B C D E F G H I中序:B C A E D G H F I,前序:B C 中序:B C,前序: D E F G H I 中序: E D G H F I,前序:F G H I 中序:G H F I,前序: D E F G H I 中序: E D G H F I,顺序存储结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置(下标)应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系 。,5.4 二叉树的存储结构及实现,完全二叉树的顺序存储,5.4 二叉树的存储结构
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉
链接地址:https://www.31doc.com/p-3431054.html