ADT Tree 轰据对象：D-∈mSet,i1,2n,n≥0； 6.1树的定义-基本术语 数据关系：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R=田，H是如下二元 。基本术语 关系： 第1层 1)在D中存在难-的称为根的数据元素r0ot,它在关系H下无丽 第2层 高度为4 2)者D红oot≠中，则存在D-红a0t的一个刻分D1,D2,,D ®自@面①①第3层 mP0)(D表示构成第i保子树的结点集，对任煮j手k1≤jk≤ 令结点 ®① m)有D;门Dx=中，且对任煮的i1≤i≤m,唯一存在数据元素均∈ 孩子 一第4层 D,有<00此，>∈H(H表示结点之间的父子关系方 结点的度 ”丸亲 ◆树的度 )对应于D-红ot的分，Hro0t,P,,00t2有唯-的 令结点的层次 ◆兄弟 ◆树的深度/高度 一个划分H,压。，Hnm0)(氏表示第i探子树中的父子关系， 令终增结点（叶子） 祖先 有序树 对任意j≠k1jk≤m)有HH,=中，且对任意0≤i≤m,H是 冬非终墙结点（分支结点） 令子开 ◆无序树 D:上的二元关系，①，H)是一霖符合本定义的树，称为根r0ot的 必内部结点 ◆堂兄弟 令森林 子树。 71106 回 图 基本操作： InitTree(&T) 操作结果：构造空树T Value(T,cur_e) DestroyTree(&T) 初始条件：树T已存在，cre是T中某个结点 初始条件：树T已存在 操作结果：返回cur_e的值 操作结果：销毁树T Assign(T,&cur_e,value) ClearTree(&T) 初始条件：树T已存在，cre是T中某个结点 初始条件：树T已存在 操作结果：结点cure赋值为aue 操作结果：将树T清为空树 Parent(T,cur e) TreeEmpty(T) 初始条件：树T已存在，cre是T中某个结点 初始条件：树T已存在 操作结果：若ce是T的非根结点，则返国它的双亲，否则函数值 操作结果：若T为空树，则返回TRU亚，否则返回FALSE 为“空” CTreeDepth(T) LeftChild(T,cur e) 初始条件：树T已存在 初始条件：树T已存在，cure是T中某个结点 操作结果：返回树T的深度 操作结果：若cre是T的非叶子结点，则返回它的最左孩子，否则 Root(T 返国“空” 初始条件：树T已存在 操作结果：返回T的根 图 10/106 图 RightSibling(T,cur e) 初条传：树T已存在，re是T中某个结点 操作结果：着cm_e有右兄弟，则返回它的右兄弟，否则返回“空” 6.1树的定义-ADT Tree InsertChild(&T p,i,c) 初始条作：树T已存在，p指舟T中某个结点，1≤1≤p所指结点的度 ADT Tree +上，非空树c与T不相交 操作结果：插入c为T中p所指结点的第1根子树， ·查找：Parent(T,cur_e)LeftChild(T,cur_e) DeleteChild(&T,p,i) Rightsibling(T,cur_e) 初衡承作：树T已存在印指向T中某个结点，1i≤p所指结点的度 ,插入：InsertChild(&T,&p,i,c) 操作结果：测除T中p所指结点的第1樱子树· TraverseTree(T,visit() ,则除：DeleteChild(&T,&p,i) 初始条传：树T已存在，是州结点操作的应用函数 ,通历：TraverseTree(T,Visit()) 操作结果：技某种次序对T的每个结点调用函数is()一次且至多一 次。一且s()失败，则操作失数 JADT Tree 1/106 图 12/106 图7/106 ™结点 ™结点的度 ™结点的层次 ™终端结点(叶子) ™非终端结点(分支结点) ™内部结点 6.1 树的定义-基本术语 „ 基本术语 A B C D E F G H I J K L 第1层 第2层 第3层 第4层 高度为4 ™孩子 ™双亲 ™兄弟 ™祖先 ™子孙 ™堂兄弟 ™树的度 ™树的深度/高度 ™有序树 ™无序树 ™森林 8/106 9/106 10/106 11/106 12/106 6.1 树的定义-ADT Tree „ ADT Tree „ 查找：Parent(T,cur_e) LeftChild(T, cur_e) RightSibling(T, cur_e) „ 插入：InsertChild(&T, &p, i, c) „ 删除：DeleteChild(&T, &p, i) „ 遍历：TraverseTree(T, Visit())