第6章树和二叉树案例.ppt

第6章 树和二叉树 树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。 6.1 树的定义和基本术语  树(Tree)是n(n≥0)个结点的有限集。在任意一棵非空树中： (1)有且仅有一个特定的称为根(Root)的结点； (2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。 例如， (a)是只有一个根结点的树；(b)是有13个结点的树，其中A是根，其余结点分成三个互不相交的子集：T1= {B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2和T3都是根A的子树，且本身也是一棵树。 树的逻辑结构除了根结点外，每个结点有且仅有一个直接前驱。所有结点可以有多个直接后继。1对多 (a)只有根结点的树 (b)一般的树 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性。 基本术语 树的结点包含一个数据元素及若干指向其子树的分支。 度为0的结点称为叶子(1eaf)或终端结点。 度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。 树的度是树内各结点的度的最大值。 结点的子树的根称为该结点的孩子(child)，相应地，该结点称为孩子的双亲(Parent)。 同一个双亲的孩子之间互称兄弟(sibling) 结点的祖先是从根到该结点所经分支上的所有结点。 结点的层次(level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第i层，则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟。 树中结点的最大层次称为树的深度(Depth)或高度。 如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树。 就逻辑结构而言，任何一棵树是一个二元组Tree= (root，F)，其中：root是数据元素，称做树的根结点；F是m(m≥0)棵树的森林；F=(T1，T2，…，Tn)，其中Ti=(ri，Fi)称做根root的第i棵子树；当m!=0时，在树根和其子树森林之间存在下列关系： RF={root , ri | i=1 , 2 , … , m , m 0 } 抽象数据类型树的定义。 ADT Tree { 数据对象D： D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}， H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若D-{root}!=Φ，则存在D-{root)的一个划分D1，D2，…，Dm (m0)，对任意j!=k(1≤j，k≤m)有Dj∩Dk=Φ，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di，有root，xi∈H； (3)对应于D-{root}的划分，H-{root，x1，…，root，xm}有唯一的一个划分H1，H2，…，Hm(m0)，对任意j!=k(1≤j，k≤m)有Hj∩Hk=Φ，对任意i(1≤i≤m)，Hi是Di上的二元关系，（Di ,{Hi})是一棵符合本定义的子树，称为根root的子树。 基本操作： InitTree(＆T)； 操作结果：构造空树T。 DestroyTree(T)； 初始条件：树T存在。 操作结果：销毁树T。 CreateTree(T，definition)； 初始条件：definit