文档内容
《信息技术》三色速记手册
一棵高度为k的二叉树，最多具有2k－1个结点。
证明：这棵二叉树中的每一层的结点个数必须最多。
根据性质1，第i层的结点数最多为等于2i-1，
因此结点个数 N 最多为：2k－1
二叉树的性质3
对于一棵非空二叉树，如果叶子结点数为n，度数为2的结点数为n，则有:n＝n＋1 成
0 2 0 2
立。
证明：设n为二叉树的结点总数，n 为二叉树中度数为1的结点数。
1
二叉树中所有结点均小于或等于2，所以有：
n ＝ n ＋ n ＋ n
0 1 2
再看二叉树中的树枝（父结点和儿子结点之间的线段）总数。
在二叉树中，除根结点外，其余结点都有唯一的一个树枝进入本结点。
设B为二叉树中的树枝数，那么有下式成立：
B ＝ n－1
这些树枝都是由度为1和度为2的结点发出的，
一个度为1的结点发出一个树枝，一个度为2的结点发出两个树枝， 所以有：
B ＝ n＋2n
1 2
因此，n＝n＋1
0 2
二叉树的性质4
具有n个结点的完全二叉树的高度 k = log2n + 1
证明 根据完全二叉树的定义和性质2可知，高度为k的
完全二叉树的第一层到第k-1层具有最多的结点个数，总数为 2k-1- 1个，第k层至少具有
一个结点，至多有2k-1个结点。因此，2k-1–1 1，则其父亲结点的编号为i/2 。
（2）如果2i>n，则编号为i的结点为叶子结点，没有儿子；否则，其左儿子的编号为2i。
（3）如果2i+1> n，则编号为i的结点无右儿子；否则，其右儿子的编号为2i+1。
哈夫曼树
哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。
要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可以适当离
55《信息技术》三色速记手册
树根远一些。
二叉树的遍历
先序遍历
定义：先访问父节点，然后遍历左子树，最后遍历右子树。
中序遍历
定义：先遍历左子树，访问根节点，遍历右子树
后续遍历
56《信息技术》三色速记手册
定义：先遍历左子树，再遍历右子树，最后访问根节点
图的定义
图可以用G=（V， E）表示。
其中，V是顶点的集合，E是连接顶点的边（弧）的集合。
如果边是有方向的，称为有向图。有向图的边用<>表示。
表示从A出发到B的一条边。
在有向图中，和是不一样的。
如果边是无方向的，称为无向图。
无向图的边通常用圆括号表示。（A，B）表示顶点A和B之间有一条边。无向图也称为双向
图。
加权图：边被赋予一个权值的图称为加权图。
如果图是有向的，称为加权有向图，如果是无向的，称为加权无向图。
加权图
加权图中边的表示：或（Vi， Vj， W）
图的基本术语
邻接：如（Vi，Vj）是图中的一条边，则称Vi和Vj是邻接的。 如是图中的一条
边，则称Vi邻接到Vj，或Vj和Vi邻接。
度：无向图中邻接于某一结点的边的总数。
入度：有向图中进入某一结点的边数，称为该结点的入度
出度：有向图中离开某一结点的边数，称为该结点的出度
57《信息技术》三色速记手册
完全图
完全图：每两个节点之间都有边的无向图称为完全图。完全图有 n（n-1）/2 条边的无向
图。其中 n 是结点个数。
有向完全图：每两个节点之间都有两条弧的有向图称为有向完全图。有向完全图有 n（n-1）
条边。其中 n 是结点个数。
如果一个有向图中没有环，则称为有向无环图，简写为DAG
【知识点速记】以下表达式中n为顶点个数：
①无向完全图的边数：n（n -1）/2
②有向完全图的边数：n（n -1）
有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的
路径的图。
图中边数最多情况:即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条
边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个
顶点的强连通图最多有n（n-1）条边。
58《信息技术》三色速记手册
图的遍历
对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶
点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图
中访问一个顶点u之后，在以后的访问过程中，又可能再次返回到顶点u，所以图的遍历要
比树的遍历更复杂
深度优先搜索 广度优先搜索
深度优先搜索
1、选中第一个被访问的顶点；
2、对顶点作已访问过的标志；
3、依次从顶点的未被访问过的第一个、第二个、第三个…… 邻接顶点出发，进行深度优先
搜索；
4、如果还有顶点未被访问，则选中一个起始顶点，转向2；
5、所有的顶点都被访问到，则结束。
从结点5开始进行深度优先的搜索，
则遍历序列可以为：5，7，6，2，4，3，1，
也可以为：5，6，2，3，1，4，7。
深度优先生成树
深度优先生成森林
在进行深度优先搜索DFS时，有时并不一定能够保证从某一个结点出发能访问到所有的顶点
在这种情况下，必须再选中一个未访问过的顶点，继续进行深度优先搜索。直至所有的顶点
都被访问到为止。
这时，得到的是一组树而不是一棵树，这一组树被称为深度优先生成森林。
从结点1开始深度优先搜索
【考点四】Python语言基础
（一）Python程序的结构
1.简单Python程序示例
59《信息技术》三色速记手册
【程序清单：Hello】
#!/usr/bin/Python3
'''
Hello程序
'''
# 获取用户昵称
sname = input("请输入你的昵称：")
print("Hello,", sname)
程序运行结果：
2.Python语言程序的结构说明
（1）#!/usr/bin/Python3：为起始行，用以指定Python的解释器。
（2）''' Hello程序''' ：多行注释，常用于文档注释（Docstring）。一般出现在模块头
部、函数和类的头部，用三个单引号 ''' 或者三个双引号 """ 将注释括起来。
（3）# 获取用户昵称：单行注释，以“#”开头，“#”号后空一格。可以在语句后紧跟的注
释，至少使用两个空格和语句分开。
（4）sname=input("请输入你的昵称：")：赋值语句，将输入的字符串赋值给变量sname，
Python输入由input函数完成。Python语句结束处没有分号。
（5）print("Hello,", sname)：输出语句，Python 输出由print函数完成。
（二）Python编码规范
Python的规范基于PEP8标准。规范的编码令人赏心悦目，使代码的表达逻辑更清晰，也使
工程代码更容易被维护和交流。
1.命名规范
（1）标识符
标识符的第一个字符必须是字母表中字母或下划线_ ；标识符的其他部分由字母、数字和
下划线组成；标识符对大小写敏感。
（2）变量名
变量名尽量小写，如有多个单词，用下划线隔开，例如school_name。私有变量名用双下划
线__开头，例如__privatevar。
（3）常量
常量名称采用全大写，如有多个单词，使用下划线隔开。例如，MAX_CLIENT、MAX_CONNECTION、
CONNECTION_TIMEOUT 。
（4）类名
类名使用驼峰（CamelCase）命名风格，首字母大写，私有类可用双下划线__开头，例如Farm、
AnimalFarm、__PrivateFarm。
（5）对象名
对象名称采用全小写，例如obj、animal。
（6）函数名
函数名称采用全小写，如有多个单词，用下划线隔开，私有函数在函数前加双下划线__。例
60《信息技术》三色速记手册
如run()、run_with_env()、__private_func()。
（7）包名与模块名
包含“_init_.py”的文件夹是包（package），一个文件统为模块，包名与模块名要求统一
用小写。例如decoder、html_parser。不推荐以大写字母开头，例如Decoder。
2.代码缩进
Python最具特色的就是使用缩进来表示代码块，不需要使用大括号{}，缩进统一使用4个
空格。如果没有缩进、代码块不对齐，会导致程序运行错误。例如：
以上程序由于缩进不一致，执行后会出现类似以下错误：
3.其他规范
（1）多行语句
Python 通常是一行写完一条语句，每行代码尽量不超过80个字符。但如果语句很长，可以
使用反斜杠（\）来实现多行语句，例如：
在 []、{}或 () 中的多行语句，不需要使用反斜杠（\），例如：
（2）同一行显示多条语句
Python可以在同一行中使用多条语句，语句之间使用分号（;）分割，例如：
使用交互式命令行时，语句输入及执行结果如下：
（3）空行
函数之间或类的方法之间用空行分隔，表示一段新的代码的开始。模块级函数和类定义之
间空两行，类成员函数之间空一行。类和函数入口之间也用一行空行分隔，以突出函数入口
的开始；条件（if）、循环（while、for）、函数定义（def）、类（class）等代码段都要用
空行隔开。
（4）代码组
缩进相同的一组语句构成一个代码块，称之代码组。如if、while、def和class等复合语
句，首行以关键字开始，以冒号（:）结束，该行之后的一行或多行代码构成代码组。将首
61《信息技术》三色速记手册
行及后面的代码组称为一个子句（clause）。例如：
（5）引号
单引号'与双引号"使用没有区别，但当有重叠使用时，不能重复用双引号或者单引号。当用
单引号定义字符串时，串内字符串则使用双引号；或者反之。这是Python易用性和人性化
的一个极致体现，从而不需要转义。
三单引号（'''）与三双引号（"""）通常用于表示多行字符串以及多行注释，并且其中可
以直接使用单引号或双引号而无需转义。三双引号用于文档字符串（docstring）使用。例
如：
（6）空格
在二元运算符两边各空一格，例如=、-、+=、==、>、in、is not、and。
在pycharm编程环境中，如果二元运算符两边没有空格，将出现白色波浪线，鼠标悬停该
处，则会有错误提示（如下图所示），含义是“运算符两边没有空格”。
（三）基本数据类型
Python3 中有六个标准的数据类型：Number（数字）、String（字符串）、List（列表）、Tuple
（元组）、Set（集合）以及Dictionary（字典）。
其中，Number（数字）、String（字符串）、Tuple（元组）为不可变数据类型，
List（列表）、Dictionary（字典）、Set（集合）为可变数据类型。
62《信息技术》三色速记手册
不可变数据类型是指当该数据类型对应变量的值发生了改变，其对应的内存地址也会发生
改变；
可变数据类型则是指当该数据类型对应变量的值发生了改变，其对应的内存地址不发生改
变。
查看变量内存地址的Python内置函数是id()。
例如：对于不可变数据类型int，有整数变量x，其值由5变成11后，地址将发生变化。如
下图所示。
对于可变数据类型list，有列表a，其值由[1, 2, 3]变成[1, 2, 3, 4]后，地址保持不变。
如下图所示。
1.Number（数字）
Python的Number（数字）数据类型用于存储数值，包括 int、float、bool、complex。
（1）int整型：在Python3中，只有一种整数类型 int，通常被称为是整型或整数，有正
整数、负整数和0，不带小数点。
（2）float浮点型：即folat类型，由整数部分与小数部分组成，可用科学计数法表示。
例如，2.5e2 = 2.5 * 102 = 250。
（3）bool布尔类型：即bool类型，只有True和False两种值。
（4）complex复数类型：由实数部分和虚数部分构成，可以用a + bj或者complex(a,b)
表示。
复数的实部a和虚部b都是浮点型。
Number（数字）内置类型之间可以进行转换，将数据类型作为函数名即可。例如：
int(x) 将x转换为一个整数。
float(x) 将x转换到一个浮点数。
complex(x) 将x转换到一个复数，实数部分为 x，虚数部分为 0。
complex(x, y) 将 x 和 y 转换到一个复数，实数部分为 x，虚数部分为 y。x 和 y 是数
字表达式。
2.String（字符串）
Python中的字符串用单引号 ' 或双引号 " 括起来，两者使用完全相同。使用三引号（'''
63《信息技术》三色速记手册
或"""）可以指定一个多行字符串。
Python 不支持单字符类型，单字符在 Python 中也是作为一个字符串使用。在Python3中，
所有的字符串都是Unicode字符串。
（1）创建字符串
为变量分配一个字符串值，即创建字符串。例如：
var1 = 'Hello World!'
var2 = "Python"
（2）三引号
Python三引号允许一个字符串跨多行，字符串中可以包含换行符、制表符以及其他特殊字
符。例如，如下左图程序的三引号字符串，显示结果如右图所示。
（3）访问子字符串
Python 通过索引方式访问子字符串，即使用方括号与索引值来截取字符串。例如：
print ("var1[0]: ", var1[0])
print ("var2[1:5]: ", var2[1:5]) [1:5)
执行结果为：
var1[0]: H
var2[1:5]: ytho
var1 = 'Hello World!'
var2 = “Python“
（4）转义字符
需要在字符中使用特殊字符时，Python用反斜杠（\）。如下表：
（5）把obj对象转换为字符串
64
