教案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 初始条件：树T已存在 操作结果：将树T清为空树 TreeEmpty(T) 初始条件：树T己存在 操作结果：若T为空树，则返回TRUE,否则返回FALSE TreeDepth(T) 初始条件：树T已存在 操作结果：返回树T的深度 Root(T) 初始条件：树T已存在 操作结果：返回T的根 Value(T,cur e) 初始条件：树T己存在，cure是T中某个结点 操作结果：返回cure的值 Assign(T,&cur_e,value) 初始条件：树T已存在，cure是T中某个结点 操作结果：结点cure赋值为value Parent(T,cur_e) 初始条件：树T已存在，cure是T中某个结点 操作结果：若cure是T的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T,cur_e) 初始条件：树T己存在，cure是T中某个结点 操作结果：若cure是T的非叶子结点，则返回它的最左孩子，否则返 回“空” RightSibling(T,cur_e) 初始条件：树T已存在，cure是T中某个结点 操作结果：若cure有右兄弟，则返回它的右兄弟，否则返回“空” InsertChild(&T,p,i,c) 初始条件：树T已存在，p指向T中某个结点，1≤≤p所指结点的度 +1,非空树c与T不相交 操作结果：插入c为T中p所指结点的第i棵子树。 DeleteChild(&T,p,i) 初始条件：树T己存在，P指向T中某个结点，1≤≤p所指结点的度 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree(T.visit()) 初始条件：树T已存在，visit是对结点操作的应用函数 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。 一旦visit()失败，则操作失败 ADT Tree 6.2二叉树 一般树的度不定，直接考虑其操作比较困难，故首先考虑度为二的树。这里引入二叉树。 6.2.1二叉树的定义 1、二叉树的特殊性 ·0≤度≤2 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第1页程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 1 页 第六章 树和二叉树 基本概念、遍历算法及其应用 初始条件：树 T 已存在 操作结果：将树 T 清为空树 TreeEmpty(T) 初始条件：树 T 已存在 操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE TreeDepth(T) 初始条件：树 T 已存在 操作结果：返回树 T 的深度 Root(T) 初始条件：树 T 已存在 操作结果：返回 T 的根 Value(T, cur_e) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的值 Assign(T, &cur_e, value) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：结点 cur_e 赋值为 value 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 有右兄弟，则返回它的右兄弟，否则返回“空” 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 棵子树。 TraverseTree(T, visit( ) ) 初始条件：树 T 已存在，visit 是对结点操作的应用函数 操作结果：按某种次序对 T 的每个结点调用函数 visit( )一次且至多一次。 一旦 visit( )失败，则操作失败 }ADT Tree 6.2 二叉树 一般树的度不定，直接考虑其操作比较困难，故首先考虑度为二的树。这里引入二叉树。 6.2.1 二叉树的定义 1、二叉树的特殊性 ·0≤度≤2