二叉树的遍历
先序遍历：D L R ABDC 中序遍历：L D R BDAC 后序遍历：L R D DBCA
A
D
L
R
A D LR
D LR
B T1 D
T2
B
C
C
D LR
T3
D
以先序遍历D L R 为例演示遍历过程
软件工程基本概念
软件的定义
软件(software)是计算机系统中与硬件(hardware)相互依存的另一 部分。软件包括三个部分：程序(program)、相关数据(data)、说明文档 (document)。
队 尾
队列的主要运算
设置一个空队列；
插入一个新的队尾（rear）元素，称为进队；
删除队头（front）元素，称为出队；
读取队头元素；
栈和队列
队列的主要运算
队空时，令rear=front=0; 元素个数＝rear-front
当有新元素入队时，尾指针加1，当有元素出队时，头 指针加1。故在非空队列中，头指针始终指向队头元素 前一个位置，而尾指针始终指向队尾元素的位置
D、具有n个结点的完全二叉树的深度为[log2n]+1，其中 [log2n]表示log2n 的整数部分。第三层 (i=3)，有23-1=4个节
1
点
深度h=4，共有24-1=15个节
2
3
点
4 89
5
10
11
6
12
13
n0=8,n2=7,n0=n2+1 7 15个节点，深度 14 15=[log215]+1=4
‫ ٭‬基本特性
▪ 可行性：根据实际问题设计的算法，执行得到满意结果 ▪ 确定性：每一步骤必须有明确定义，不允许有多义性。 ▪ 有穷性：算法必须能在有限的时间内做完。 ▪ 输入和输出：拥有足够的情报，方可执行。
算法的基本要素
‫ ٭‬1.对数据对象的运算和操作
▪ 算术运算：＋、－、×、÷等 ▪ 逻辑运算：>、<、＝、>=、<=、!=等 ▪ 关系运算：and、or、not等 ▪ 数据传输：w、r等
1
计算机软件基础知识
软件基础
算法
❖算法的基本概念
‫ ٭‬算法：是一组有穷指令集，是解题方案的准确而完 整的描述。通俗地说，算法就是计算机解题的过程。 算法不等于程序，也不等于计算方法，程序的编制 不可能优于算法的设计。
‫ ٭‬算法的基本特征：是一组严谨地定义运算顺序的规则，每
一个规则都是有效的，是明确的，此顺序将在有限的次数下终 止。算法不等于程序，程序不可能优于算法。
an
约定top始终指向新数据元素将存放的位置。 ….
栈底（bottom):不允许插入和删除的一端。 a2
栈底
a1
栈和队列
队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。
此种结构称为先进先出（FIFO）表。
a1 , a2 , a3 , a4 , ………… an-1 , an
队 头
‫ ٭‬对各种数据结构进行的运算
主要目的是为了提高数据的效率。所谓提高数据处理的效率，
主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据 处理过程中所占用的计算机存储空间。
数据结构类型
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据
树形结构 B．非线性结构
结 构
图形结构
的 三
2、数据的存储结构 A 顺序存储
栈和队列
栈和队列是两种运算时要受到某些特殊限制的线性 表，故也称为限定性的数据结构。
栈：限定只能在表的一端进行插入和删除的特殊的线性表,此
种结构称为后进先出。
进栈 出栈
设栈s=（a1，a2，…,ai，…，an）
其中a1是栈底元素， an是栈顶元素。
栈顶（top)：允许插入和删除的一端； 栈顶
存储地址 存储内容
Lo Lo+m
元素1 元素2
……..
三个弱点
‫ ٭‬插入或删除操作时，需 移动大量元数。
‫ ٭‬长度变化较大时，需按 最大空间分配。
‫ ٭‬表的容量难以扩充
Lo+(i-1)*m
元素i ……..
Lo+（n-1)*m 元素n
Loc(a)=Lo+（i-1)*m
每个元 素所占 用的存 储单元 个数
的空间、③算法执行过程中所需要的额外空间
数据结构基本概念
数据结构是一门研究数据组织、存储和运 算的一般方法的学科。
整数(能1,输2)入、到实计数算(1机.中1,1.2) 并能字被符计串算(B机ei程ji序ng处)、理的 符 图号形的、集声合音。
数据结构基本概念
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
数据结构基本概念
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
对数据结构中的节点进行操作处理 (插入、删除、修改、查找、排序)
数据结构研究的主要内容
❖ 数据结构主要研究以下三个方面的问题：
‫ ٭‬数据的逻辑结构：数据集合中各元素的信息，及元 素之间所固有的逻辑关系（前后件关系）
‫ ٭‬数据的存储结构：各数据元素在计算机中的存储关 系
算法效率度量——算法的复杂度
❖算法的复杂度：时间复杂度、空间复杂度
‫ ٭‬算法的时间复杂度
▪ 算法时间复杂度是指执行算法所需要的计算工作量。 ▪ 工作量用算法所执行的基本运算次数来度量，而算法所执
行的基本运算次数是问题规模的函数，即 算法的工作量=f(n)
‫ ٭‬算法空间复杂度
▪ 算法空间复杂度是指执行这个算法所需要的内存空间。 ▪ 存储空间包括：①算法程序所占的空间、 ②输入数据所占
个 方
B 链式存储
面
3、数据的运算：检索、排序、插入、删除、修改等。
线性结构和非线性结构
线性结构条件
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 （3）首节点无前件，尾节点无后件。
非线性结构：不满足线性结构条件的数据结构
注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；
空二叉树
仅有 根结点
右子树 为空
左子树 为空
二叉树的五种基本形态
左右子树 均非空
满二叉树
Байду номын сангаас特点：所有分支结点都存在左右子树，且所有叶子 结点都在同一层上。
1
2
3
4
5
6
7
8
9 10
11 12
13 14 15
完全二叉树
特点：除最后一层外，每一层都取最大结点数，最 后一层结点都集中在该层最左边的若干位置。
1
4
D={ 1 , 2 , 3 , 4}
R={(1,2) , (1,3) , (1,4) , (2,3)
2
3
(3,4) , (2,4) }
无向图
1
D={ 1 , 2 , 3 }
R={ (1,2) , (2,3) , (3,2) , (1,3) }
2
3 有向图
顺序存储与链式存储
顺序存储
‫ ٭‬常用于线性数据结构， 将逻辑上相邻的数据元 素存储在物理上相邻的 存储单元里。
E
F
G
D
HI
J
现实K 世界中L，能用树的结T构2 表示M：学校的T行3 政关 系、书的层次结构、人类的家族血缘关系等。
树与二叉树
树的基本概念：
结点（Node）：树中的元素 A
结点的度（Degree）：结点拥有的子树数。
结点的层次：从根结点开始算起，根为第一层。
叶子（Leaf）：度B为零的结点，C也称端结点。D 孩子（CTh1ild）：结点子树的根称为该结点的孩子结点。
1
2
3
4
5
6
7
8 9 10 11 12
完全二叉树
1
2
4
5
3
6
7
8 9 10 11
12
非完全二叉树
二叉树的基本性质
A、二叉树的第i层上至多有2i-1（i 1）个结点。
B、深度为h的二叉树中至多含有2h-1个结点。
C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有 n2个度为2的结点，则：n0=n2+1
兄双弟亲（（SPiabrleiEnngt））：：孩同子一F结双点亲的的上孩G层子结。点，H称为其I的双亲J。
深森度林（（KDFoerpetsht)）：L：树M中棵结互点不的相最交T大2的层树次的数集M。合。
T3
树与二叉树
二叉树（Binary Tree）的定义
二因为叉树的一每种个特结殊点的的树度型不结同构，，存特储点困是难树，中使每对个树结的点处只理有算两法棵 子很树复杂，且。子所树以有引左出右二之叉分树的，理次论序不。能颠倒。
计算机管理图书问题 图书馆里有各种卡片：有按书名编排的、有按作者
编排的、有按分类编排。 如何将查询图书的这些信息存入计算机中既要考虑
查询时间短，又要考虑节省空间
数据结构基本概念
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
最简单的办法之一是建立一张表，每一本书的信息 在表中占一行，如
数据结构基本概念
软件的特点
软件是一种逻辑实体，不是物理实体，具有抽象性。 软件没有明显的制造过程。 软件在使用过程中，没有磨损、老化问题 软件依赖与硬件和环境，导致了移植问题 软件是复杂的，而且以后会更复杂 软件的成本相当昂贵 软件工作牵涉到很多社会因素
软件工程基本概念
软件危机
早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低， 维护困难，这些问题称为“软件危机”，软件工程概念的出现源自于软件 危机。