即为二叉树
(1) 非空二叉树只有一个根结点;
(2) 每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
二叉树基本性质:★★★★
性质1 在二叉树的第k层上,最多有 个结点。
性质2 深度为m的二叉树最多有个 个结点。
性质3 在任意一棵二叉树中,度数为0的结点(即叶子结点)总比度为2的结点多一个。
性质4 具有n个结点的二叉树,其深度至少为 ,其中 表示取 的整数部分
3、满二叉树与完全二叉树
满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。
完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
下图a表示的是满二叉树,下图b表示的是完全二叉树:
4、二叉树的遍历 ★★★★
二叉树的遍历是指不重复地访问二叉树中的
所有结点。二叉树的遍历可以分为以下三种:
(1)前序遍历(DLR):若二叉树为空,则结束返回。否则:首先访问根结点,然后遍历左子树,最后遍历右子树;并且,在遍历左右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。
(2)中序遍历(LDR):若二叉树为空,则结束返回。否则:首先遍历左子树,然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。
(3)后序遍历(LRD):若二叉树为空,则结束返回。否则:首先遍历左子树,然后遍历右子树,最后访问根结点,并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点.
该二叉树前序遍历为:F C A D B E G H P
该二叉树中序遍历为:A C B D F E H G P
该二叉树后序遍历为:A B D C H P G E F
1.7 查找技术
查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。
查找结果:(查找成功:找到;查找不成功:没找到。)
平均查找长度:查找过程中关键字和给定值比较的平均次数。
查找分为: 顺序查找 二分法查找对于长度为n的有序线性表,最坏情况只需比较 次,而顺序查找需要比较n次。
1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
1、交换类排序法(冒泡排序,快速排序)
2、插入类排序法(简单插入排序,希尔排序)
3、选择类排序法(简单选择排序,堆排序)
冒泡排序法,快速排序法,简单插入排序法,简单选择排序法,最坏需要比较的次数为n(n-1)/2
希尔排序,最坏需要比较的次数为
堆排序,最坏需要比较的次数为
2.1 程序设计设计方法和风格
"清晰第一、效率第二"已成为当今主导的程序设计风格。
形成良好的程序设计风格需注意:
1、源程序文档化;
2、数据说明的方法;
3、语句的结构;
4、输入和输出。
注释分序言性注释和功能性注释。 语句结构清晰第一、效率第二。
2.2 结构化程序设计
结构化程序设计方法的四条原则是:
1、自顶向下;
2、逐步求精;
3、模块化;
4、限制使用goto语句。
3.1 软件工程基本概念
1、软件的相关概念
计算机软件是包括
程序、数据及相关文档的完整集合。
软件的特点包括:1)软件是一种逻辑实体,而不是物理实体,具有抽象性;2)软件的生产与硬件不同,它没有明显的制作过程
;3)软件在运行、使用期间不 存在磨损、老化问题;4)软件的开发、运行对计算机系统具有依赖性,受
计算机系统的限制,这导致了软件移植的问题;5)软件复杂性高,成本昂贵;6)软件 开发涉及诸多的社会因素。
2、软件危机与软件工程
软件工程源自软件危机。所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重
问题。
软件工程的主要思想是将工程化原则运用到软件开发过程,它包括3个要素:方法、工具和过程。方法是完成软件工程项目的技术手段;工具是支持软件的开发、管理、
文档生成;过程支持软件开发的各个环节的控制、管