数据结构讲义第6章节.pptVIP

第六章 树和二叉树 树是计算机算法最重要的非线性结构。 树中每个数据元素至多有一个直接前驱，但可以有多个直接后继。 树是一种以分支关系定义的层次结构。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §6.1 树的基本概念 一、树（Tree）的定义 a.树是n(≥0)结点组成的有限集合。{N.沃恩} (树是n(n≥1)个结点组成的有限集合。{D.E.Knuth}) 在任意一棵非空树中： ⑴有且仅有一个没有前驱的结点----根(root)。 ⑵当n1时，其余结点有且仅有一个直接前驱。 ⑶所有结点都可以有０个或多个后继。 b. 树是n(n≥0)个结点组成的有限集合。 在任意一棵非空树中： ⑴有一个特定的称为根（root）的结点。 ⑵当n1时，其余结点分为ｍ（ｍ≥0）个互不相交的子集T1，T2，…，Tm。 每个集合本身又是一棵树，并且称为根的子树（subtree） 树的固有特性---递归性。即非空树是由若干棵子树组成，而子树又可以由若干棵更小的子树组成。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 树的基本概念 （3）中有13个结点，其中Ａ是树根，其余结点分成三个互不相交的子集。 Ｔ1={B,E,F,K,L} Ｔ2={C,G} Ｔ3={D,H,I,J,K} T1,T2,T3都是根A的子树，它们本身又是一棵树。 T1:根B {E,K,L} {F} 根E {k} {L} T2:根C {G} T3:根D {H,M} {I} {J} 根H {M} Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 树的基本操作 二、树的基本操作 1、InitTree(T) 初始化 2、DestroyTree(T) 撤消树 3、creatTree(T,F) 按F的定义生成树 4、ClearTree(T) 清除 5、TreeEmpty(T) 判树空 6、TreeDepth(T) 求树的深度 7、Root(T) 返回根结点 8、Parent(T,x) 返回结点 x 的双亲 9、Child(T,x,i) 返回结点 x 的第i 个孩子 10、InsertChild(T,p,i,x) 把 x 插入到 P的第i棵子树处 11、DeleteChild(T,p,i) 删除结点P的第i棵子树 12、traverse(T) 遍历 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 树的基本术语 树的结点：包含一个数据元素及若干指向子树的分支。 ●结点的度: 结点拥有子树的数目 ●叶结点 : 度为零的结点 ●分枝结点: 度非零的结点 ●树的度 : 树中各结点度的最大值 ●孩子 : 树中某个结点的子树的根 ●双亲 : 结点的直接前驱 ●兄弟 : 同一双亲的孩子互称兄弟 ●祖先 : 从根结点到某结点j 路径上的所有结点（不包括指定结点）。 ●子孙 : 某结点的子树中的任一结点称为该结点的子孙 ●结点层次: 从根结点到某结点 j 路径上结