软件基础串讲

1、计算机软件基础,重点知识串讲,树与二叉树,一、树与二叉树概念 1树 树（tree）是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。左图表示了一棵一般的树。由图可以看出，在用图形表示树这种数据结构时，很像自然界中的树，只不过是一棵倒长的树，因此，这种数据结构就用“树”来命名,一般的树,在现实世界中，能用树这种数据结构表示的例子有很多。例如，图中的树表示了学校行政关系结构；由于树具有明显的层次关系，因此，树与二叉树都可以用树这种数据结构来描述。在所有的层次关系中，人们最熟悉的是血缘关系，按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系，因此，在描述树

2、结构时，也经常使用血缘关系中的一些术语,学校行政层次结构树,树：是一个或多个结点的有穷集合T，且满足以下条件： 1、有且仅有一个指定的称作树根的结点； 2、除根以外的其余结点被分成m个不相交的集合，这些集合的每一个又都是树，并且称为根的子树,2树的一些术语 结点的度：结点N的子树数称为结点的度。 树的度：树T中各结点的度的最大值称的树T的度。 叶子：树中度为0的结点称为叶子（终端结点）。 分枝结点：树中度不为0的结点称为分枝结点（非终端结点）。 双亲和孩子：若树中结点P的一棵子树的根是结点C，则我们称P是C的双亲或父母，反之称C是P的孩子。 结点的层数：树的层数为1，其余任一结点的层数等于它的

3、双亲的层数加1. 树的深度：树中各结点的层数的最大值称为T的深度（高度,3二叉树 1）二叉树概念 二叉树（bintree）是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构可以相互转换，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。 二叉树是n（n0）个结点的有限集合，它或者是空集（n=0），或者由一个根结点及两棵互不相交的、分别称这个根的左子树和右子树的二叉树组成。 二叉树不是树的特殊情形，与度数为2的有序树不同,二叉树具有以下两个特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 由以上特点可以看出，

4、在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树，也没有右子树时，该结点即是叶子结点。图是一棵深度为4的二叉树。 五种形态：空，根，左，右，左右,2）二叉树的基本性质 性质1：在二叉树的第k层上，最多有2k1个结点。 根据二叉树的特点，这个性质是显然的。 性质2：深度为k的二叉树最多有2k1个结点。 深度为k的二叉树是指二叉树共有k层。根据性质1，只要将第1层到第k层

5、上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即 性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，即 n0=n2+1 性质4：具有n个结点的完全二叉树的深度为 int（log2n）+1,满二叉树： 满二叉树是一棵深度为k，结点数为2K-1 的二叉树。 完全二叉树： 完全二叉树是满二叉树在最下层自右向左去除部分结点,3）二叉树的存贮表示： 顺序存贮： 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树） 链表表示：lchild，data，rchlid,4）遍历： 根据访问结点的次序不同可得三种遍

6、历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。 前序：根左右 中序：左根右 后序：左右根,5）树的二叉树表示 转换方法： 兄弟相连，保留长子的连线,查找,一、概念 查找：就是确定一个已给的数据是否出现在某个数据表中。 域（字段）：组成记录的每个数据项。 关键字：通常记录中总存在某个或某组数据项，它们的值能唯一标识一个记录，这个（组）数据项称为关键字。 平均查找长度ASL：衡量查找算法效率优劣的标准，是在查找过程中对关键字需要执行的平均比较次数,二、查找方法 线性表查找的方法： 顺序查找：逐个查找，ASL=（n+1）/2； 二分查找：取中点int（n/2）比

7、较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（每层结点数*层数）/N,二叉排序树（BST），（二叉查找树）。定义是： 二叉排序树是空树或者满足如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又是一棵二叉排序树。 二叉排序树的插入、建立、删除的算法平均时间性能是： O（nlog2n）。 二叉排序树的删除操作可分三种情况进行处理： *P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。 *P只有一个孩子*child，此时只需将*child和*p的双

8、亲直接连接就可删去*p. *p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点,散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。 哈希查找： 哈希函数：能把关键字映射成记录存贮地址的函数。 哈希表：假定数组HT0m-1为存贮记录的地址空间，哈希函数H以每个记录的关键字值K作为输入，产生一个落在0m-1内的整数H（K），并以它作为K所标识的记录在表HT中的地址或索引号，这样产生的记录表H（K）叫做哈希表,构造哈希函数的方法： 平方取中法：hash=int（x2）%100） 除余法：表长为m，hash=x%m 相乘取整法：hash=int（m*（x*A-int

9、（x*A）；A=0.618 随机数法：hash=random（x,处理冲突的方法： 开放定址法： 一般形式为hi=（h（key）+di）%m1im-1，开放定址法要求散列表的装填因子1. 拉链法： 是将所有关键字为同义词的结点链接在同一个单链表中。 拉链法的优点： 拉链法处理冲突简单，且无堆积现象； 链表上的结点空间是动态申请的适于无法确定表长的情况； 拉链法中可以大于1，结点较大时其指针域可忽略，因此节省空间； 拉链法构造的散列表删除结点易实现。 拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间,排序,排序是使文件中的记录按关键字递增（或递减）次序排

10、列起来。 基本操作：比较关键字大小；改变指向记录的指针或移动记录。 存储结构：顺序结构、链表结构、索引结构。 排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序,内部排序方法可分为：插入排序、选择排序、交换排序。 评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程度也是要考虑的一个因素。 插入排序： 直接插入排序： 逐个向前插入到合适位置。 直接插入排序的时间复杂度为O（n2）， 比较次数为（n+2）（n-1）/2； 移动次数为（n+4）（n-1）/2,交换排序： 冒泡排序：自下向上确定最轻的一个，后自上向下确定最重的一个。 冒泡排序时间复杂度为O（n2）， 比较次数为n（n-1）/2； 移动次数