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