chap05数据结构树型结构.pdfVIP

第五章 树型结构 • 线性结构: 反映相邻关系 • 层次关系? • 树（Tree）型结构。 • 以分支关系定义的层次结构。 树的基本概念 • 1 树的定义 • 树 （递归的描述） • 空树 • 子树 总结出树结构的特点： 树的形式定义——抽象 • 用二元组表示： Tree=（ D , R ） 若D φ,则Tree为空树，否则 D={ root } ∪Df , root 为树的根结点 ; D = D ∪ D ∪ ... ∪ D ，且D ∩ D φ ( i≠j , 1≤ i,j≤ f 1 2 m i j m ) ; R= { r } 树的逻辑表示方法 • (1)树形表示方法。 • (2)文氏图表示方法。 • (3)凹入表示方法。 • (4)广义表表示方法。 树的基本术语 • 1.根 • 2.孩子、双亲和兄弟 、祖先、子孙 • 3.分支结点和叶子结点 • 4.结点的度和树的度 • 5.结点的层数和树的深度 • 6.路径和路径长度 • 7.有序树和无序树 • 8.森林 树的操作（实际生活的抽象） （1）求根操作 Root(x) 求出当前树中结点x的根结点； （2）求双亲操作 Parent(x) 求出当前树中结点x的双亲结点； （3）求孩子操作 Child(x，i) 求出当前树中结点x的第i个孩子结点； （4）插入子树操作 Insert(x,i,s) 当前树中插入根结点为s的子树，并 作为结点x的第i棵子树； （5）删除子树操作 Delete(x,i) 在当前树中删除结点x的第i棵子树； （6）树的遍历操作 Travel( ) 按某种次序依次访问当前树中的各个 结点，并使每个结点只被访问一次； （7）清除操作 Clear( ) 将当前树置为空树； （8）求树高 Depth( ) 求出树的高度； （9）树建立操作 Create( ) 建立一棵非空的树并成为当前树； 树的抽象数据类型 template class T class Tree { //对象: 树是由n ( ≥0) 个结点组成的有限集合。在 // 类界面中的position 是树中结点的地址。在顺序 //存储方式下是下标型, 在链表存储方式下是指针 //型。T 是树结点中存放数据的类型, 要求所有结 // 点的数据类型都是一致的。 public: Tree (); ~Tree (); BuildRoot (const T value); //建立树的根结点 position FirstChild(position p); //返回p 第一个子女地址, 无子女返回0 position NextSibling(position p); //返回p 下一兄弟地址, 若无下一兄弟返回0 position Parent(position p); //返回p 双亲结点地址, 若p 为根返回0 T getData(position p); //返回结点p 中存放的值 bool InsertChild(position p, T value); //在结点p 下插入值为value 的新子女, 若插 //入失败, 函数返回false, 否则返回true bool DeleteChild (position p, int i); //删除结点p 的第i 个子女及其全部子孙结 //点, 若删除失败, 则返回false,