引用型操作} TreeE 初始祭件:树T存在。 操作结果:若T为空树,则返回TRUE,否则 返回 FALSE。 TreeDepth(T) 攔罪结果:回传深度。 Root(T) 初始条件:树T存在 操作结果:返回T的根。 Value T, cur e 初始条件:树T存在,cure是T中某个结点。 操作结果:返回cure的值
• {引用型操作} TreeEmpty(T); 初始条件：树 T 存在。 操作结果：若 T 为空树，则返回 TRUE，否则 返回 FALSE。 TreeDepth(T); 初始条件：树T存在。 操作结果：返回T的深度。 Root(T); 初始条件：树 T 存在。 操作结果：返回 T 的根。 Value(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：返回 cur_e 的值
° Parent(T,cure} 操罪结果:若Cu日是的菲结点,则返它的双亲,否 则返回"空"。 Leftchild(T, cur 初始条件:树存在,cure是T中某个结点。 操作结果:若cue是T的菲叶子结点,则返回它的最左孩 子,否则返回"空"。 Ril ghtsibling(T, cur_e) 初始条件:树T存在,cure是T中某个结点。 操作结果:若cure有右兄弟,则返回它的右兄弟,否则 返回"空"。 Traverse Tree(T, visit 初始条件:树T存在,st是对结点操作的应用函数。 操作结果:按某种次序对T的每个结点调用函数vs(0 次且至多一次。一旦 visit0失败,则操作失败
• Parent(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 是T的非根结点，则返回它的双亲，否 则返回"空" 。 LeftChild(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 是T的非叶子结点，则返回它的最左孩 子，否则返回"空" 。 RightSibling(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则 返回"空" 。 TraverseTree(T, visit()); 初始条件：树T存在，visit 是对结点操作的应用函数。 操作结果：按某种次序对 T 的每个结点调用函数 visit() 一 次且至多一次。一旦 visit() 失败，则操作失败
加工型操作 Assign(Ti cur_e, value); 初始条件:树T存在,cure是T中某个结点。 操作结果:结点cure赋值为vaue ClearTree(&T) 初始条件:树T存在。 操作结果:将树T清为空树。 Insertchild(&T, &p, i,c); 初始条件:树T存在,P指向T中某个结点,1sp所指 结点的度1菲空树c与木相交。 操作结 果:插人c为T中p所指结点的第i棵子树。 Delete Child(&T, 点的度始条件:树T存在,P指向T中某个结点,1指结 操作结果:删除T中p所指结点的第i棵子树。 JADT Tree
• {加工型操作} Assign(T, cur_e, value); 初始条件：树T存在，cur_e 是 T 中某个结点。 操作结果：结点 cur_e 赋值为 value。 ClearTree(&T); 初始条件：树 T 存在。 操作结果：将树 T 清为空树。 InsertChild(&T, &p, i, c); 初始条件：树 T 存在，p 指向T中某个结点，1≤i≤p 所指 结点的度＋1，非空树 c 与 T 不相交。 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。 DeleteChild(&T, &p, i); 初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 指结 点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。 } ADT Tree
树和线性结构对照: 线性结构 树结构 存在唯一的没有存在唯一的没有前 驱 区的 的“首元素 根结点 存在唯一的没有存在多个没有后继 后继 的 的"尾元素 叶子 其余元素均存在其余结点均存在唯 的 的"前驱元素“和 前驱(双亲)结 点“和多 的“后继元素 个“后继(孩子)结 点
树和线性结构对照：
第二节二叉树类型 定义:二叉树是另一种树形结构。它与树形 结构的区别是: (1)每个结点最多有两棵子树; (2)子树有左右之分。 二叉树也可以用递归的形式定义。 即:二叉树是n(n≥0)个结点的有限集合。 当n=0时,称为空二叉树;当n>0时,有且 仅有一个结点为二叉树的根,其余结点被分 成两个互不相交的子集,一个作为左子集, 另一个作为右子集,每个子集又是一个二叉 树
第二节 二叉树类型 • 定义：二叉树是另一种树形结构。它与树形 结构的区别是： • （1）每个结点最多有两棵子树； • （2）子树有左右之分。 • 二叉树也可以用递归的形式定义。 即：二叉树是n（n≥0）个结点的有限集合。 当n=0时，称为空二叉树；当n>0时，有且 仅有一个结点为二叉树的根，其余结点被分 成两个互不相交的子集，一个作为左子集， 另一个作为右子集，每个子集又是一个二叉 树