20xx年三级数据库技术等级考试大纲考试要点各章讲义

20xx年三级数据库技术等级考试大纲考试要点各章讲义内容摘要：

，其定义如下：树是 n(n0)个结点的有穷集合，满足： (1)有且仅有一个称为根的结点； (2)其余结点分为 m(m≥ 0)个互不相交的非空集合， T1， T2，…， Tm，这些集合中的每一个都是一棵树，称为根的子树。 在树上，根结点没有直接前趋。 对树上任一结点 X来说， X是它的任一子树的根结点的惟一的直接前趋。 为了讨论方便，我们引入树的若干习惯术语。 树上任一结点所拥有的子树的数目称为该结点的度。 度为 0的结点称为叶子或终端结点，度大于 0的结点称为非终端结点或分支点。 一棵树中所有结点的度的最大值称为该树的度。 若树中结点 A是结点 B的直接前趋，则称 A为 B的双亲或父结点，称 B为 A的孩子 (即 “子女 ”)或子结点。 易知任何结点 A的孩子 B也就是 A的一棵子树的根结点，父结点相同的结点互称为兄弟。 一棵树上的任何结点 (不包括根本身 )称为根的子孙。 反之若 B是 A的子孙，则称 A是 B的祖先。 结点的层数 (或深度 )从根开始算起：根的层数为 1，其余结点的层数为其双亲的层数加 1。 一棵树中所有结点层数的最大值称为该树的高度或深度。 树 (及一切树形结构 )是一种 “分支层次 ”结构。 所谓 “分支 ”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支 ”；所谓 “层次 ”是指树上所有结点可以按它们的层数划分不同的 “层 次 ”。 在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的逻辑关系 (即父结点与子结点之间的邻接关系 )往往用来表示数据元素之间的某种重要的、必须加以表达的关系。 用图示法表示任何树形结构时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简单地用连线代替箭头。 ： ①求根 ROOT(T)，引用型运算，其结果是结点 X在树 T的根结点。 ②求双亲 PARENT(T， X)，引用型运算，其结果是结点 X在树 T上的双亲结点；若 X是树T的根或 X不在 T上，则结果为一特殊标志。 ③求孩子 CHILD(T， X， i)，引用型运算，其结果是树 T上的结点 X的第 i个孩子；若 X不在 T上或 X没有第 i个孩子，则结果为一特殊标志。 ④建树 CREATE(X， T1，…， Tk)， k≥ 1,加工型运算，其作用是建立一棵以 X为根，以T1，…， Tk为第 1，… k棵子树的树。 ⑤剪枝 DELETE(T， X， i)，加工型运算，其作用是删除树 T上结点 X的第 i棵子树；若 T无第 i棵子树，则为空操作。 (1)二叉树的基本概念二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件： ①有且仅有一个称为根的结点： ②其余结点分为两个互不相交的集合 T T2， T1与 T2都是二叉树，并且 T1与 T2有顺序关系 (T1在 T2之前 )，它们分别称为根的左子树和右子树。 二叉树是一类与树不同的树形结构。 它们的区别是：第一，二叉树可以是空集，这种二叉树称为空二叉树；第二，二叉树的任一结点都有两棵子树 (当然，它们中的任何一个可以是空子树 )，并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。 相应地，二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。 另外，二叉树上任一结点的度定义为该结点的孩子数 (即非空子树数 )。 除这个几 个术语之外，树的其它术语也适用于二叉树。 特别值得注意的是，由于二叉树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。 二叉树的基本运算包括：ⅰ初始化 INITLATE(BT)，加工型运算，其作用是设置一棵空二叉树 BT= ROOT(BT)，引用型运算，其结果是二叉树 BT的根结点；若 BT为空二叉树，运算结果为一特殊标志。 ⅲ求双亲 PARENT(BT，X)，引用型运算，其结果是结点 X在二叉树 BT上的双亲；若 X是 BT的根或 X根本不是 BT上的结点，运算结果为一特殊标志。 ⅳ求左孩子 LCHILD(BT， X)和求右孩子 RCHILD(BT，X)，引用型运算，其结果分别为结点 X在二叉树 BT上的左、右孩子；若 X为 BT的叶子或 X不在 BT上，运算结果为一特殊标志。 ⅴ建树 CREAT(X， LBT， RBT)，加工型运算，其作用是建立一棵以结点 X为根，以二叉树 LBT、 RBT分别为 X的左、右子树的二叉树。 ⅵ剪枝 DELLEFT(BT， X)和 DELRIGHT(BT， X)，加工型运算，其作用分别为删除二叉树BT上结点 X的左、右子树；若 X无左或右子树，运算为空操作。 与其它数 据结构相同，在实际应用中根据需要对基本运算适当增减。 (2)二叉树的性质在某些情况下，了解二叉树的下列性质是有帮助的。 性质 1二叉树第 i(i≥ 1)层上至多有 2i1个结点。 性质 2深度为 k(k≥ 1)的二叉树至多有 2k1个结点。 性质 3对任何二叉树，若度数为 2的结点数为 n2，则叶子数 n0=n2+1。 有两种特殊形态的二叉树在讨论问题时很有用，这就是满二叉树和完全二叉树。 深度为 k(k≥ 1)且有2k1个结点的二叉树称为满二叉树。 由性质 2知，满二叉树上各层的结点数已达到了二叉树可以容纳的最大值。 如果在一棵深度为 k(k≥ 1)的满二叉树上删去第 k层上最右边的连续 j(0≤ j2k1)个结点，就得到一棵深度为 k的完全二叉树。 显然，满二叉树也是完全二叉树，但反之不然。 完全二叉树有下述重要性质 (其中［ x］表示不大于 x的最大整数 )：性质 4具有 n个结点的完全二叉树的深度为［ log2n］ +1。 完全二叉树另一个重要性质是对其结点的 “按层编号 ”将得到很好的结果。 所谓 “按层编号 ”是指：将一棵树中的所有 n个结点按从第一层到最大层、每层从左到右的顺序依次标记为 1， 2，…， n。 性质 5如果将一棵有 n个结点的完全二叉树按层编号，则对任一编号为 i(1≤ i≤ n)的结点 X有： (1)若 i=1，则结点 X是根；若 i1，则 X的双亲 PARENT(X)的编号为［ i/2］。 (2)若 2in，则结点 X无左孩子 (且无右孩子 )；否则， X的孩子 LCHILD(X)的编号为 2i。 (3)若 2i+1n，则结点 X无右孩子，否则， X的右孩子 RCHILD(X)的编号为 2i+1 ，顺序存储结构和链式存储结构。 (1)二叉树的链式存储结构二叉树有不同的链式存储结构，其中最常用的是二叉树链表与三叉链表。 二叉树链表的结点形式如下： lchild data rchild 其中， data域称为数据域，用于存储二叉树结点中的数据元素； lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针 (这个指针及指针域有时简称为左指针 )。 类似地， rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针 (简称右指针 )。 二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。 此外，每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。 根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开始。 值得注意的是，二叉链表中每 个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针 NULL。 若二叉树为空，则 root=NULL。 若某结点的某个孩子不存在，则相应的指针为空。 具有 n个结点的二叉树中，一共有 2n个指针域，其中只有 n1个用来指向结点的左右孩子，其余的 n+1个指针域为 NULL。 二叉树的链式存储结构操作方便，表达简明 (二叉树的逻辑关系 ——结点间的父子关系 ——在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针 )，因而成为二叉树最常用的存储结构。 然而在某些情况下，二叉树的顺序存储结构也很有用。 (2)二叉树的顺序存储结构二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。 显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系 (父子关系 )，否则二叉树的基本运算就难以实现。 由二叉树的性质 5可知，若对任一完全二叉树上的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。 因此，对于任何完全二叉树来说，可以采用 “以编号为地址 ”的策略将结点存入作为顺序存储结构的一维数组。 具体地说就是：将编号为 i的结点存入一维数组的第 i个 单元。 在这一存储结构中，由于一结点的存储位置 (即下标 )也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。 ，无需详加讨论。 下面研究二叉树的一种较为复杂的重要运算 ——遍历及其在二叉链表上的实现。 遍历一棵二叉树就是按某种次序系统地 “访问 ”二叉树上的所有结点，使每个结点恰好被 “访问 ”一次。 所谓 “访问 ”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。 遍历运算的关键在于访问结点的 “次序 ”，这种次序应保 证二叉树上的每个结点均被访问一次且仅一次。 由定义可知，一棵二叉树由三部分组成：根、左子树和右子树。 因此对二叉树的遍历也可相应地分解成三项 “子任务 ”： ①访问根根点； ②遍历左子树 (即依次访问左子树上的全部结点 )； ③遍历右子树 (即依次访问右子树上的全部结点 )。 因为左、右子树都是二叉树 (可以是空二叉树 )，对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。 由此可见，上述三项子任务之间的次序决定了遍历的次序。 若以 D、 L、 R分别表示这三项子任务，则人有六种可能的次序： DLR、 LDR、 LRD、 DRL、 RDL和 RLD。 通常限定 “先左后右 ”，即子任务②在子任务③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历 (或前序遍历 )、中根 (或中序 )遍历、后根 (或后序 )遍历。 三种遍历方法的定义如下：先根遍历若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作： ①访问根结点； ②先根遍历左子树 ③先根遍历右子树。 中根遍历若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作： ①中根遍历左子树； ②访问根结点； ③中根遍右子树。 后根遍历若需遍历的二叉树为空，执行空操作，否则，依次执行下列操 作； ①后根遍历左子树 ②后根遍历右子树 ③访问根结点。 显然，上述三种遍历方法的区别在于执行子任务 “访问根结点 ”的 “时机 ”不同； 最先(最后、在中间 )执行此子任务，则为先根 (后根、中根 )遍历。 按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。 为了适应各种应用问题的需要，多种不同的存储结构也相应地建立起来。 下面介绍树的三种常用存储结构 (1)孩子链表表示法孩子链表表示法是树的一种链式存储结构。 与二叉树的二叉链表存储方法类似，孩子链表表示法的基本思想是：树上的一个 结点的内容 (数据元素 )以及指向该结点所有孩子的指针存储在一起以便于运算的实现。 由于树上的结点的度 (孩子数 )没有限制，而且各个结点的度可能相差很大，一种自然的表示方法是为树上的每个结点 X建立一个 “孩子链表 ”，以便存储 X中的数据元素和指向 X的所有孩子的指针。 一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域：数据域和指针域。 其中，数据域用于存储结点 X中的数据元素；指针域用于存储指向该单链表中第一个表结点 (首结点 )的指针。 为了检索方便，所有头结点组织成一个数组，称为表头数组。 对每个结点 X的孩子链表来说，其中的所有表结点也含两个域，孩子域 (即数据域 )和指针域。 第 i个表结点的孩子域存储 X的第 i个孩子在头结点数组中的下标值。 (2)孩子兄弟链表表示法孩子兄弟链表中所有存储结点的形式相同，均含三个域：数据域 ——用于存储树上的结点中的数据元素；孩子域 ——用于存储指向本结点第一个孩子的指针；兄弟域 ——用于存放指向本结点下一个兄弟的指针。 值得注意的是，孩子兄弟链表的结构形式与二叉链表完全相同；但存储结点中指针的含义不同。 二叉链表中存储结点的左、右指针分别指向左、右孩子；而孩子兄弟链表中存储结点的两个指针 分别指向 “长子 ”和 “大弟 ”。 在孩子兄弟链表表示法中，结点形式统一，结点间的联系比较简洁。 同时，在这种存储结构上容易实现树形数据结构的大多数运算。 (3)双亲表示法树上每个结点的孩子可以有任意多个，但双亲只有一个。 因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。 树的这种存储表示方法称为双亲表示法。 在双亲表示法下，每个存储结点由两个域组成：数据域 ——用于存储树上结点中的数据元素； “指针 ”域 ——用于指示本结点之双亲所在的存储结点。 值得注意的是， “指针 ”域的类型定义可以有两种选择。 第 一种是将其定义为高级语言 (如 C语句 )中的指针类型。 通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二叉链表、孩子链表等等。 第二种选择是将 “指针 ”域定义为整型、子界型等型。 严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过 “指针 ”完成的，而且这些指针反映了结点之间的逻辑关系。 为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构 (如单链表、二叉链表等等 )称为 “动态链表 ”，相应的指针称为 “动态指针 ”；将指针域定义为整型、子界型等类型的各种键式存储结构称为 “静态链表 ”，相应的 “指针 ”称为： “静态指针 ”。 动态链表中的结点是。