access2007数据库应用技术教学课件作者杨江文9.ppt

图9-8 【例9-5】的排序步骤 返回 图9-7 【例9-4】的排序步骤 返回 图9-6 【例9-3】的排序步骤 返回 图9-5 二叉树在内存空间中的存放方式 返回 图9-4 二叉树的存储结构 返回 图9-3 完全二叉树 返回 图9-2 满二叉树 返回 图9-1 树结构 返回 * 9.5　线性链表 9.5.3　循环链表及其基本操作 在线性链表中，虽然对数据元素的插入和删除操作比较简单，但由于 它对第一个结点和空表需要单独处理，使得空表与非空表的处理不一 致。 循环链表，即是采用另一种链接方式，它的特点如下： （1）在循环链表中增加一个表头结点，其数据域为任意或根据需要 来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针 指向表头结点。 上一页 下一页 返回 9.5　线性链表 （2）循环链表中最后一个结点的指针域不是空的，而是指向表头结 点。在循环链表中，所有结点的指针构成一个环状链。 在循环链表中，只要指出表中任何一个结点的位置，均可以从它开始 扫描到所有的结点，而线性链表做不到，线性链表是一种单向的链 表，只能按照指针的方向进行扫描。 上一页 返回 9.6　树与二叉树 9.6.1　树的基本概念图9-1 树结构 树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的 层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前 件，下端点为后件，如图9-1所示。 在树结构中，每一个结点只有一个前件，称为父结点。如A即为结点 B、C、D的父结点。 没有父结点的结点只有一个，称为根结点。在图9-1中，结点A即为 根结点。 每一个结点可以有多个后件，它们均称为该结点的子结点。如结点G、 H、I是结点D的子结点。 下一页 返回 9.6　树与二叉树 没有后件的结点，称为叶子结点。在图9-1中，叶子结点有J、M、N、 L、C、G、H、I。 在树结构中，一个结点所拥有的后件结点个数称为该结点的度。例 如，结点D的度为3，结点E的度为1等，按此原则，所有叶子结点的度 均为0。 在树中，所有结点中最大的度称为该树的度。在图9-1所示的树中， 所有结点中最大的度是3，所以该树的度为3。 树分层，根结点为第一层，往下依此类推。同一层结点的所有子结点 均在下一层。如图9-1中，A结点在第1层，B、C、D结点在第2层，E、 F、G、H、I在第3层，J、K、L在第4层，M、N在第5层。 上一页 下一页 返回 9.6　树与二叉树 树的最大层次称为树的深度。图9-1中树的深度为5。 在树中，某结点的一个子结点为根构成的树称作该结点的子树，叶子 结点没有子树。 在计算机中，可以用树来表示算术表达式。原则如下： （1）表达式中每一个运算符在树中对应一个结点，称为运算符结点。 （2）运算符的每一个运算对象在树中为该运算符结点的子树（在树 中的顺序为从左到右）。 （3）运算对象中的单变量均为叶子结点。 树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对 应结点的信息，而每个结点中的链域（即指针域）个数将随着树中该 结点的度而定义。 上一页 下一页 返回 9.6　树与二叉树 如果在树中，每一个结点的子结点的个数不相同，因此在多重链表中 各结点的链域个数也不相同，会导致算法太复杂。因此，在树中，常 采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的 链域的个数。 9.6.2　二叉树及其基本性质 1. 二叉树的定义 二叉树的特点： （1）非空二叉树只有一个根结点。 （2）每一个结点最多只有两个子结点，且结点分左右。则一个结点 最多可以有两棵子树，分别称为左子树和右子树。 上一页 下一页 返回 9.6　树与二叉树 在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树 中，任何的子树也均为二叉树。 在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树 中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有 左子树，也没有右子树，则该结点为叶子结点。 2. 二叉树的性质 性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。 性质2：深度为m的二叉树最多有2m-1（m≥1）个结点。 性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为 2的结点多一个。 上一页 下一页 返回 9.6　树与二叉树 性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中 [log2n]表示log2n的整数部分。 3. 满二叉树与完全二叉树图9-2 满二叉树 （1）满二叉树。满二叉树除最后一层外，每一层上的所有结点都有 两个子结点，即在满二叉树中，每一层上的结点数都达到最大值，即 在满二叉树上的第k层上有2k-1个结点。如图9-2所示即为一棵满二叉 树。 （2）完全二叉树。特点：除最后一层外，每