四川大学：《数据结构》课程教学资源（PPT课件讲稿）第五章 树和二叉树 Tree & Binary Tree

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() ) // 遍历

插入类: IntrEe(&T)∥/初始化置空树 CreateTree(&t, definition) ∥按定义构造树 Assign(t, cur e, value) ∥给当前结点赋值 InsertChild(&t, &p, i, c) ∥将以c为根的树插入为结点p的第课棵子树 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 InitTree(&T) // 初始化置空树 插入类： CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树

删除类 Clear Tree(&T)∥将树清空 Destroy Tree(&T)∥/销毁树的结构 Delete Child(&T, &p, i) ∥删除结点p的第课棵子树 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 ClearTree(&T) // 将树清空 删除类： DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树

基本术语 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 基 本 术 语

结点数据元素+若干指向子树的分支 结点的度分支的个数 树的度树中所有结点的度的最大值 叶子结点度为零的结点 分支结点度大于零的结忘D H 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 结点 结点的度 树的度 叶子结点 分支结点 数据元素+若干指向子树的分支 分支的个数 树中所有结点的度的最大值 度为零的结点 度大于零的结点 D H I J M

(从根到结点的路径A 由从根到该结点④ EGGOG 所经分支和结点构 成 孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 (从根到结点的)路径 孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点 由从根到该结点 所经分支和结点构 成 A B C D E F G H I J K L M