Chapter 5 Tree Binary Tree 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 Chapter 5 Tree & Binary Tree
树的类烈定义 n(n>0)个元素的有 限亮合 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 树的类型定义 n(n≥0)个元素的有 限集合
树的类型定义 数据对象D D是具有相同特性的数据元素的集合。 数据关系R 若D为空集,则称为空树。 否则 (1)在D中存在唯一的称为根的数据元素root (2)当n>1时,其余结点可分为m(m>0)个互 不相交的有限集T1,T2,…,Tm,其中每 棵子集本身又是一棵符合本定义的树, 称为根ro的子树。 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 数据对象 D： D是具有相同特性的数据元素的集合。 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1 , T2 , …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系 R： 树的类型定义
基本操作 +查找类 +插入类 +删除类 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 基本操作： 查 找 类 插 入 类 删 除 类
查找类 Root(T)∥求树的根结点 Value(T,cure)∥求当前结点的元素值 Parent(T,cure)∥求当前结点的双亲结点 Leftchild(T,cure)∥/求当前结点的最左孩子 Rightsibling(T,cure)∥求当前结点的右兄弟 TreeEmpty(T)∥判定树是否为空树 TreeDepth(T)∥求树的深度 TraverseTree((T, Visit0)∥遍历 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 Root(T) // 求树的根结点 查找类： Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历