IOTek Information Tchnology,*,Click to edit Master title style,IOTek Information Tchnology,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,IOTek Information Tchnology,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,IOTek Information Tchnology,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,IOTek Information Tchnology,*,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,static void Main(string,args),Console.WriteLine(,请输入一个字符串,：);/,输入提示,/,从控制台读入字符串,string,line,=Console.ReadLine();,/,循环输出字符串中的字符,foreach(char c in,line,),Console.WriteLine(c);,Console.ReadLine();,static void Main(string,args),Console.WriteLine(,请输入一个字符串,：);/,输入提示,/,从控制台读入字符串,string,line,=Console.ReadLine();,/,循环输出字符串中的字符,foreach(char c in,line,),Console.WriteLine(c);,Console.ReadLine();,依次循环字符串中的每个字符,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,树和二叉树,预习检查,什么是二叉树,树的遍历有哪几种方式,树有那些应用,2024/11/16,3,本章目标,了解树的定义和根本术语,了解二叉树的定义、性质、和存储构造,把握二叉树的遍历,本章构造,树的规律构造和存储构造,树和二叉树,二叉树,遍历二叉树,2024/11/16,5,5.1.1 树型构造实例,1家族树,5-1 树的规律构造和存储构造,图,5-1,家族树,2024/11/16,6,2书的名目构造,图5-2 书的名目,5-1 书的名目构造,2024/11/16,7,5.1.2 树的定义,1树的定义,树(Tree)是n(n0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：,(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；,(2)除根结点以外，其余结点可分为m(m0)个互不相交的有限集合T0，Tl，Tm-1。其中每个集合又构成一棵树，树T0，Tl，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。,树的规律构造表示数据之间的关系是一对多，或者多对一的关系。它的构造特点具有明显的层次关系，是一种特别重要的非线性的数据构造。,5-1 树的规律构造和存储构造,2024/11/16,8,图5-3 树的例如,图,5-3(a),是一棵只有一个根结点的树；,图,5-3(b),是一棵有,12,个结点的树，即,T=A,，,B,，,C,，,，,K,，,L,。,A,是棵根，除根结点,A,之外，其余的,11,个结点分为三个互不相交的集合。,T1，T2,和,T3,是根,A,的三棵子树，且本身又都是一棵树。,所以树的,定义,是递归的,。,2024/11/16,9,2树的根本术语,树的结点包含一个数据元素及假设干指向其子树的分支。,1.树的结点:包含一个DE和指向其子树的全局部支;,2.结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;,3.树的度:树中全部结点的度的最大值 Max(D(I),含义:树中最大分支数为树的度;,4.结点的层次及树的深度:根为第一层,根的孩子为其次层,假设某结点为第k层,则其孩子为k+1层.,树中结点的最大层次称为树的深度或高度,5.森林:是m(m=0)棵互不相的树的集合,森林与树概念相近,相互很简洁转换.,6.有序树、无序树 假设树中每棵子树从左向右的排列拥有肯定的挨次，不得互换，则称为有序树，否则称为无序树。,2024/11/16,10,7.森林:是mm0棵互不相交的树的集合。,在树构造中，结点之间的关系又可以用家族关系描述，定义如下：,8.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。,9.子孙:以某结点为根的子树中的全部结点都被称为是该结点的子孙。,10.祖先:从根结点到该结点路径上的全部结点。,11.兄弟:同一个双亲的孩子之间互为兄弟。,12.堂兄弟:双亲在同一层的结点互为堂兄弟。,2024/11/16,11,3.树的根本运算,树的根本运算主要有：,初始化操作INITIATE(T)：创立一棵空树。,求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。,求双亲函数PARENT(T,x)：在树T中求x的双亲。,求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。,建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。,6.遍历树操作TRAVERSE(T)：按挨次访问树T中各个结点。,2024/11/16,12,1树的遍历,所谓树的遍历，就是依据某种挨次依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性构造的树结点变成线性序列的一种方式。,树的遍历可以按深度优先遍历，也可以依据广度优先按层次遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。,(1)前序遍历的递归定义：,假设树T非空，则：,访问根结点R；,依据从左到右的挨次依次前序遍历根结点R的各子树T1，T2，Tk。,5-1-5,树的遍历,2024/11/16,13,(2)后序遍历的递归定义：,假设树T非空，则：,依据从左到右的挨次依次后序遍历根T的各子树Tl，T2，Tk；,访问根结点R。,(3)广度优先按层遍历,广度优先按层次遍历定义为：先访问第一层结点即树根结点，再从左至右访问其次层结点，依次按层访问，直到树中结点全部被访问为止。对图6-6(a)中的树进展按层次遍历得到树的广度优先遍历序列为：ABCDEFG。,说明：,前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。6.2节将介绍二叉树,后序遍历树恰好等价于中序遍历该树所对应的二叉树。,2024/11/16,14,树的先序遍历算法描述如下：,void Preorder(Btree*root)/,先根遍历,k,叉树,if(root!=NULL),printf(,“,%,cn,”,root-data);/,访问根结点,for(i=0;iti);/,递归前序遍历每一个子结点,2024/11/16,15,5.2.1二叉树的定义与性质,二叉树(Binary Tree)是另一种重要的树型构造。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树构造的定义类似，二叉树的定义也可以用递归形式给出。,1二叉树的递归定义,二叉树(BinaryTree)是n(n0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：,(1)有且仅有一个根结点；,(2)其余的结点分成两棵互不相交的左子树和右子树。,5-2,二叉树,2024/11/16,16,二叉树与树有区分：树至少应有一个结点，而二叉树可以为空；树的子树没有挨次，但假设二叉树的根结点只有一棵子树，必需明确区分它是左子树还是右子树，由于两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据构造。,二叉树有5种根本形态：,图5-7 二叉树的五种根本形态,(,a),空二叉树,(,b),只有根结点的二叉树,(,c),右子树为空的二叉树,(,d),左子树为空的二叉树,(,e),左右子树均不为空的二叉树,2024/11/16,17,两种特殊形态的二叉树：满二叉树和完全二叉树。,(1)满二叉树(FullBinaryTree),深度为k，且有2k-1个结点的二叉树。,特点：1每一层上结点数都到达最大,2度为1的结点n1=0，树叶都在最下一层上。,结点层序编号方法：从根结点起从上到下逐层层内从左到右对二叉树的结点进展连续编号。,1,2,3,7,6,5,4,K=3,n=2,3,-1=7,满二叉树,2024/11/16,18,(2)完全二叉树(Complete BinaryTree),深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与一样深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。,图,5-8,完全二叉树,完全二叉树的特点：,1每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能消失在层次最大或次最大的两层上。,2完全二叉树结点数n满足2k-1-1n2k-1,3满二叉树肯定是完全二叉树，反之不成立。,4,5,2,1,3,2024/11/16,19,1,3,2,4,6,5,3,2,4,1,LH,1,=3,RH,1,=1,LH,1,-,RH,1,=2,非完全二叉树 非完全二叉树,LH,2,=0,RH,2,=1,LH,2,-RH,2,=0-1=-1,2024/11/16,20,2二叉树的性质,性质1 在二叉树的第i层上至多有2i-1 个结点(i1)。,性质2 深度为k的二叉树至多有2k-1个结点(k1)。,深度肯定，二叉树的最大结点数也确定,性质3 二叉树中,终端结点数n0与度为2的结点数n2有如下关系:,n0=n2+1,性质4 结点数为n的完全二叉树，其深度为 log2n+l,性质5 在按层序编号的n个结点的完全二叉树中，任意一结点i(1in)有：,i=1时，结点i是树的根；否则，结点i的双亲为结点 i/2 (i1)。,2in时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。,2i+1n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。,2024/11/16,21,链式存储构造 二叉链表,设计不同的结点构造，可以构成不同的链式存储构造。常用的有：,二叉链表,三叉链表,线索链表 用空链域存放指向前驱或后继的线索,2024/11/16,22,由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的构造表示为：,其中左链域lchild为指向左孩