数据结构树和二叉树ppt课件.ppt
《数据结构树和二叉树ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构树和二叉树ppt课件.ppt(107页珍藏版)》请在三一办公上搜索。
1、,第六章 树和二叉树,第六章 树和二叉树6.1 树的有关概念6.2 二叉树6.3 二叉树的遍历6.4 遍历的应用6.5 * 线索二叉树(简单介绍)6.6 树和森林6.7 哈夫曼树及应用,第六章 树和二叉树,6.1 树的有关概念,1树的定义,定义:树是n个结点的有限集合。在任一棵非空树中: (1)有且仅有一个称为根的结点;。 (2)其余结点可分为m个互不相交的有限集合,而且这些集合中的每一集合本身又是一棵树,称为根的子树。,树是递归结构,在树的定义中又用到了树的概念,树结构 (除了一个称为根的结点外)每个元素都有且仅有一个直接前趋,有且仅有零个或多个直接后继。,6.1 树的有关概念,从逻辑结构看
2、: 1)树中只有根结点没有前趋;2)除根外,其余结点都有且仅一个前趋;3)树的结点,可以有零个或多个后继;4)除根外的其他结点,都存在唯一条从根到该结点的路径;5)树是一种分枝结构,6.1 树的有关概念,2树的应用1)树可表示具有分枝结构关系的对象,例1家族族谱,例2单位行政机构的组织关系、系统功能模块图,6.1 树的有关概念,2)树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系,但是为了便于管理和使用数据,将它们用树的形式来组织。例3 计算机的文件系统 不论是DOS文件系统还是window文件系统,所有的文件是用树的形式来组织的。,6.1 树的有关概念,3 、树的基本术语
3、,1)结点的度:结点所拥有的子树的个数。2)树的度:树中各结点度的最大值。,DA=3,DB=2,DC=1,DG=0,DTree=3,6.1 树的有关概念,3)叶子结点:度为0的结点,也称为终端结点。4)分支结点:度不为0的结点,也称为非终端结点。,叶子结点:K,L,F,G,M,I,J,分支结点:A,B,C,D,E,H,6.1 树的有关概念,5)孩子、双亲:树中结点的子树的根结点称为这个结点的孩子结点,这个结点称为它孩子结点的双亲结点;6)兄弟:具有同一个双亲的孩子结点互称为兄弟。,孩子结点:B,C,D双亲结点:A兄弟结点:E,F,6.1 树的有关概念,7)路径:如果树的结点序列n1, n2,
4、, nk有如下关系:结点ni是ni+1的双亲,则把n1, n2, , nk称为一条由n1至nk的路径;路径上经过的边的个数称为路径长度。,结点序列:nA,nB, nE, nK路经长度=3,6.1 树的有关概念,8)祖先、子孙:在树中,如果有一条路径从结点x到结点y,那么x就称为y的祖先,而y称为x的子孙。,6.1 树的有关概念,9)结点所在层数:根结点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。10)树的深度:树中所有结点的最大层数,也称高度。,6.1 树的有关概念,11)有序树、无序树:如果一棵树中结点的各子树从左到右是有次序的(即不能互换),称这棵树为有序树;反
5、之,称为无序树。,数据结构中讨论的一般都是有序树,6.1 树的有关概念,12)森林:m (m0)棵互不相交的树的集合。,树中每一个结点的子树的集合即为森林。,6.1 树的有关概念,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,6.1 树的有关概念,4、树的基本操作 树的应用很广,应用不同基本操作也不同。下面列举了树的一些基本操作: 1)InitTree( /返回树T的根值,6.1 树的有关概念,8) Value(T, /按某种次序访问树中每个结点,6 2 二 叉 树,树是一种分枝结构的对象,在树的概念中,对每一
6、个结点孩子的个数没有限制,因此树的形态多种多样,本章我们主要讨论一种最简单的树二叉树。,6.2 二 叉 树,一 二叉树的概念1 二叉树的定义二叉树: 或为空树,或由根及两颗不相交的左子树、右子树构成,并且左、右子树本身也是二叉树。,说明:1)二叉树中每个结点最多有两颗子树;二叉树每个结点度小于等于2;2)左、右子树不能颠例有序树;3)二叉树是递归结构,在二叉树的定义中又用到了二叉树的概念;,6.2 二 叉 树,2 二叉树的基本形态,6.2 二 叉 树,二、二叉树性质 性质1 在二叉树的第i 层上最多有2i-1个结点(i=1),证明: 当i=1时,第1层只有一个根结点,结点数=20 =1,结论显
7、然成立。,假设j=i-1时,结论正确,即第j层最多有2i-2,,所以当j=i时,第i层最多有2*2i-2=2i-1;结论正确,6.2 二 叉 树,性质2 一棵深度为k的二叉树中,最多有2k-1个结点,最少有k个结点。,证明:由性质1可知,深度为k的二叉树中结点个数最多= =2k-1;,每一层至少要有一个结点,因此深度为k的二叉树,至少有k个结点。,6.2 二 叉 树,证明: 设n为二叉树的结点总数,n1为二叉树中度为1的结点数,则有: nn0n1n2 在二叉树中,除了根结点外,其余结点都有唯一的一个分枝进入,由于这些分枝是由度为1和度为2的结点射出的,一个度为1的结点射出一个分枝,一个度为2的
8、结点射出两个分枝,所以有: nn12n21因此可以得到:n0n21 。,性质3 在一棵二叉树中,如果叶子结点数为n0,度为2的结点数为n2,则有: n0n21。,6.2 二 叉 树,两种特殊的二叉树满二叉树:如果深度为k的二叉树,有2k-1个结点则称为满二叉树;,满二叉树的特点:,叶子只能出现在最下一层;只有度为0和度为2的结点。,满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多,6.2 二 叉 树, 完全二叉树 深度为K,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点都一一对应时,称之为完全二叉树。,6.2 二 叉 树,
9、在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一棵完全二叉树。,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,8,不是完全二叉树,结点10与满二叉树中的结点10不是同一个结点,6.2 二 叉 树,完全二叉树的特点,1. 叶子结点只能出现在最下两层;2. 完全二叉树中如果有度为1的结点,只可能有一个,且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,8,6.2 二 叉 树,性质4 具有n个结点的完全二叉树的深度为 log2n +1。,6.2 二 叉
10、 树,性质5 对一棵具有n个结点的完全二叉树中从1开始按层序编号,则对于任意的序号为i(1in)的结点,有: (1)如果i1,则结点i的双亲结点的序号为 i/2(取整);如果i1,则结点i是根结点,无双亲结点。,6.2 二 叉 树,(2)如果2in,则结点i的左孩子的序号为2i; 如果2in,则结点i无左孩子。,6.2 二 叉 树,(3)如果2i1n,则结点i的右孩子的序号为2i1; 如果2i1n,则结点 i无右孩子。,6.2 二 叉 树,对一棵具有n个结点的完全二叉树中从1开始按层序编号,则 结点i的双亲结点为 i/2; 结点i的左孩子为2i; 结点i的右孩子为2i1。,性质5表明,在完全二
11、叉树中,结点的层序编号反映了结点之间的逻辑关系。,6.2 二 叉 树,三二叉树存贮结构 1 二叉树的顺序结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置(下标)应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系 。,6.2 二 叉 树,完全二叉树的顺序存储,以编号为下标,6.2 二 叉 树,二叉树的顺序存储,按照完全二叉树编号,以编号为下标,6.2 二 叉 树,二叉树的顺序存储结构一般仅 存储完全二叉树和满二叉树。,6.2 二 叉 树,2 二叉树的链式存储结构,1)基
12、本思想:令二叉树的每个结点对应一个链表结点,链表结点除了存放与二叉树结点有关的数据信息外,还要设置指示左右孩子的指针。,结点结构:,其中,data:数据域,存放该结点的数据信息; lchild:左指针域,存放指向左孩子的指针; rchild:右指针域,存放指向右孩子的指针。,6.2 二 叉 树,二叉树的二叉链表存储表示:Typedef struct BiNode TElemType data; struct BiNode *lchild, *rchild;/ 左右孩子指针BiNode, *BiTree;,6.2 二 叉 树,2)二叉链表 二叉链表中每个结点至少包含三个域:数据域、左指针域、 右
13、指针域,在n个结点的二叉树中,有n+1个空链域。,6.2 二 叉 树,3 )三叉链表 三叉链表中每个结点至少包含四个域:数据域、双亲指针域、左指针域、右指针域,结点结构:,其中,data:数据域,存放该结点的数据信息; parent:双亲指针域,存放指向指向双亲节点的指针; lchild:左指针域,存放指向左孩子的指针; rchild:右指针域,存放指向右孩子的指针。,rchild,6.2 二 叉 树,第六章 树和二叉树,6.3 二叉树的遍历,一、二叉树的遍历方法,二叉树的遍历是指从根结点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果?,
14、对于线性结构由于每个结点只有一个直接后继,遍历是很容易的事。 二叉树是非线性结构,每个结点可能有两个后继,如何访问二叉树的每个结点,而且每个结点仅被访问一次?,二叉树的遍历方式:DLR、LDR、LRD、DRL、RDL、RLD,如果限定先左后右,则二叉树遍历方式有三种:前序:DLR中序:LDR后序:LRD,层序遍历:按二叉树的层序编号的次序访问各结点。,考虑二叉树的组成:,6.3 二叉树的遍历,1、先序(根)遍历若二叉树为空,则空操作返回;否则:访问根结点;先序遍历根结点的左子树;先序遍历根结点的右子树。,先序遍历序列:A B D G C E F,6.3 二叉树的遍历,6.3 二叉树的遍历,2、
15、中序(根)遍历若二叉树为空,则空操作返回;否则:中序遍历根结点的左子树;访问根结点;中序遍历根结点的右子树。,中序遍历序列:D G B A E C F,6.3 二叉树的遍历,3、后序(根)遍历若二叉树为空,则空操作返回;否则:后序遍历根结点的左子树;后序遍历根结点的右子树;访问根结点。,后序遍历序列:G D B E F C A,4、层序遍历二叉树的层次遍历是指从二叉树的第一层(即根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。,层序遍历序列:A B C D E F G,6.3 二叉树的遍历,6.3 二叉树的遍历,例如:,先序序列:,中序序列:,后序序列:,A B
16、C D E F G H K,B D C A E H G K F,D C B H K G F E A,6.3 二叉树的遍历,二. 遍历的递归算法,void Preorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,先序遍历递归算法,6.3 二叉树的遍历,二叉树前序遍历的非递归算法的关键:在前序遍历过某结点的整个左子树后,如何找到该结点的右子树的根指针。解决办法:在访问完该结点后,将该结点的指针保存在栈中,以便以后能通过它找到该结点的右子树。,先序遍历非递归算法,先序遍历算法的执行轨迹,A,B,D,G,C,E,F,A,栈内容,B,D,G,C,E,F,1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 树和二叉树ppt课件 二叉 ppt 课件
链接地址:https://www.31ppt.com/p-1939689.html