第五章 树PPT讲稿.ppt
《第五章 树PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第五章 树PPT讲稿.ppt(65页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第五章 树第1页,共65页,编辑于2022年,星期三树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式现实世界中,能用树的结构表示的例子:现实世界中,能用树的结构表示的例子:学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。2023/1/242第2页,共65页,编辑于2022年,星期三ABCDEFGH树形结构 结点间具有分层次的连接关系HBCDEFGA2023/1/243第3页,共65页,编辑于2022年,星期三由一个或多个结点组成的有限集合由一个或多个结点组成的有限集合。仅有一个根结点,结点间仅有一个根结点,结点间有明显
2、的层次结构关系。除根结点外有明显的层次结构关系。除根结点外,其余结点又可构成其余结点又可构成互不相交若干个子树若干个子树.ACGT2DHIT3JMBELKT1F5.1树的定义:树的定义:2023/1/244第4页,共65页,编辑于2022年,星期三空树E F G H I J B C DAA只有一个根结点的树K L M树的若干形式:树的若干形式:一棵树结构非树结构2023/1/245第5页,共65页,编辑于2022年,星期三B C D AE F G H I JK LMT1 T2T3基本术语:基本术语:结点的度:子树的个数。叶结点:度为0的结点。分枝结点:度不为0的结点。左孩子、右孩子、双亲路径、
3、路径长度祖先、子孙 结点的层数:树中根结点的层次为1,根结点子树的根为第2层,以此类推。树的深度:树中所有结点层次的最大值。树的度:树中所有结点度的最大值。2023/1/246第6页,共65页,编辑于2022年,星期三n(1)Initiate(t)初始化一棵树)初始化一棵树t;n(2)Root(x)求结点)求结点x所在树的根结点;所在树的根结点;n(3)Parent(t,x)求树)求树t中结点中结点x的双亲结点;的双亲结点;n(4)Child(t,x,i)求树求树t中结点中结点x的第的第i个孩子结点;个孩子结点;n(5)RightSibling(t,x)求树求树t中结点中结点x的第一个右边兄弟
4、结的第一个右边兄弟结点点n(6)Insert(t,x,i,s)把以)把以S为结点的树插人到树为结点的树插人到树t中作中作为结为结点点x的第的第i棵子树棵子树n(7)Delete(t,x,i)在树)在树t中删除结点中删除结点x的第的第i棵子树;棵子树;5.1.3树的基本操作树的基本操作2023/1/247第7页,共65页,编辑于2022年,星期三1、二叉树的定义和基本操作、二叉树的定义和基本操作(1)二叉树的定义二叉树的定义二叉树的五种基本形态二叉树的五种基本形态二叉数是二叉数是n(n=0)个结点的有限集合。它或为空数个结点的有限集合。它或为空数(n=0),或由一个或由一个根结点和两棵分别称为根
5、的左子树和右子树的互不相交的二叉数根结点和两棵分别称为根的左子树和右子树的互不相交的二叉数组成组成,子树间有子树间有次序关系次序关系。二叉树的基本形态有下图:。二叉树的基本形态有下图:空二叉树空二叉树仅有仅有根结点根结点右子树右子树为空为空左子树左子树为空为空左右子树左右子树均非空均非空5.2二叉树二叉树2023/1/248第8页,共65页,编辑于2022年,星期三 特别要注意:特别要注意:二叉数不是树的特殊情况。是一类二叉数不是树的特殊情况。是一类与树不同的树形结构与树不同的树形结构.a aa ab bb b两棵不同的二叉数两棵不同的二叉数2023/1/249第9页,共65页,编辑于2022
6、年,星期三满二叉树满二叉树423167891011121314155特点:特点:是一棵二叉树是一棵二叉树所有叶子结点都在同一层,所有叶子结点都在同一层,除叶子结点外其余结点的度都为除叶子结点外其余结点的度都为2 2。2023/1/2410第10页,共65页,编辑于2022年,星期三4231678910 11125 非完全二叉树非完全二叉树完全二叉树完全二叉树4231678910 11125 完全二叉树完全二叉树在一棵深度为在一棵深度为K K的满二叉树上删去第的满二叉树上删去第K K层上层上最右最右边起的连续边起的连续j j个结点,就得到深度为个结点,就得到深度为K K的完全二叉的完全二叉树。树
7、。满二叉树也是完全二叉树满二叉树也是完全二叉树,但完全二叉树未必是但完全二叉树未必是满二叉树。满二叉树。2023/1/2411第11页,共65页,编辑于2022年,星期三树与二叉树的区别树与二叉树的区别树中结点的最大度数没有限制,二叉树结点最大度数为树中结点的最大度数没有限制,二叉树结点最大度数为2。树树的的结结点点子子树树无无左左、右右之之分分,二二叉叉树树的的结结点点子子树树有有明明确确的的左左、右右之之分。分。二二叉叉树树树树2023/1/2412第12页,共65页,编辑于2022年,星期三性质性质性质性质1、二叉树的第i层上至多有2 i-1(i 1)个结点。二叉树的基本性质二叉树的基本
8、性质423167891011121314155第三层上第三层上(i=3)(i=3),有,有2 23-13-1=4=4个节点。个节点。第四层上第四层上(i=4)(i=4),有,有2 24-14-1=8=8个节点。个节点。2023/1/2413第13页,共65页,编辑于2022年,星期三性质性质性质性质2、深度为k的二叉树中至多含有2k -1个结点。423167891011121314155此树的深度此树的深度k=4k=4,共有,共有2 24 4-1=15-1=15个节点。个节点。二叉树的基本性质二叉树的基本性质2023/1/2414第14页,共65页,编辑于2022年,星期三性质性质性质性质3
9、3:对于任意一棵二叉树BT,如果度为0的结点个数为n0,度为2的结点个数为n2,则n0=n2+1。证明:假设度为1的结点个数为n1,结点总数为n,B为二叉树中的分支数。因为在二叉树中,所有结点的度均小于或等于2,所以结点总数为:n=n0+n1+n2 (1)再查看一下分支数。在二叉树中,除根结点之外,每个结点都有一个从上向下的分支指向,所以,总的结点个数n与分支数B之间的关系为:Bn-1。二叉树的基本性质二叉树的基本性质2023/1/2415第15页,共65页,编辑于2022年,星期三又因为在二叉树中,度为1的结点产生1个分支,度为2的结点产生2个分支,所以分支数B可以表示为:B=n1+2n2。
10、将此式代入上式,得:n=n1+2n2+1 (2)用(1)式n=n0+n1+n2减去(2)式,并经过调整后得到:n0=n2+1。二叉树的基本性质二叉树的基本性质2023/1/2416第16页,共65页,编辑于2022年,星期三若在任意一棵二叉树中,有n0个叶子结点,有n2个度为2的结点,则:n0=n2+1423167891011121314155n n0 0=8=8n n2 2=7=7二叉树的基本性质二叉树的基本性质2023/1/2417第17页,共65页,编辑于2022年,星期三 性质性质4:具有n个结点的完全二叉树的深度为 log2n+1。其中,log2n 的结果是不大于log2n的最大整数
11、。2k-1-1n=2k-1对不等式取对数对不等式取对数有有:K-1=log2nn,则结点i没有左孩子;否则其左孩子结点的编号为2i。n(3)如果2i+1n,则结点i没有右孩子;否则其右孩子结点的编号为2i+1。二叉树的基本性质二叉树的基本性质2023/1/2419第19页,共65页,编辑于2022年,星期三如果i=1,则结点i是这棵完全二叉树的根如果2in,则结点i没有左孩子111234567891012如果2i+1n,则结点i没有右孩子对一棵对一棵完全完全二叉树:二叉树:二叉树的基本性质二叉树的基本性质2023/1/2420第20页,共65页,编辑于2022年,星期三5.2.3二叉树的存储二
12、叉树的存储二二叉叉树树的的顺顺序序存存储储:按按二二叉叉树树从从左左到到右右、从从上到下的顺序存储。上到下的顺序存储。一一般般以以完完全全二二叉叉树树和和满满二二叉叉树树采采用用顺顺序序存存储储比比较较合合适适。数数组组下下标标序序号号可可以以惟惟一一反反映映出出结点间的逻辑关系。结点间的逻辑关系。对对非非完完全全二二叉叉树树,则则通通过过添添加加虚虚拟拟结结点点构构造造出完全二叉树后进行顺序存储。出完全二叉树后进行顺序存储。1.顺序存储顺序存储2023/1/2421第21页,共65页,编辑于2022年,星期三(2)链式存储结构链式存储结构若父结点在数组中若父结点在数组中i下标处,其左孩子在下
13、标处,其左孩子在2*i处,右孩子在处,右孩子在2*i+1处。处。(1)顺序存储结构顺序存储结构1.顺序存储结构顺序存储结构2h-1=24-1=15用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素。结结点点在在数数组组中中的的相相对对位位置置蕴蕴含含着着结结点点之之间间的的关关系。系。一般二叉树必须按完全二叉树的形式存储,将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储,将造成存储的浪费。二叉树的存储结构二叉树的存储结构1 2 3 4 4 6 7 8 9 10 11 12 13 12 34 5 6 78 9 10 11 12 132023/1/2422第22
14、页,共65页,编辑于2022年,星期三二叉树的顺序存储表示可描述为:二叉树的顺序存储表示可描述为:#defineMAXNODE100/*二二叉叉树树的的最最大大结结点数点数*/typedefelemtypeSqBiTreeMAXNODE/*0号单元存放根结点号单元存放根结点*/SqBiTreebt;即将即将btbt定义为含有定义为含有MAXNODEMAXNODE个个elemtypeelemtype类型类型元素的一维数组元素的一维数组。2023/1/2423第23页,共65页,编辑于2022年,星期三n2.链式存储结构n 在顺序存储结构中,利用编号表示元素的位置及元素之间孩子或双亲的关系,因此对
15、于非完全二叉树,需要将空缺的位置用特定的符号填补,若空缺结点较多,势必造成空间利用率的下降。在这种情况下,就应该考虑使用链式存储结构。n 常见的二叉树结点结构如下所示:LchildDataRchild2023/1/2424第24页,共65页,编辑于2022年,星期三 其中,Lchild和Rchild是分别指向该结点左孩子和右孩子的指针,Data是数据元素的内容。在C语言中的类型定义为:typedef struct BiTNode elemtype data;struct BiTNode*lchild;*rchild;/*左右孩子指针*/BiTNode,*BiTree;下面是一棵二叉树及相应的链
16、式存储结构。2023/1/2425第25页,共65页,编辑于2022年,星期三2.二叉链式存储结构二叉链式存储结构lchildDatarchild每个结点由数据域、左指针域和右指针域组成。每个结点由数据域、左指针域和右指针域组成。二叉链式存储结构为:2023/1/2426第26页,共65页,编辑于2022年,星期三三叉链式存储结构三叉链式存储结构每个结点由数据域、左指针域和右指针域和指向父亲结点的每个结点由数据域、左指针域和右指针域和指向父亲结点的指针组成。指针组成。三叉链式存储结构为:2023/1/2427第27页,共65页,编辑于2022年,星期三Initiate(bt)建立一棵空二叉树。
17、建立一棵空二叉树。Create(x,lbt,rbt)生成一棵以生成一棵以x为根结点的数据域信息,以二叉树为根结点的数据域信息,以二叉树lbt和和rbt为左子树和右子树的二叉树。为左子树和右子树的二叉树。InsertL(bt,x,parent)将数据域信息为将数据域信息为x的结点插入到二叉树的结点插入到二叉树bt中作为结点中作为结点parent的左孩子结点。如果结点的左孩子结点。如果结点parent原来有左孩子结点,原来有左孩子结点,则将结点则将结点parent原来的左孩子结点作为结点原来的左孩子结点作为结点x的左孩子结点。的左孩子结点。InsertR(bt,x,parent)将数据域信息为将数
18、据域信息为x的结点插入到二叉树的结点插入到二叉树bt中作为结点中作为结点parent的右孩子结点。的右孩子结点。DeleteL(bt,parent)在二叉树)在二叉树bt中删除结点中删除结点parent的左子树。的左子树。DeleteR(bt,parent)在二叉树)在二叉树bt中删除结点中删除结点parent的右子树。的右子树。Search(bt,x)在二叉树在二叉树bt中查找数据元素中查找数据元素x。Traverse(bt)按某种方式遍历二叉树按某种方式遍历二叉树bt的全部结点。的全部结点。5.2.4二叉树基本操作的算法实现二叉树基本操作的算法实现2023/1/2428第28页,共65页,
19、编辑于2022年,星期三(1)二叉树是一种非线性的数据结构,在对它进行操作时,总是需要逐一对每个数据元素实施操作,这样就存在一个操作顺序问题,由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。n二叉树的遍历方式分为两大类:一类按根、左子树和右子树三个部分进行访问;另一类按层次访问。下面我们将分别进行讨论。5.2.5遍历二叉树遍历二叉树2023/1/2429第29页,共65页,编辑于2022年,星期三(1)先序遍历若二叉树为空,则结束遍历操作;否则n访问根结点;n先序遍历左子树;n先序遍历
20、右子树。二叉树的遍历二叉树的遍历按根、左子树和右子树三部分进行遍历.根据根访问的位置不同分别被称为:先序遍历TLR 中序遍历LTR 后序遍历LRT。递归算法如下:void PreOrder(BiTree bt)if(bt=NULL)return;Visite(bt-data);PreOrder(bt-lchild);PreOrder(bt-rchild);2023/1/2430第30页,共65页,编辑于2022年,星期三(3)后序遍历若二叉树为空,则结束遍历操作;否则n后序遍历左子树;n后序遍历右子树;n访问根结点。(2)中序遍历若二叉树为空,则结束遍历操作;否则 中序遍历左子树;访问根结点;
21、中序遍历右子树。void InOrder(BiTree bt)if(bt=NULL)return;InOrder(bt-lchild);Visite(bt-data);InOrder(bt-rchild);void PostOrder(BiTree bt)if(bt=NULL)return;PostOrder(bt-lchild);PostOrder(bt-rchild);Visite(bt-data);2023/1/2431第31页,共65页,编辑于2022年,星期三pre(D R);pre(A R);voidPreOrder(BiTreebt)if(bt=NULL)return;/*递归调
22、用的结束条件递归调用的结束条件*/Visit(bt-data);PreOrder(bt-lchild);PreOrder(bt-rchild);主程序主程序Pre(T)返回返回pre(C R);返回返回ACBDTBprintf(B);pre(B L);BTAprintf(A);pre(A L);ATDprintf(D);pre(D L);DTCprintf(C);pre(C L);C返回T左是空返回左是空返回pre(B R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回2023/1/2432第32页,共65页,编辑于2022年,星期三void InO
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章 树PPT讲稿 第五 PPT 讲稿
限制150内