数据结构第六章树和二叉树.ppt

第六章 树和二叉树 第一节 树的类型定义 A 为“根” T1、T2和T3都是一棵树，称为A的子树。 称根和子树根之间的连线为“分支” 结点分支的个数定义为“结点的度”，如结点B的度为2，D 的度为3。 树中所有结点度的最大值定义为“树的度”。 称度为零的结点为“叶子” 或“终端结点” 所有度不为零的结点 被称作分支结点 基本定义 森林为 m(m≥0) 棵互不相交的树的集合。 树的深度定义为树中叶子结点所在最大层次数。 称根结点为子树根的双亲。 称子树根为根结点的孩子“ 根的所有子树根互为“兄弟”。 有序树、无序树 如果树中 每棵子树从左向右的排列拥有 一定的顺序，不得互换，则称 为有序树，否则称为无序树。 树的抽象数据类型： ADT Tree {　数据对象：D是具有相同特性的数据元素的集合。　数据关系：　　若 D 为空集，则称为空树；　　若 D 中仅含一个数据元素，则关系R为空集；　　否则 R={H}，　　 (1) 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；　　 (2) 当n1时，其余数据元素可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 root,xi H,i=1,2,…,m。 基本操作：　{结构初始化}　　InitTree(T);　　　操作结果：构造空树 T。　　CreateTree(T,definition);　　　初始条件：definition 给出树T的定义。　　　操作结果：按 definition 构造树 T。　{销毁结构}　　DestroyTree(T);　　　初始条件：树 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 的值。 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(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时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个