《软件基础串讲》PPT课件.ppt

计算机软件基础 重点知识串讲 第2页 树与二叉树 一 树与二叉树概念1 树树 tree 是一种简单的非线性结构 在树这种数据结构中 所有数据元素之间的关系具有明显的层次特性 左图表示了一棵一般的树 由图可以看出 在用图形表示树这种数据结构时 很像自然界中的树 只不过是一棵倒长的树 因此 这种数据结构就用 树 来命名 一般的树 第3页 在现实世界中 能用树这种数据结构表示的例子有很多 例如 图中的树表示了学校行政关系结构 由于树具有明显的层次关系 因此 树与二叉树都可以用树这种数据结构来描述 在所有的层次关系中 人们最熟悉的是血缘关系 按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系 因此 在描述树结构时 也经常使用血缘关系中的一些术语 学校行政层次结构树 第4页 树 是一个或多个结点的有穷集合T 且满足以下条件 1 有且仅有一个指定的称作树根的结点 2 除根以外的其余结点被分成m个不相交的集合 这些集合的每一个又都是树 并且称为根的子树 第5页 2 树的一些术语结点的度 结点N的子树数称为结点的度 树的度 树T中各结点的度的最大值称的树T的度 叶子 树中度为0的结点称为叶子 终端结点 分枝结点 树中度不为0的结点称为分枝结点 非终端结点 双亲和孩子 若树中结点P的一棵子树的根是结点C 则我们称P是C的双亲或父母 反之称C是P的孩子 结点的层数 树的层数为1 其余任一结点的层数等于它的双亲的层数加1 树的深度 树中各结点的层数的最大值称为T的深度 高度 第6页 3 二叉树1 二叉树概念二叉树 bintree 是一种很有用的非线性结构 二叉树不同于前面介绍的树结构 但它与树结构可以相互转换 二叉树的存储结构及其算法都较为简单 因此二叉树显得特别重要 二叉树是n n 0 个结点的有限集合 它或者是空集 n 0 或者由一个根结点及两棵互不相交的 分别称这个根的左子树和右子树的二叉树组成 二叉树不是树的特殊情形 与度数为2的有序树不同 第7页 二叉树具有以下两个特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 由以上特点可以看出 在二叉树中 每一个结点的度最大为2 即所有子树 左子树或右子树 也均为二叉树 而树结构中的每一个结点的度可以是任意的 另外 二叉树中的每一个结点的子树被明显地分为左子树与右子树 在二叉树中 一个结点可以只有左子树而没有右子树 也可以只有右子树而没有左子树 当一个结点既没有左子树 也没有右子树时 该结点即是叶子结点 图是一棵深度为4的二叉树 五种形态 空 根 左 右 左右 第8页 2 二叉树的基本性质性质1 在二叉树的第k层上 最多有2k 1个结点 根据二叉树的特点 这个性质是显然的 性质2 深度为k的二叉树最多有2k 1个结点 深度为k的二叉树是指二叉树共有k层 根据性质1 只要将第1层到第k层上的最大的结点数相加 就可以得到整个二叉树中结点数的最大值 即性质3 在任意一棵二叉树中 度为0的结点 即叶子结点 总是比度为2的结点多一个 即n0 n2 1性质4 具有n个结点的完全二叉树的深度为int log2n 1 第9页 满二叉树 满二叉树是一棵深度为k 结点数为2K 1的二叉树 完全二叉树 完全二叉树是满二叉树在最下层自右向左去除部分结点 第10页 3 二叉树的存贮表示 顺序存贮 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中 存储前先将其画成完全二叉树 链表表示 lchild data rchlid 第11页 4 遍历 根据访问结点的次序不同可得三种遍历 先序遍历 前序遍历或先根遍历 中序遍历 或中根遍历 后序遍历 或后根遍历 前序 根 左 右中序 左 根 右后序 左 右 根 第12页 5 树的二叉树表示转换方法 兄弟相连 保留长子的连线 第13页 查找 一 概念查找 就是确定一个已给的数据是否出现在某个数据表中 域 字段 组成记录的每个数据项 关键字 通常记录中总存在某个或某组数据项 它们的值能唯一标识一个记录 这个 组 数据项称为关键字 平均查找长度ASL 衡量查找算法效率优劣的标准 是在查找过程中对关键字需要执行的平均比较次数 第14页 二 查找方法线性表查找的方法 顺序查找 逐个查找 ASL n 1 2 二分查找 取中点int n 2 比较 若小就比左区间 大就比右区间 用二叉判定树表示 ASL 每层结点数 层数 N 第15页 二叉排序树 BST 二叉查找树 定义是 二叉排序树是空树或者满足如下性质的二叉树 若它的左子树非空 则左子树上所有结点的值均小于根结点的值 若它的右子树非空 则右子树上所有结点的值均大于根结点的值 左 右子树本身又是一棵二叉排序树 二叉排序树的插入 建立 删除的算法平均时间性能是 O nlog2n 二叉排序树的删除操作可分三种情况进行处理 P是叶子 则直接删除 P 即将 P的双亲 parent中指向 P的指针域置空即可 P只有一个孩子 child 此时只需将 child和 p的双亲直接连接就可删去 p p有两个孩子 则先将 p结点的中序后继结点的数据到 p 删除中序后继结点 第16页 散列技术 将结点按其关键字的散列地址存储到散列表的过程称为散列 哈希查找 哈希函数 能把关键字映射成记录存贮地址的函数 哈希表 假定数组HT 0 m 1 为存贮记录的地址空间 哈希函数H以每个记录的关键字值K作为输入 产生一个落在 0 m 1 内的整数H K 并以它作为K所标识的记录在表HT中的地址或索引号 这样产生的记录表H K 叫做哈希表 第17页 构造哈希函数的方法 平方取中法 hash int x 2 100 除余法 表长为m hash x m相乘取整法 hash int m x A int x A A 0 618随机数法 hash random x 第18页 处理冲突的方法 开放定址法 一般形式为hi h key di m1 i m 1 开放定址法要求散列表的装填因子 1 拉链法 是将所有关键字为同义词的结点链接在同一个单链表中 拉链法的优点 拉链法处理冲突简单 且无堆积现象 链表上的结点空间是动态申请的适于无法确定表长的情况 拉链法中 可以大于1 结点较大时其指针域可忽略 因此节省空间 拉链法构造的散列表删除结点易实现 拉链法也有缺点 当结点规模较小时 用拉链法中的指针域也要占用额外空间 还是开放定址法省空间 第19页 排序 排序是使文件中的记录按关键字递增 或递减 次序排列起来 基本操作 比较关键字大小 改变指向记录的指针或移动记录 存储结构 顺序结构 链表结构 索引结构 排序过程中不涉及数据的内 外存交换则称之为 内部排序 内排序 反之 若存在数据的内外存交换 则称之为外排序 第20页 内部排序方法可分为 插入排序 选择排序 交换排序 评价排序算法好坏的标准主要有两条 执行时间和所需的辅助空间 另外算法的复杂程度也是要考虑的一个因素 插入排序 直接插入排序 逐个向前插入到合适位置 直接插入排序的时间复杂度为O n 2 比较次数为 n 2 n 1 2 移动次数为 n 4 n 1 2 第21页 交换排序 冒泡排序 自下向上确定最轻的一个 后自上向下确定最重的一个 冒泡排序时间复杂度为O n 2 比较次数为n n 1 2