树的概念和定义PPT.ppt

,*,第十四讲,树的概念与定义,1,树是,n,（,n0,）个结点的有限集合,T,。当,n=0,时，称为空树；当,n0,时，该集合满足如下条件：,(1),其中必有一个称为根（,root,）的特定结点，它没有直接前驱，但有零个或多个直接后继。,(2),其余,n-1,个结点可以划分成,m,（,m0,）个互不相交的有限集,T,1,，,T,2,，,T,3,，,，,T,m,，其中,T,i,又是一棵树，称为根,root,的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。,2,图,6.1,树的图示方法,3,结点：,包含一个数据元素及若干指向其它结点的分支信息。,结点的度：,一个结点的子树个数称为此结点的度。,叶结点：,度为,0,的结点，即无后继的结点，也称为终端结点。,分支结点：,度不为,0,的结点，也称为非终端结点。,孩子结点：,一个结点的直接后继称为该结点的孩子结点。,双亲结点：,一个结点的直接前驱称为该结点的双亲结点。,兄弟结点：,同一双亲结点的孩子结点之间互称兄弟结点。,4,祖先结点：,一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图,6.1,中，结点,K,的祖先是,A,、,B,、,E,。,子孙结点：,一个结点的直接后继和间接后继称为该结点的子孙结点。在图,6.1,中，结点,D,的子孙是,H,、,I,、,J,、,M,。,树的度：,树中所有结点的度的最大值。,结点的层次：,从根结点开始定义，根结点的层次为,1,，根的直接后继的层次为,2,，依此类推。,树的高度（深度）：,树中所有结点的层次的最大值。,有序树：,在树,T,中，如果各子树,Ti,之间是有先后次序的，则称为有序树。,森林：,m,（,m0,）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。,5,ADT Tree,数据对象,D,：一个集合，该集合中的所有元素具有相同的特性。,数据关系,R,：若,D,为空集，则为空树。若,D,中仅含有一个数据元素，则,R,为空集，否则,R=H,，,H,是如下的二元关系：,(1),在,D,中存在唯一的称为根的数据元素,root,，它在关系,H,下没有前驱。,(2),除,root,以外，,D,中每个结点在关系,H,下都有且仅有一个前驱。,6,基本操作：,(1)InitTree,（,Tree,）：将,Tree,初始化为一棵空树。,(2)DestoryTree,（,Tree,）：销毁树,Tree,。,(3)CreateTree,（,Tree,）：创建树,Tree,。,(4)TreeEmpty,（,Tree,）：若,Tree,为空，则返回,TRUE,，否则返回,FALSE,。,(5)Root,（,Tree,）：返回树,Tree,的根。,(6)Parent,（,Tree,，,x,）：树,Tree,存在，,x,是,Tree,中的某个结点。若,x,为非根结点，则返回它的双亲，否则返回,“,空,”,。,7,(7)FirstChild,（,Tree,，,x,）：树,Tree,存在，,x,是,Tree,中的某个结点。若,x,为非叶子结点，则返回它的第一个孩子结点，否则返回,“,空,”,。,(8)NextSibling,（,Tree,，,x,）：树,Tree,存在，,x,是,Tree,中的某个结点。若,x,不是其双亲的最后一个孩子结点，则返回,x,后面的下一个兄弟结点，否则返回,“,空,”,。,8,(9)InsertChild,（,Tree,，,p,，,Child,）：树,Tree,存在，,p,指向,Tree,中某个结点，非空树,Child,与,Tree,不相交。将,Child,插入,Tree,中，做,p,所指向结点的子树。,(10)DeleteChild,（,Tree,，,p,，,i,）：树,Tree,存在，,p,指向,Tree,中某个结点，,1id,，,d,为,p,所指向结点的度。删除,Tree,中,p,所指向结点的第,i,棵子树。,(11)TraverseTree,（,Tree,，,Visit,（）：树,Tree,存在，,Visit,（）是对结点进行访问的函数。按照某种次序对树,Tree,的每个结点调用,Visit,（）函数访问一次且最多一次。若,Visit,（）失败，则操作失败。,9,二叉树的定义与基本操作,10,定义：我们把满足以下两个条件的树形结构叫做,二叉树,（,Binary Tree,）：,（,1,）每个结点的度都不大于,2,；,（,2,）每个结点的孩子结点次序不能任意颠倒。,由此定义可以看出，一个二叉树中的每个结点只能含有,0,、,1,或,2,个孩子，而且每个孩子有左右之分。我们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。,11,图,6.2,给出了二叉树的五种基本形态。,12,与树的基本操作类似，二叉树有如下基本操作：,(1)Initiate,（,bt,）：将,bt,初始化为空二叉树。,(2)Create(bt),：创建一棵非空二叉树,bt,。,(3)Destory,（,bt,）：销毁二叉树,bt,。,(4)Empty,（,bt,）：若,bt,为空，则返回,TRUE,，否则返回,FALSE,。,(5)Root(bt),：求二叉树,bt,的根结点。若,bt,为空二叉树，则函数返回,“,空,”,。,13,(6)Parent,（,bt,，,x,）：求双亲函数。求二叉树,bt,中结点,x,的双亲结点。若结点,x,是二叉树的根结点或二叉树,bt,中无结点,x,，则返回“空”。,(7)LeftChild,（,bt,，,x,）：求左孩子。若结点,x,为叶子结点或,x,不在,bt,中，则返回,“,空,”,。,(8)RightChild,（,bt,，,x,）：求右孩子。若结点,x,为叶子结点或,x,不在,bt,中，则返回,“,空,”,。,(9)Traverse,（,bt,）,:,遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。,(10)Clear,（,bt,）：清除操作。将二叉树,bt,置为空树。,14,二叉树的性质,15,性质,1:,在二叉树的第,i,层上至多有,2,i-1,个结点,(i1),。,证明：,用数学归纳法。,归纳基础：当,i,=1,时，整个二叉树只有一根结点，此时,2,i-1,=2,0,=1,，结论成立。,归纳假设：假设,i=k,时结论成立，即第,k,层上结点总数最多为,2,k-1,个。,现证明当,i=k+1,时，结论成立：,因为二叉树中每个结点的度最大为,2,，则第,k+1,层的结点总数最多为第,k,层上结点最大数的,2,倍，即,22,k-1,=2,(k+1)-1,，故结论成立。,16,性质,2:,深度为,k,的二叉树至多有,2,k,-1,个结点（,k1,）。,证明,：因为深度为,k,的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为,k,的二叉树的结点总数至多为,故结论成立。,17,性质,3:,对任意一棵二叉树,T,，若终端结点数为,n,0,，而其度数为,2,的结点数为,n,2,，则,n,0,=n,2,+1,。,证明：设二叉树中结点总数为,n,，,n1,为二叉树中度为,1,的结点总数。,因为二叉树中所有结点的度小于等于,2,，所以有,n=n,0,+n,1,+n,2,设二叉树中分支数目为,B,，因为除根结点外，每个结点均对应一个进入它的分支，所以有,n=B+1,18,又因为二叉树中的分支都是由度为,1,和度为,2,的结点发出，所以分支数目为,B=n,1,+2n,2,整理上述两式可得到,n=B+1=n,1,+2n,2,+1,将,n=n,0,+n,1,+n,2,代入上式，得出,n,0,+n,1,+n,2,=n,1,+2n,2,+1,，整理后得,n,0,=n,2,+1,，故结论成立。,19,满二叉树：,深度为,k,且有,2,k,-1,个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。图,6.3(a),所示的二叉树，即为一棵满二叉树。,满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（,1,，,2,，,，,n,）。例如图,6.3(a),所示的满二叉树的顺序表示为,(1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,，,11,，,12,，,13,，,14,，,15),。,20,完全二叉树：,深度为,k,，结点数为,n,的二叉树，如果其结点,1n,的位置序号分别与满二叉树的结点,1n,的位置序号一一对应，则为完全二叉树，如图,6.3(b),所示。,满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。,21,图,6.3,满二叉树与完全二叉树,22,性质,4,：,具有,n,个结点的完全二叉树的深度为,log,2,n,+1,。,证明：假设,n,个结点的完全二叉树的深度为,k,，根据性质,2,可知，,k-1,层满二叉树的结点总数为,n,1,=2,k-1,-1,k,层满二叉树的结点总数为,n,2,=2,k,-1,显然有,n,1,nn,2,，进一步可以推出,n,1,+1nn,2,+1,。,将,n,1,=2,k-1,-1,和,n,2,=2,k,-1,代入上式，可得,2,k-1,n2,k,，即,k-1log,2,n1,，则序号为,i,的结点的双亲结点序号为,i/2,。,（,2,）如,2in,，则序号为,i,的结点无左孩子；如,2in,，则序号为,i,的结点的左孩子结点的序号为,2i,。,（,3,）如,2i,1n,，则序号为,i,的结点无右孩子；如,2i,1n,，则序号为,i,的结点的右孩子结点的序号为,2i,1,。,24,可以用归纳法证明其中的（,2,）和（,3,）：,当,i=1,时，由完全二叉树的定义知，如果,2i=2n,，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为,2,；反之，如果,2n,，说明二叉树中不存在序号为,2,的结点，其左孩子不存在。同理，如果,2i+1=3n,，说明其右孩子存在且序号为,3,；如果,3n,，则二叉树中不存在序号为,3,的结点，其右孩子不存在。,假设对于序号为,j(1ji),的结点，当,2jn,时，其左孩子存在且序号为,2j,，当,2jn,时，其左孩子不存在；当,2j+1n,时，其右孩子存在且序号为,2j+1,，当,2j+1n,时，其右孩子不存在。,25,当,i=j+1,时，根据完全二叉树的定义，若其左孩子存在，则其左孩子结点的序号一定等于序号为,j,的结点的右孩子的序号加,1,，即其左孩子结点的序号等于（,2j+1,）,+1=2,（,j+1,）,=2i,，且有,2in,；如果,2in,，则左孩子不存在。若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加,1,，即右孩子结点的序号为,2i+1,，且有,2i+1n,；如果,2i+1n,，则右孩子不存在。,故（,2,）和（,3,）得证。,26,由（,2,）和（,3,）我们可以很容易证明（,1,）。,当,i=1,时，显然该结点为根结点，无双亲结点。当,i1,时，设序号为,i,的结点的双亲结点的序号为,m,，如果序号为,i,的结点是其双亲结点的左孩子，根据（,2,）有,i=2m,，即,m=i/2;,如果序号为,i,的结点是其双亲结点的右孩子，根据（,3,）有,i=2m+1,，即,m=,（,i-1,）,/2=i/2-1/2,，综合这两种情况，可以得到，当,i1,时，其双亲结点的序号等于,i/2,。证毕。,27,二叉树的存储结构,28,二叉树的结构是非线性的，每一结点最多可有两个后继。,二叉树的存储结构有两种：顺序存储结构和链式存储结构。,1.,顺序存储结构,图,6.4,二叉树与顺序存储结构,29,图,6.5,单支二叉树与其顺序存储结构,30,2.,链式存储结构,对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子：,LChild,Data,RChild,其中，,LChild,域指向该结点的左孩子，,Data,域记录该结点的信息，,RChild,域指向该结点的右孩子。,31,用,C,语言可以这样声明二叉树的二叉链表结点的结构：,typedef struct Node,DataType data;,struct Node*LChild;,struct Node*RChild;,BiTNode,*BiTree;,有时，为了便于找到父结点，可以增加一个,Parent,域，,Parent,域指向该结点的父结点。该结点结构如下：,LChild,Data,parent,RChild,32,图,6.6,二叉树和二叉链表,33,若一个二叉树含有,n,个结点，则它的二叉链表中必含有,2n,个指针域，其中必有,n,1,个空的链域。此结论证明如下：,证明：分支数目,B=n-1,，即非空的链域有,n-1,个，故空链域有,2n-(n-1)=n+1,个。,不同的存储结构实现二叉树的操作也不同。如要找某个结点的父结点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。可见，在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。,34,二叉树的遍历,35,图,6.7,二叉树结点的基本结构,36,我们用,L,、,D,、,R,分别表示遍历左子树、访问根结点、遍历右子树，那么对二叉树的遍历顺序就可以有六种方式：,(1),访问根，遍历左子树，遍历右子树（记做,DLR,）。,(2),访问根，遍历右子树，遍历左子树（记做,DRL,）。,(3),遍历左子树，访问根，遍历右子树（记做,LDR,）。,(4),遍历左子树，遍历右子树，访问根（记做,LRD,）。,(5),遍历右子树，访问根，遍历左子树（记做,RDL,）。,(6),遍历右子树，遍历左子树，访问根（记做,RLD,）。,37,注意：先序、中序、后序遍历是递归定义的，即在其子树中亦按上述规律进行遍历。,下面就分别介绍三种遍历方法的递归定义。,先序遍历（,DLR,）操作过程：,若二叉树为空，则空操作，否则依次执行如下,3,个操作：,(1),访问根结点；,(2),按先序遍历左子树；,(3),按先序遍历右子树。,38,中序遍历（,LDR,）操作过程：,若二叉树为空，则空操作，否则依次执行如下,3,个操作：,(1),按中序遍历左子树；,(2),访问根结点；,(3),按中序遍历右子树。,后序遍历（,LRD,）操作过程：,若二叉树为空，则空操作，否则依次执行如下,3,个操作：,(1),按后序遍历左子树；,(2),按后序遍历右子树；,(3),访问根结点。,39,先序遍历：,A,、,B,、,D,、,F,、,G,、,C,、,E,、,H,。,中序遍历：,B,、,F,、,D,、,G,、,A,、,C,、,E,、,H,。,后序遍历：,F,、,G,、,D,、,B,、,H,、,E,、,C,、,A,。,图,6.8,二叉树,40,中序遍历二叉树的递归过程,41,最早提出遍历问题是对存储在计算机中的表达式求值。例如：（,a+b*c,）,-d/e,。该表达式用二叉树表示如图,6.9,所示。当我们对此二叉树进行先序、中序、后序遍历时，便可获得表达式的前缀、中缀、后缀书写形式：,前缀：,-+a*bc/de,中缀：,a+b*c-d/e,后缀：,abc*+de/-,其中中缀形式是算术表达式的通常形式，只是没有括号。前缀表达式称为波兰表达式。算术表达式的后缀表达式被称作逆波兰表达式。在计算机内，使用后缀表达式易于求值。,42,图,6.9,算术式的二叉树表示,43,