第六章树 树是一类重要的非线性数据结构，是以分支关 系定义的层次结构 §6.1树的定义和基本术语 ★定义 定义：树(tree)是n(n>0)个结点的有限集T,其中： ●有且仅有一个特定的结点，称为树的根(roo) ●当n>1时，其余结点可分为m(m>0)个互不相交 的有限集T1,T2,..Tm,其中每一个集合本身 又是一棵树，称为根的子树(subtree) 必特点： ●树中至少有一个结点一根 ●树中各子树是互不相交的集合
第六章 树 树是一类重要的非线性数据结构，是以分支关 系定义的层次结构 §6.1 树的定义和基本术语 定义 ❖定义：树(tree)是n(n>0)个结点的有限集T，其中： ⚫有且仅有一个特定的结点，称为树的根(root) ⚫当n>1时，其余结点可分为m(m>0)个互不相交 的有限集T1,T2,……Tm，其中每一个集合本身 又是一棵树，称为根的子树(subtree) ❖特点： ⚫树中至少有一个结点——根 ⚫树中各子树是互不相交的集合
只有根结点的树 有子树的树 根 子树
A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树
数据对象D: D是具有相同特性的数据元素的集合。 数据关系R: 若D为空集，则称为空树。 否则： (1)在D中存在唯一的称为根的数据元素root; (2)当n>1时，其余结点可分为m(m>0)个互 不相交的有限集T1,T2,,Tm,其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树
数据对象 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() ) // 遍历
插入类： 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)∥将树清空 Destroy Tree(&T)∥销毁树的结构 DeleteChild(&T,&p,i) /删除结点p的第棵子树
ClearTree(&T) // 将树清空 删除类： DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
线性结构 树型结构 第一个数据元素 根结点 (无前驱) (无前驱) 最后一个数据元素 多个叶子结点 (无后继) (无后继) 其它数据元素 其它数据元素 (一个前驱、 (一个前驱、 一个后继) 多个后继) 三
线性结构 树型结构 第一个数据元素 (无前驱) 根结点 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继)
树的表示方法 列如： G H M
A B C D E F G H I J K L M 例如: 树的表示方法
]嵌套集合形式 B b)广义表形式 G A(E,FK,L少GD(H,L四) 树根 T
b)广义表形式 A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 树根 T1 T2 T3 A B D C E K L F H M I J G a)嵌套集合形式