第五和六章二叉树和树.pps
《第五和六章二叉树和树.pps》由会员分享,可在线阅读,更多相关《第五和六章二叉树和树.pps(211页珍藏版)》请在三一文库上搜索。
1、1,二叉树的逻辑结构与存储结构 二叉树查找树 堆与优先队 哈夫曼树 树的逻辑结构与存储结构 K叉树,第3部分 二叉树和树,本章的主要内容是,2,树T:n(n0)个结点的有限集合。当n0时,称为空树;任意一棵非空树满足以下条件: 有且仅有一个特定的称为根的结点; 当n1时,除根结点之外的其余结点被分成m(m0)个互不相交的有限集合T1,T2, ,Tm,其中每个集合又是一棵树,并称为这个根结点的子树。,5.1 树的基本概念,树的固有特性-树的定义是采用递归方法,树的定义,3,(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构,5.1 树的基本概念,树的逻辑表示,1. 结点和结点间的连线表示
2、法,1=B,D,E,F,H,I 2=C,G,4,.文式图表示法-集合嵌套,3.凹式表示法-层次表表示,5.1 树的基本概念,5,树的应用举例文件结构,5.1 树的基本概念,6,树的基本概念,结点的度:结点所拥有的子树的个数。 树的度:树中各结点度的最大值。,5.1 树的基本概念,树的相关术语,7,叶子结点:度为0的结点,也称为终端结点。 分支结点:度不为0的结点,也称为非终端结点,或 内部结点。,5.1 树的基本概念,8,孩子、双亲:树中某结点子树的根结点称为这个结点的孩子结 点,这个结点称为它孩子结点的双亲结点; 兄弟:具有同一个双亲的孩子结点互称为兄弟。 堂兄弟:双亲在同一层的孩子结点互称
3、为堂兄弟。,5.1 树的基本概念,9,路径:如果树的结点序列n1, n2, , nk有如下关系:结点ni是ni+1的双亲(1=ik),则把n1, n2, , nk称为一条由n1至nk的路径;路径上经过的边的个数称为路径长度。,5.1 树的基本概念,10,祖先、子孙:在树中,如果有一条路径从结点x到结点y,那 么x就称为y的祖先,而y称为x的子孙。,5.1 树的基本概念,结点为n的树,必然有n-1条边。,11,结点的深度:结点所在层数,根结点的层数为0;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。 树的深度:树中所有结点的最大层数+1,也称高度。,5.1 树的基本概念,国内大部分
4、教材设为1,12,层序编号:将树中结点按照从上层到下层、同层从左到右的次 序依次给他们编以从1开始的连续自然数。,5.1 树的基本概念,13,有序树、无序树:如果一棵树中结点的各子树从左到右是有 次序的,称这棵树为有序树;反之,称为 无序树。,数据结构中讨论的一般都是有序树,5.1 树的基本概念,14,森林:m (m0)棵互不相交的树的集合。,5.1 树的基本概念,F=(T1,T2,.Tm),15,同构:对两棵树,若通过对结点适当地重命名,就可以使这两棵树完全相等(结点对应相等,结点对应关系也相等),则称这两棵树同构。,5.1 树的基本概念,16,树结构和线性结构的比较,线性结构,树结构,无前
5、驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,5.1 树的基本概念,17,二叉树的定义,二叉树是n(n0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.2 二叉树的逻辑结构,二叉树的定义及主要特性,(1)二叉树的定义,18,(2)二叉树的特点,每个结点最多有两棵子树; 二叉树是有序的,其次序不能 任意颠倒。,5.2 二叉树的逻辑结构,19,(3)二叉树的基本形态,5.2 二叉树的逻辑结构,20,例:具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。
6、,树,二叉树,5.2 二叉树的逻辑结构,21,特殊的二叉树,(1)斜树 1 .所有结点都只有左子树的二叉树称为左斜树; 2 .所有结点都只有右子树的二叉树称为右斜树; 3.左斜树和右斜树统称为斜树。,1. 在斜树中,每一层只有一个结点; 2.斜树的结点个数与其深度相同。, 斜树的特点:,5.2 二叉树的逻辑结构,22,(2)满二叉树 在一棵二叉树中,如果所有分支结点都存在左子树和右子树, 满二叉树的特点:,只有度为0和度为2的结点。,5.2 二叉树的逻辑结构,23,(3)完全二叉树 从根结点起每一层从左至右填充。一棵高度为d的完全二叉树除了d-1层以外,每一层都是满的,且底曾叶结点集中在左边的
7、若干位置上。,5.2 二叉树的逻辑结构,24,1. 叶子结点只能出现在最下两层,且最下层的叶子结点都集中在二叉树的左部; 2. 完全二叉树中如果有度为1的结点,只可能有一个,且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。, 完全二叉树的特点:,5.2 二叉树的逻辑结构,25,(4)国内大部分教材定义 满二叉树 在一棵二叉树中,如果所有分支结点都存在左子树和右子树 所有叶子都在同一层上, 满二叉树的特点:,叶子只能出现在最下一层; 只有度为0和度为2的结点。,5.2 二叉树的逻辑结构,26,不是完全二叉树,在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一
8、棵完全二叉树。,需要注意的是:满二叉树与完全二叉树之间并没有任何特别关系。,5.2 二叉树的逻辑结构,27,按照上述(第二种)定义,不是满二叉树,虽然所有分支结点都有左右子树,但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多,5.2 二叉树的逻辑结构,28,对一棵具有n个结点的二叉树按层序编号,如果编号为i(1in)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,按照上述(第二种)定义,5.2 二叉树的逻辑结构,29,二叉树的基本性质,性质5-1 二叉树的第i层上最多有2i-1个结点(i1)。,证明:当i=1时,
9、第1层只有一个根结点,而 2i-1=20 =1,结论显然成立。 假定i=k(1ki)时结论成立,即第k层上至多有2k-1个结点, 则 i=k+1时,因为第k+1层上的结点是第k层上结点的孩子,而二叉树中每个结点最多有2个孩子,故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍,即22k-12k。结论成立。,5.2 二叉树的逻辑结构,30,性质5-2 一棵深度为k的二叉树中,最多有2k-1个结点,最少有k个结点。,证明:由性质1可知,深度为k的二叉树中结点个数最多 = =2k-1; 每一层至少要有一个结点,因此深度为k的二叉树, 至少有k个结点。,5.2 二叉树的逻辑结构,31,性质5-
10、3 在一棵二叉树中,如果叶子结点数为n0,度为2的结点数为n2,则有: n0n21。,证明: 设n为二叉树的结点总数,n1为二叉树中度为1的结点数,则有: nn0n1n2 在二叉树中,除了根结点外,其余结点都有唯一的一个分枝进入,由于这些分枝是由度为1和度为2的结点射出的,一个度为1的结点射出一个分枝,一个度为2的结点射出两个分枝,所以有: nn12n21 因此可以得到:n0n21 。,5.2 二叉树的逻辑结构,32,在有n个结点的满二叉树中,有多少个叶子结点?,5.2 二叉树的逻辑结构,33,性质5-4 具有n个结点的完全二叉树的深度为 log2n +1。,证明:假设具有n个结点的完全二叉树
11、的深度为k, 根据完全二叉树的定义和性质2,有下式成立 2k-1 n 2k,5.2 二叉树的逻辑结构,34,证明(续):,5.2 二叉树的逻辑结构,35,性质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.2 二叉树的逻辑结构,36,对一棵具有n个结点的完
12、全二叉树中从1开始按层序编号,则 结点i的双亲结点为 i/2; 结点i的左孩子为2i; 结点i的右孩子为2i1。,性质5表明,在完全二叉树中,结点的层序编号反映了结点之间的逻辑关系。,5.2 二叉树的逻辑结构,37,二叉树的抽象数据类型,ADT BiTree Data 由一个根结点和两棵互不相交的左右子树构成, 结点具有相同数据类型及层次关系 Operation InitBiTree 前置条件:无 输入:无 功能:初始化一棵二叉树 输出:无 后置条件:构造一个空的二叉树,5.2 二叉树的逻辑结构,38,DestroyBiTree 前置条件:二叉树已存在 输入:无 功能:销毁一棵二叉树 输出:无
13、 后置条件:释放二叉树占用的存储空间 InsertL 前置条件:二叉树已存在 输入:数据值x,指针parent 功能:将数据域为x的结点插入到二叉树中,作为结点parent的左孩子。如果结点parent原来有左孩子,则将结点parent原来的左孩子作为结点x的左孩子 输出:无 后置条件:如果插入成功,得到一个新的二叉树,5.2 二叉树的逻辑结构,39,DeleteL 前置条件:二叉树已存在 输入:指针parent 功能:在二叉树中删除结点parent的左子树 输出:无 后置条件:如果删除成功,得到一个新的二叉树 Search 前置条件:二叉树已存在 输入:数据值x 功能:在二叉树中查找数据元素
14、x 输出:指向该元素结点的指针 后置条件:二叉树不变,5.2 二叉树的逻辑结构,40,PreOrder 前置条件:二叉树已存在 输入:无 功能:前序遍历二叉树 输出:二叉树中结点的一个线性排列 后置条件:二叉树不变 InOrder 前置条件:二叉树已存在 输入:无 功能:中序遍历二叉树 输出:二叉树中结点的一个线性排列 后置条件:二叉树不变,5.2 二叉树的逻辑结构,41,PostOrder 前置条件:二叉树已存在 输入:无 功能:后序遍历二叉树 输出:二叉树中结点的一个线性排列 后置条件:二叉树不变 LeverOrder 前置条件:二叉树已存在 输入:无 功能:层序遍历二叉树 输出:二叉树中
15、结点的一个线性排列 后置条件:二叉树不变 endADT,5.2 二叉树的逻辑结构,42,/ Binary tree node abstract class template class BinNode public: virtual Elem,二叉树结点ADT的实现,5.2 二叉树的逻辑结构,P93,43,二叉树的遍历操作,二叉树的遍历是指从根结点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果?,5.2 二叉树的逻辑结构,44,二叉树的遍历方式: DLR、LDR、LRD、 DRL、RDL、RLD,如果限定先左后右,则二叉树遍历方式有三种:
16、 前序:DLR 中序:LDR 后序:LRD,层序遍历:按二叉树的层序编号的次序访问各结点。,5.2 二叉树的逻辑结构,考虑二叉树的组成:,45,(1)前序(根)遍历 若二叉树为空,则空操作返回;否则: 访问根结点; 前序遍历根结点的左子树; 前序遍历根结点的右子树。,5.2 二叉树的逻辑结构,前序遍历序列:A B D G C E F,46,(2)中序(根)遍历 若二叉树为空,则空操作返回;否则: 中序遍历根结点的左子树; 访问根结点; 中序遍历根结点的右子树。,5.2 二叉树的逻辑结构,中序遍历序列:D G B A E C F,47,(3)后序(根)遍历 若二叉树为空,则空操作返回;否则: 后
17、序遍历根结点的左子树; 后序遍历根结点的右子树。 访问根结点;,5.2 二叉树的逻辑结构,后序遍历序列:G D B E F C A,48,(4)层序遍历 二叉树的层次遍历是指从二叉树的第一层(即根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。,5.2 二叉树的逻辑结构,层序遍历序列:A B C D E F G,49,(1)前序遍历的实现 方法1 Template void PreOrder(BinNode* subroot) if (subroot = NULL) return; visit(subroot); PreOrder(subroot-left(); P
18、reOrder(subroot-right(); ,5.2 二叉树的逻辑结构,二叉树遍历操作 C+语言的实现,P94,50,前序遍历算法的执行轨迹,前序遍历序列:A B D G C E F,5.2 二叉树的逻辑结构,51,方法2 template void preorder2(BinNode* subroot) visit(subroot); if (subroot-left() != NULL) preorder2(subroot-left(); if (subroot-right() != NULL) preorder2(subroot-right(); ,5.2 二叉树的逻辑结构,前序遍
19、历序列:A B D G C E F,P94,52,二叉树前序遍历的非递归算法的关键:在前序遍历过某结点的整个左子树后,如何找到该结点的右子树的根指针。 解决办法:在访问完该结点后,将该结点的指针保存在栈中,以便以后能通过它找到该结点的右子树。,在前序遍历中,设要遍历二叉树的根指针为root,则有两种可能: 若root!=NULL,则表明?如何处理? 若root=NULL,则表明?如何处理?, 非递归算法,5.2 二叉树的逻辑结构,53,访问结点序列:,A,栈S内容:,B,D,A,B,前序遍历的非递归实现,A,D,B,C,5.2 二叉树的逻辑结构,54,访问结点序列:,A,栈S内容:,B,D,A
20、,前序遍历的非递归实现,A,D,B,C,D,5.2 二叉树的逻辑结构,55,访问结点序列:,A,栈S内容:,B,D,C,前序遍历的非递归实现,A,D,B,C,C,5.2 二叉树的逻辑结构,56,1.栈s初始化; 2.循环直到root为空且栈s为空 2.1 当root不空时循环 2.1.1 输出root-data; 2.1.2 将指针root的值保存到栈中; 2.1.3 继续遍历root的左子树 2.2 如果栈s不空,则 2.2.1 将栈顶元素弹出至root; 2.2.2 准备遍历root的右子树;,伪代码描述,5.2 二叉树的逻辑结构,57,template void PreOrder(Bin
21、Node * subroot) top= -1; /采用顺序栈,并假定不会发生上溢 while (subroot!=NULL | | top!= -1) while (subroot!= NULL) coutdata; s+top= subroot; subroot = subroot -lchild; if (top!= -1) subroot =stop-; subroot = subroot -rchild; ,5.2 二叉树的逻辑结构,58,(2)中序遍历的实现 template void InOrder(BinNode* subroot) if(subroot = NULL) ret
22、urn; InOrder(subroot-left(); visit(subroot); InOrder(subroot-right(); ,课堂练习,中序遍历序列:D G B A E C F,59,(3)后序遍历的实现 template void PostOrder(BinNode* subroot) if(subroot = NULL) return; PostOrder(subroot-left(); PostOrder(subroot-right(); visit(subroot); ,后序遍历序列:G D B E F C A,课堂练习,60,课堂练习,遍历二叉树是二叉树各种操作的基础
23、 适当修改访问操作的内容,可以派生出很多关于二叉树的 应用算法。,void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); ,61,课堂练习,设计算法求二叉树的结点个数。 P95,Template int count(BinNode *subroot) if (subroot) Count(subroot-left(); n+; /n为全局量并已初始化为0 Count(subroot-right(); ,62,课堂练习,设计算法按前序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 二叉
链接地址:https://www.31doc.com/p-2285426.html