山东理工大学：《数据结构》课程教学课件（数学）CH6 树和二叉树

第膏附我户天尉 70

70

6.1树的类型定义和基本术语 6.2二叉树的类型定义及性质 6.3二叉树的存储结构 6.4二叉树的通历 6.5线索二叉树 6.6树和森林 6.7哈夫曼树与哈夫曼编码

6.1 树的类型定义和基本术语 6.2 二叉树的类型定义及性质 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码

6.1 树的类型定义和基本术语

6.1 树的类型定义和基本术语

树是一类重要的非线性数据结构，是以分支关系定义 的层次结构。 。树的定义 ·定义：树(Tree)是n(n≥0)个结点的有限集T,其中： 当n≥1时，有且仅有一个特定的结点，称为树的根(Root), 当>1时，其余结点可分为m(m>0)个互不相交的有限集 T,T2,.Tm,其中每一个集合本身又是一棵树，称为根的 子树(SubTree)。 ·特点： -树中各子树是互不相交的集合

• 定义：树(Tree)是n(n≥0)个结点的有限集T，其中： –当n≥1时，有且仅有一个特定的结点，称为树的根(Root)， –当n 1时，其余结点可分为m(m>0)个 的有限集 T1,T2,.Tm，其中每一个集合本身又是一棵树，称为根的 子树(SubTree)。 • 特点： –树中各子树是互不相交的集合。 

只有根结点的树 有子树的树 根 子树

A A B C D E F G H I J K L M

ADT Tree 数据对象D: D是具有相同特性的数据元素的集合。 数据关系R: 若D为空集，则称为空树； 否则： (①在D中存在唯一的称为根的数据元素root, (2)当n>1时，其余结点可分为m(m>0)个互 不相交的有限集T,T2,Tm,其中每一 个子集本身又是一棵树，称为根root的子树。 基本操作P: ADT Tree

数据对象 D： D是具有相同特性的数据元素的集合。 (1) 在D中存在唯一的称为根的数据元素root, (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1 , T2 , ., Tm, 其中每一 个子集本身又是一棵树,称为根root的子树。 数据关系 R： 若D为空集，则称为空树； 否则: 基本操作 P：

基本操作： +查找类 +插入类 +删除类 酸

基本操作： 查 找 类 插 入 类 删 除 类

查找类： Root(T)∥求树的根结点 Value(T,cure)/∥求当前结点的元素值 Parent(T,cure)∥求当前结点的双亲结点 LeftChild(T,cure)∥求当前结点的最左孩子 RightSibling(T,cur_e)∥求当前结点的右兄弟 TreeEmpty(T)l∥判定树是否为空树 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() ) // 遍历 树中结点的最大层次

插入类： InitTree(&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棵子树

删除类： ClearTree(&T)/将树清空 DestroyTree(&T)∥销毁树结构 DeleteChild(&T,&p,i) ∥删除T中结点p的第棵子树

ClearTree(&T) // 将树清空 删除类： DestroyTree(&T) // 销毁树结构 DeleteChild(&T, &p, i) // 删除T中结点p的第i棵子树