数据结构与算法课件:Data Structure-Binary Tree.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构与算法课件:Data Structure-Binary Tree.ppt》由用户(罗嗣辉)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法课件:Data Structure-Binary Tree 数据结构 算法 课件 Data Structure Binary
- 资源描述:
-
1、第五章 二叉树李李 睿睿College of SoftwareHunan UniversityChangsha Hunan P.R.CCopyright 2004 by Li Rui2 树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界是大量存在的,例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。等等。 5.1 树的定义和基本术语 定义:树(Tree)是n(n=0)个结点
2、的有限集T,T为空时称为空树,否则它满足如下两个条件: (1)有且仅有一个特定的称为根(Root)的结点;Copyright 2004 by Li Rui3(2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm,其中每个子集又是一棵树,并称其为子树(Subtree)。5.2 二叉树 二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树 相互转换,这样就解决了树的存储结构及其运算中存在的复杂性。5.2.1 二叉树的定义定义:二叉树是由n(n=0)个结点的有限集合构成,此集合或者为空集,或者由一个根结点及两棵互不相交的左右子树组成,并且左
3、右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合,根可以有空的左子树或空的右子树。Copyright 2004 by Li Rui5二叉树的相关概念二叉树的相关概念 (1)结点的度。结点所拥有的子树的个数称为该结点的度。 (2)叶结点。度为0的结点称为叶结点,或者称为终端结点。 (3)分枝结点。度不为0的结点称为分支结点,或者称为非终端结点。一棵树的结点除叶结点外,其余的都是分支结点。 (4)左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。(5)路径、路径长度。如果一棵树的一串结点n1,n2,nk有
4、如下关系:结点ni是ni+1的父结点(1i=1)。 采用归纳法证明此性质。 当i=1时,只有一个根结点,2i-1=20 =1,命题成立。 现在假定多所有的j,1=j=1).深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和,由性质1得到每层上的最大结点数,: EkI=1(第i层上的最大结点数)= EkI=12i-1=2k 1 性质3: 对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0n21。设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二叉树中所有结点均小于或等于2,所以有:Nn0n1n2 (5-1)再看二叉树中的分支数,除根结点外,其余结点都有一
5、个进入分支,设B为二叉树中的分支总数, 则有:NB1。Copyright 2004 by Li Rui10由于这些分支都是由度为1和2的结点射出的,所有有: Bn1+2*n2 NB1n12n21 (52)由式(51)和(52)得到: n0+n1+n2=n1+2*n2+1 n0n21下面介绍两种特殊形态的二叉树:满二叉树和完全二叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图5.9就是一棵满二叉树,对结点进行了顺序编号。如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应,2453671图5.9 满二叉树1234561234571236
6、7(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图5.10 完全二叉树则称这样的二叉树为完全二叉树,图5.10(b)、c)是2棵非完全二叉树。满二叉树是完全二叉树的特例。完全二叉树的特点是:(1)所有的叶结点都出现在第k层或k1层。 (2)对任一结点,如果其右子树的最大层次为1,则其左子树的最大层次为1或l1。 性质4:具有n个结点的完全二叉树的深度为log2n 1。符号 x 表示不大于x的最大整数。 假设此二叉树的深度为k,则根据性质2及完全二叉树的定义得到:2k-11n=2k-1 或 2k-1=n2k取对数得到:k1=log2nk 因为k是整数。所以有:k log2n 1。 性质5
7、: 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第 log2n +1层,每层从左到右),则对任一结点i(1=i1,则其双亲是结点 i/2 。 (2)如果2in,则结点i为叶子结点,无左孩子;否则,其左孩子是结点2i。 (3)如果2i1n,则结点i无右孩子;否则,其右孩子是结点2i1。 I/2iI+12i2i+1 2(I+1)2i+3I+12(I+1)2i+3i2i2i+1图5.11 完全二叉树中结点I和i+1(a)I和i+1结点在同一层 (b)I和i+1结点不在同一层如图5.11所示为完全二叉树上结点及其左右孩子结点之间的关系。 在此过程中,可以从(2)和(3)推出(1),所以
8、先证明(2)和(3)。 对于i1,由完全二叉树的定义,其左孩子是结点2,若2n,即不存在结点2,此是,结点i无孩子。结点i的由孩子也只能是结点3,若结点3不存在,即3n,此时结点i无右孩子。对于i1,可分为两种情况: (1)设第j(1=jn,则无左孩子:其右孩子必定为第j1层的第二个结点,编号为2i1。若2i+1n,则无右孩子。 (2)假设第j(1=j=log2n)层上的某个结点编号为i(2e(j-1)=i=2ej-1),且2i11时,如果i为左孩子,即2(i/2)=i,则i/2是i的双亲;如果i为右孩子,i2p+1,i的双亲应为p,p(i1)/2=i/2. 证毕。Copyright 2004
9、 by Li Rui18二叉树的抽象数据类型二叉树结点的ADT template class BinNodepublic: virtual Elem& val()=0;(神马东西) virtual void setVal(const Elem&)=0;(同上) virtual BinNode* left()=0; virtual BinNode* right()=0; virtual void setLeft(BinNode*)=0; virtual void setRight(BinNode*)=0 ; virtual bool isLeaf()=0;Copyright 2004 by Li
10、 Rui195.2.3 二叉树的存储结构1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此,必须把二叉树的所有结点安排成为一个恰当的序列,结点在这个序列中的相互位置能反映出结点之间的逻辑关系,用编号的方法: #define max-tree-size 100Typedef telemtype sqbitreemax-tree-size;Sqbitree bt 从树根起,自上层至下层,每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费,在最坏的情况下,一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且,若经常需要插入与删除树中结点时,顺序存储方
11、式不是很好! Copyright 2004 by Li Rui20ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijklCopyright 2004 by Li Rui21ABCDEFG 表示该处没有元素存在仅仅为了好理解ABCDEFG一般二叉树Copyright 2004 by Li Rui22(2)二叉树的二叉动态链式存储表示二叉树的二叉动态链式存储表示1、结点结构和示例leftChild data rightChildABCDEFrootABCDEFrootCopyright 2004 by Li Rui23二叉树的二叉链表存储表
12、示template class BinaryTree;template class BinTreeNode firend class BinaryTree;private: Elem data; BinTreeNode * lchild; BinTreeNode * rchild;public: BinTreeNode()lchild=rchild=NULL;(干嘛用的) BinTreeNode(Elem e,BinNodePtr*l=NULL, BinNodePtr*r=NULL) data=e; lchild=l; rchild=r; BinTreeNode() Copyright 200
13、4 by Li Rui24二叉树的二叉链表存储表示Elem val()return data;void setVal(const Elem e)data=e;inline BinTreeNode* left()return lchild;inline BinTreeNode* right()return rchild;void setLeft(BinTreeNode* left)lchild=left;void setRight(BinTreeNode* right)rchild=right; bool isLeaf() return (lchild=NULL)&(rchild=NULL);有
14、时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域;Copyright 2004 by Li Rui25template class BinaryTreeprivate: BinTreeNode *root; Elem Refvalue; BinTreeNode *Parent (BinTreeNode *start, BinTreeNode *current); void Traverse (BinTreeNode *current, ostream & out) const void destroy (BinTreeN
15、ode *current);public: Virtual BinaryTree (Elem value): root (NULL), Refvalue (value) Virtual BinaryTree( ) destroy (root); Virtual bool IsEmpty( ) return root = = NULL ? true :false; Virtual BinTreeNode *Parent (BinTreeNode *current) return Parent (root, current); Copyright 2004 by Li Rui263、部分成员函数的
16、实现(递归的步骤还是不明白)template void BinaryTree : destroy (BinTreeNode *current) /删除以current为根的子树 if (current != NULL) destroy (current - leftChild); /删除current的左子树 destroy (current - rightChild); /删除current的右子树 delete current; /删除current 算法中,、两递归调用语句可互换,它只关系到左右子树中,哪一个先删,哪一个后删。 语句不能同和语句互换,因为那样将导致一个子树甚至两个子树无法
17、删。Copyright 2004 by Li Rui27template BinTreeNode *BinaryTree : Parent (BinTreeNode *start, BinTreeNode *current) if (start = = NULL | | current = = start) return NULL; if (start - leftChild = = current | | start - rightChild = = current) return start; /start是双亲 BinTreeNode *p; if (p = Parent (start
18、- leftChild, current) != NULL) return p; /在左子树找 else return Parent (start - rightChild, current); /在右子树找template void Binary Tree : Traverse (BinTreeNode *current, ostream & out) const (为什么要加上const) /搜索并输出根为current的二叉树(out是神马意思) if (current != NULL) out data leftChild, out); /搜索并输出左子树 Traverse (curr
19、ent - rightChild, out); /搜索并输出右子树Copyright 2004 by Li Rui285.3 5.3 遍历二叉树(遍历二叉树(Traversal Binary TreeTraversal Binary Tree)一、一、TBT概述概述1、定义 按某种次序,访问所有结点,使每个节点都被访问且尽访问一次的运算叫TBT。 “访问”包括输出结点值,修改值,统计等以不破坏BT的结构为原则。 TBT是对二叉树进行运算的基础性操作。Copyright 2004 by Li Rui29一、一、TBT概述概述2、次序(V根,L左子树,R右子树) 先序遍历 中序遍历 后序遍历先右后
20、左:VRLRVLRLV先左后右:VLRLVRLRVbtABCDEFGHIJVLR输出序列:A B D E G HI J C FLVR输出序列:D B G EI H J A C FLRV输出序列:D G I JH E B F C ACopyright 2004 by Li Rui30二、二、TBT的递归算法的递归算法1、中序遍历( inorder traversal)template void BinaryTree : InOrder ( ) InOrder (root); /公共函数,调用私有函数完成遍历template void BinaryTree : InOrder (BinTreeNo
21、de *current) if (current != NULL) /当current = = NULL,则递归终结 InOrder (current - leftChild); /中序遍历左子树 cout data; /访问根结点 InOrder (current - rightChild); /中序遍历右子树/abcdef 对 a+b*(c-d)-e/f 表达式的语法树,中序遍历得到其中缀表示: a + b * c d e / f Copyright 2004 by Li Rui312、先序遍历( preorder Traversal)template void BinaryTree :
22、PreOrder (BinTreeNode *current) /私有函数 if (current != NULL) cout data; PreOrder (current - leftChild); PreOrder (current - rightChild); /abcdef 对表达式a+b*(c-d)-e/f 的语法树进行先序遍历得到其前缀表示: + a * b c d / e f二、二、TBT的递归算法的递归算法Copyright 2004 by Li Rui323、后序遍历( postorder traversal)template void BinaryTree : PostO
23、rder (BinTreeNode *current) /私有函数 if (current != NULL) PostOrder (current - leftChild); PostOrder (current - rightChild); cout data; 二、二、TBT的递归算法的递归算法/abcdef 对表达式 a+b*(c-d)-e/f 的语法树进行后序遍历得到其后缀表示: a b c d * + e f / Copyright 2004 by Li Rui33三、三、TBT的非递归算法的非递归算法1、递归算法中栈的使用TBT递归算法的简化traversal (BinTreeNo
24、de *current) if (current != NULL) traversal (current - leftChild); traversal (current - rightChild); Copyright 2004 by Li Rui34三、三、TBT的非递归算法的非递归算法1、递归算法中栈的使用执行过程中栈的情况和current的变化举例当左向递归则current的值进栈若current = = NULL,则出栈,current以栈顶值去执行右向递归直到栈空(top = -1)和current = = NULL为止currenttopad1ad2ad3ad4ad5stackA
25、B C DE ad1ad2ad3ad4ad5-1 0 1 2 3Copyright 2004 by Li Rui352、利用栈的前序和中序遍历非递归算法template void BinaryTree : PreOrder ( ) stack BinTreeNode * st; BinTreeNode *p = root; do while (p != NULL) cout data; st. Push (p); p = p -leftChild; if ( St. length()!=0) st. pop (p ); p = p - rightChild; while (p != NULL
展开阅读全文