文档介绍：1第6章树和二叉树(Tree&BinaryTree):非线性结构,一个直接前驱,但可能有多个直接后继(1:n). 树的定义2. 若干术语3. 逻辑结构4. 存储结构5. :过去许多书籍中都定义树为n≥1,曾经有“空树不是树”的说法,但现在树的定义已修改。注2:树的定义具有递归性,即树中还有树。由一个或多个(n≥0)结点组成的有限集合T,有且仅有一个结点称为根(root),当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树。4树的表示法有几种:图形表示法嵌套集合表示法广义表表示法目录表示法左孩子-右兄弟表示法这些表示法的示意图参见教材P120树的抽象数据类型定义参见教材P118-1195图形表示法:教师学生其他人员2000级2001级2002级2003级……太原科技大学经管应科外语……叶子根子树6广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边7左孩子-右兄弟表示法ABCDEFGHIJKLM数据左孩子右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))8树的抽象数据类型定义(见教材P118-119)ADTTree{数据对象D:数据关系R:基本操作P:}ADTTree若D为空集,则称为空树;//允许n=0若D中仅含一个数据元素,则R为空集;其他情况下的R存在二元关系:①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明D是具有相同特性的数据元素的集合。//——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点(孩子之间互称兄弟)——即双亲位于同一层的结点(但并非同一双亲)——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJMLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序,不能互换(左为第一)——结点各子树可互换位置。(续)——即树的数据元素——结点挂接的子树数(有几个直接后继就是几度,亦称“次数”)结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK——从根到该结点的层数(根结点算第一层)——即度为0的结点,即叶子——即度不为0的结点(也称为内部结点)——所有结点度中的最大值(Max{各结点的度})——指所有结点中最大的层数(Max{各结点的层次})问:右上图中的结点数=;树的度=;树的深度=1334