教裂 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：若cure是T的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T,cur_e) 初始条件：二叉树T己存在，cure是T中某个结点 操作结果：若cure是T的非叶子结点，则返回它的左孩子，否则返回 “空” RightChild(T,cur_e) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：若cure有右孩子，则返回它的右孩子，否则返回“空” LeftSibling(T,cur e) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：返回cure的左兄弟，若cure是T的左孩子或无左兄弟， 则返回“空” RightSibling(T,cur_e) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：返回cure的右兄弟，若cure是T的右孩子或无右兄弟， 则返回“空” InsertChild(&T,p,LR,c) 初始条件：二叉树T已存在，p指向T中某个结点，LR为0或1，非空 二叉树c与T不相交 操作结果：插入c为T中p所指结点的左或右子树。p所指结点的原有 左或右子树则成为c的右子树 DeleteChild(&T,p,LR) 初始条件：二叉树T已存在，p指向T中某个结点，LR为0或1 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse(T,visit()) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：先序遍历T,对每个结点调用函数visit()一次且仅一次。一旦 visit()失败，则操作失败 InOrderTraverse(T,visit()) 初始条件：二叉树T己存在，visit是对结点操作的应用函数 操作结果：中序遍历T,对每个结点调用函数visit()一次且仅一次。一 旦visit()失败，则操作失败 PostOrderTraverse(T,visit()) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：后序遍历T,对每个结点调用函数vist()）一次且仅一次。一 旦visit()失败，则操作失败 LevelOrderTraverse(T,visit()) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：层序遍历T,对每个结点调用函数vist()一次且仅一次。一 旦visit()失败，则操作失败 ADT BinaryTree 6.2.2二叉树的性质 1、性质1：第i层至多有2-1个结点（由每个结点最多只有2个孩子推出) 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第3页程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 3 页 第六章 树和二叉树 基本概念、遍历算法及其应用 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 是 T 的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 是 T 的非叶子结点，则返回它的左孩子，否则返回 “空” RightChild(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 有右孩子，则返回它的右孩子，否则返回“空” LeftSibling(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的左兄弟，若 cur_e 是 T 的左孩子或无左兄弟， 则返回“空” RightSibling(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的右兄弟，若 cur_e 是 T 的右孩子或无右兄弟， 则返回“空” InsertChild(&T, p, LR, c) 初始条件：二叉树 T 已存在，p 指向 T 中某个结点，LR 为 0 或 1，非空 二叉树 c 与 T 不相交 操作结果：插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点的原有 左或右子树则成为 c 的右子树 DeleteChild(&T, p, LR) 初始条件：二叉树 T 已存在，p 指向 T 中某个结点，LR 为 0 或 1 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 PreOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：先序遍历 T，对每个结点调用函数 visit()一次且仅一次。一旦 visit()失败，则操作失败 InOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：中序遍历 T，对每个结点调用函数 visit( )一次且仅一次。一 旦 visit( )失败，则操作失败 PostOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：后序遍历 T，对每个结点调用函数 visit( )一次且仅一次。一 旦 visit( )失败，则操作失败 LevelOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：层序遍历 T，对每个结点调用函数 visit( )一次且仅一次。一 旦 visit( )失败，则操作失败 }ADT BinaryTree 6.2.2 二叉树的性质 1、性质 1：第 i 层至多有 2 i-1 个结点（由每个结点最多只有 2 个孩子推出）