第六章树和二叉树 第一节树的类型定义 为“根 °T1、12和T3都是一棵树,称为A的子树。 称根和子树根之间的连线为“分支 结点分支的个数定义为“结点的度”,如结点B的度为2,D的度为3。 树中所有结点度的最大值定义为树的度”。 称度为零的结点为“叶子” 或“终端结点 所有度不为零的结点 被称作”分支结点 基本定义 森林为m(m≥0)棵互不相交的树的集合。 树的深度定义为树中叶子结点所在最大层次数。 称根结点为子树根的”双亲”。 称子树根为根结点的孩子“ 根的所有子树根互为“兄弟”。 °有序树、无序树如果树中 每棵子树从左向右的排列拥有 定的顺序,不得互换,则称 为有序树,否则称为无序树。 树的抽象数据类型: .ADT Tree i 数据对象:D是具有相同特性的数据元素的集合 数据关系 若D为空集,则称为空树 若D中仅含一个数据元素,则关系R为空集; 否则R={H} (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)当n>1时,其余数据元素可分为m(m>0)个互不相交的非空有限集T1,T2,,Tm 其中每一个子集本身又是一棵符合本定义的树,称为根root的子树,每一棵子树的根xi都 是根root的后继,即<rot,r>H,=1,2,,m。 基本操作: {结构初始化} 操作结果:构造空树T CreateTree(&T, definition) 初始条件: definition给出树T的定义。 操作结果:按 definition构造树T
第六章 树和二叉树 第一节 树的类型定义 •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) 当 n>1 时，其余数据元素可分为 m(m>0) 个互不相交的(非空)有限集 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。 {引用型操作 初始条件:树T存在 操作结果:若T为空树,则返回TRUE,否则返回 FALSE。 IreeDepth(t); 初始条件:树T存在。 操作结果:返回T的深度。 Root(D); 初始条件:树T存在 操作结果:返回T的根 cur 初始条件:树T存在,cure是T中某个结点。 操作结果:返回cure的值。 初始条件:树T存在,cure是T中某个结点。 操作结果:若cure是T的非根结点,则返回它的双亲,否则返回"空"。 LeftChild (t, cur e) 初始条件:树T存在,cure是T中某个结点 操作结果:若cure是T的非叶子结点,则返回它的最左孩子,否则返回"空"。 Rightsibling(l, cur e); 初始条件:树T存在,cure是T中某个结点。 操作结果:若cure有右兄弟,则返回它的右兄弟,否则返回"空 TraverseTree(T, visit(); 初始条件:树T存在,vsi是对结点操作的应用函数 操作结果:按某种次序对T的每个结点调用函数vsi0一次且至多一次。一且vsit0失 败,则操作失败 {加工型操作} Assign(T, cur e, value); 初始条件:树T存在,cure是T中某个结点。 操作结果:结点cure赋值为 value 初始条件:树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≤长p所指结点的度+1,非空树c与 T不相交 操作结果:插入c为T中p所指结点的第i棵子树。 Delete Child (&T,&p, i); 初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。 操作结果:删除T中p所指结点的第i棵子树 3 ADT Tree 树和线性结构对照: 第二节二叉树类型 ·定义:二叉树是另一种树形结构。它与树形结构的区别是: (1)每个结点最多有两棵子树; (2)子树有左右之分 叉树也可以用递归的形式定义。即:二叉树是n(n≥0)个结点的有限集合。 当n=0时,称为空二叉树;当n>时,有且仅有一个结点为二叉树的根,其余结点被分成两个 互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。 621二叉树的类型定义 ADT Binary Tree i 数据对象:D是具有相同特性的数据元素的集合 数据关系: 若D为空集,称 Binary Tree为空二叉树; 否则关系R={H} (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)D中其余元素必可分为两个互不相交的子集L和R,每一个子集都是一棵符合本 定义的二叉树,并分别为root的左子树和右子树。如果左子树L不空,则必存在一个根结点, 它是root的"左后继"<root,>∈H),如果右子树R不空,则必存在一个根结点为root的 右后继"(<root,>∈H) °基本操作P 结构初始化} Init BiTree(&I 操作结果:构造空二叉树T。 Create BiTree(&T, definition); 初始条件: definition给出二叉树T的定义 操作结果:按 definition构造二叉树T。 销毁结构} Destroy BiTree(&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 时，有且仅有一个结点为二叉树的根，其余结点被分成两个 互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 6.2.1 二叉树的类型定义 ADT BinaryTree { 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，称 BinaryTree 为空二叉树； 否则 关系 R={H}： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本 定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点 ， 它是 root 的"左后继"(<root, >∈H)，如果右子树 R 不空，则必存在一个根结点 为 root 的 "右后继"(<root, >∈H)。 •基本操作 P： {结构初始化} InitBiTree(&T); 操作结果：构造空二叉树 T。 CreateBiTree(&T, definition); 初始条件：definition 给出二叉树 T 的定义。 操作结果：按 definition 构造二叉树 T。 {销毁结构} DestroyBiTree(&T); 初始条件：二叉树 T 存在
操作结果:销毁二叉树T °{引用型操作} BiTreeempty (t 初始条件:二叉树T存在。 操作结果:若T为空二叉树,则返回TRUE,否则返回 FALSE。 reeDepth(D); 初始条件:二叉树T存在。 操作结果:返回T的深度 Root(D); 初始条件:二叉树T存在 操作结果:返回T的根 Value(T, e); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的值。 ° Parent(T,e); 初始条件:二叉树T存在,e是T中某个结点 操作结果:若e是T的非根结点,则返回它的双亲,否则返回"空"。 LeftChild(t, e); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的左孩子。若e无左孩子,则返回”空"。 Right Child(t, e) 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的右孩子。若e无右孩子,则返回空”。 LeftSibling(t, e); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的左兄弟。若e是其双亲的左孩子或无左兄弟,则返回"空 · Rightsibling(T,e); 初始条件:二叉树T存在,e是T的结点。 操作结果:返回e的右兄弟。若e是其双亲的右孩子或无右兄弟,则返回"空 PreOrderTraverse(T, visitO); 初始条件:二叉树T存在,vsi是对结点操作的应用函数 操作结果:先序遍历T,对每个结点调用函数visi-次且仅一次。一且vsit0失败,则 操作失败 InOrderTraverse(T, sito); 初始条件:二叉树T存在,vsit是对结点操作的应用函数 操作结果:中序遍历T,对每个结点调用函数Ⅴi一次且仅一次。一且vsit(失败, 则操作失败
操作结果：销毁二叉树 T。 •{引用型操作} BiTreeEmpty(T); 初始条件：二叉树 T 存在。 操作结果：若 T 为空二叉树，则返回 TRUE，否则返回 FALSE。 BiTreeDepth(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的深度。 Root(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的根。 Value(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的值。 •Parent(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：若 e 是 T 的非根结点，则返回它的双亲，否则返回"空"。 LeftChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左孩子。若 e 无左孩子，则返回"空"。 RightChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的右孩子。若 e 无右孩子，则返回"空"。 LeftSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟，则返回"空"。 •RightSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 的结点。 操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回"空"。 PreOrderTraverse(T, visit()); 初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。 操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则 操作失败。 InOrderTraverse(T, vsit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败， 则操作失败
PostOrderTraverse(l, visitO); 初始条件:二叉树T存在,vsit是对结点操作的应用函数。 操作结果:后序遍历T对每个结点调用函数vsi一次且仅一次。一且 visit0失败,则 操作失败。 LevelOrderTraverse(T, visitO); 初始条件:二叉树T存在,vit是对结点操作的应用函数 操作结果:层序遍历T对每个结点调用函数vsi一次且仅一次。一且vsi0失败, 则操作失败。 {加工型操作} ClearBiTree(&T 初始条件:二叉树T存在 操作结果:将二叉树T清为空树 Assign(&t, &e, value); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:结点e赋值为 value. Insert Child(&T, p, LR, c) 人,初始条件:二又树T存在,p指向T中某个结点,IR为0或1,非空二又树与 操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指 结点原有左或右子树成为c的右子树 Delete Child(&T, p, LR) 初始条件:二叉树T存在,p指向T中某个结点,LR为0或1 操作结果:根据LR为0或1,删除T中p所指结点的左或右子树。 3 ADT Binary Tree 622二叉树的几个特性 在二叉树的第i层上至多有21个结点(i≥1) 二、深度为k的二叉树中至多含有2k-1个结点,(k≥1) 三、对任何一棵二叉树T,如果其终端结点数为n,度为2的结点数为m,则 若二叉树中所有的分支结点的度数都为2,且叶子结点都在同一层次上,则称这类二叉树为满 二叉树 假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一、 对应,则称这类二叉树为完全二叉树。 第三节二叉树的存储表示 63.1顺序存储结构 二叉树的顺序存储结构的定义如下
PostOrderTraverse(T, visit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则 操作失败。 • LevelOrderTraverse(T, visit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败， 则操作失败。 {加工型操作} ClearBiTree(&T); 初始条件：二叉树 T 存在。 操作结果：将二叉树 T 清为空树。 Assign(&T, &e, value); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：结点 e 赋值为 value。 •InsertChild(&T, p, LR, c); 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。 • 操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指 结点原有左或右子树成为 c 的右子树。 DeleteChild(&T, p, LR); 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 } ADT BinaryTree 6.2.2 二叉树的几个特性 •一、在二叉树的第 i 层上至多有 2 i-1 个结点(i≥1)。 •二、深度为 k 的二叉树中至多含有 2 k -1 个结点，(k≥1)。 •三、对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 =n2+ 1 •若二叉树中所有的分支结点的度数都为 2，且叶子结点都在同一层次上，则称这类二叉树为满 二叉树。 •假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为 1 至 n 的结点一、 一对应，则称这类二叉树为完全二叉树。 第三节 二叉树的存储表示 •6.3.1 顺序存储结构 •二叉树的顺序存储结构的定义如下：