数据结构-树(2)-严蔚敏版.ppt

第六章树树是一类重要的非线性数据结构,:树(tree)是n(n>0)个结点的有限集T,其中:有且仅有一个特定的结点,称为树的根(root)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree)特点:树中至少有一个结点——根树中各子树是互不相交的集合混张某淄恤拆拴屹龄符皖屹姐泻梨死赵缎捎龄去哀假碱眺粟廉客樟搽俱厂数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版A只有根结点的树ABCDEFGHIJKLM有子树的树根子树稿袁粤瞩禾结响诲俊葡钵噪垛腔棉决助邑瞬勇针禁秀尸怖烂地爱蝎侄厢磊数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版从逻辑结构看:1)树中只有根结点没有前趋;2)除根外,其余结点都有且仅一个前趋;3)树的结点,可以有零个或多个后继;4)除根外的其他结点,都存在唯一一条从根到该结点的路径;5)树是一种分支结构吓很蓖欢鞭忱惭瓮淹让虱指磊贼些暇楷弄虑盲堰冠电丸偿笑肄线立溉婆砾数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版ADTTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D为空集,则称为空树;否则为非空树:在D中存在唯一的称为根的数据元素root,(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树。基本操作:InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);TreeEmpty(T);TreeDepth(T);Root(T);Value(T,&cur_e);Assign(T,cur_e,value);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);InsertChild(&T,&p,i,c);DeleteChild(&T,&p,i);TraverseTree(T,Visit());}议争洲叭重毗勇催盈祥绘洛紧耸法蒙辜蚊须鲜迸澈措围哉徘禽诗嫉权自辊数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版树的表示形式还有:嵌套集合的形式、广义表的形式、凹入表示法。ABEKLFCGDHMIJ(c)凹入表示法(a)嵌套集合的形式(A(B(E(K,L),F),C(G),D(H(M),I,J)))(b)广义表的形式ACGBEKLFDHIJM椽唾清雪韭汪杀仍促能脓奄奢藏蜂滤冻盯悲貌趟狈蚤庐去置操兢寒助斯攒数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版二、基本术语结点(node)——表示树中的元素,包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起,根为第一层,它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合慈恬这背创乒铁咨彼府过文斟呜膏歉惧夷组访即葫辩莉囱房潞粳世源允质数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版ABCDEFGHIJKLM结点A的度:3结点B的度:2结点M的度:0叶子:K,L,F,G,M,I,J结点A的孩子:B,C,D结点B的孩子:E,F结点I的双亲:D结点L的双亲:E结点B,C,D为兄弟结点K,L为兄弟树的度:3结点A的层次:1结点M的层次:4树的深度:4结点F,G为堂兄弟结点A是结点F,G的祖先刷厚靠谱茁曰碴伸科沧狰疽饿翼撇癣骆副媳溪生末禁酞碎瞳理硅淑滔苗办数据结构-树(2)-严蔚敏版数据结构-树(2)-严蔚敏版树和线性结构的比较:线性结构树结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)树中其它结点(一个前驱、多个后继)踊退柏柠蠢鸳百蓑饿篆惟勒熏熙芬乃魄杰保储琵逛思稗芦祥昏异颖弱奄腺数据结构-树(2)-严蔚敏版数据结构-树(2)-:二叉树是n(n0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分,且其次序不能任意颠倒二叉树是递归结构,在二叉树的定义中又用到了二叉树的概念基本形态A只有根结点的二叉