二叉树的基本性质包括:
1. 二叉树的第 i 层上至多有 2i-1(i>=1)个结点;
2. 深度为 k 的二叉树中至多有 2k-1(k>=1)个结点;
3. 在任意一棵二叉树中,若有终端结点数为 n0,度为 2 的结点数为 n2,则 no=n2+1.
二叉树是非线性结构,通常采用链式存储结构。表示二叉树的结点需要三个域:数据域和
左、右指针域。
所谓二叉树的遍历,就是以一定的规律访问二叉树的每个结点,使每个结点均被访问一次
且仅访问一次的过程。
限定先左后右的次序,只有 3 种方式:DLR LDR LRD (先序后遍历、中序遍历、后序遍历)。
一个结点的二叉树的度为 0.
在树形结构中,二叉树的存储空间利用率最高。
链式存储结构的二叉树中,结点数越多,空指针数就越多。(空指针数=结点数+1)
采用链式存储结构的二叉树,结点之间的关系通过指针表示。
二叉树顺序存储结构中,可能有空结点,没有空指针。
二叉树不是树的特殊形式。
二叉树排序树的平均检索长度与对半查找为同一数量级,即 O(log2n)
2.17 图
图是网状关系的数据结构,是较为复杂的结构形式。
在线性表中,数据元素之间是线性关系,每个数据元素只有一个前驱、一个后继;在树中,
数据元素之间是层次关系,每一层上的数据元素可以和下一层中零个或多个元素相关,但
只能和上一层中的一个元素相关;在图中,数据元素之间的关系是可以任意的,任意两个
元素之间都可能相关。
图的存储:1)邻接矩阵;2)邻接表。
图的遍历 通常采用的遍历方法有两种:深度优先搜索和广度优先搜索。
由 n 个顶点组成的无向连通图最多可以有 n(n-1)/2 条边。
由 n 个顶点组成的有向图的最多弧的数目为 n(n-1)条弧。
2.18-19 线性查找、对半查找和分块查找/散列查找
线性查找 从一端逐个向另一端对比查找
对半查找 与中间元素比较,是适合于对有序表进行查找的方法。
分块查找
散列函数常用的几种:
1)直接定址法;2)除留余数法;3)平方取中法;4)折叠法;5)数字分析法。
冲突的处理方法: 1)开放定址法;2)链地址法(拉链法);3)再散列法。
与其它查找方法相比,散列查找法的特点是:由关键字计算元素的存储地址后,可再进行
关键字的比较,进行查找。
2.20-21 选择排序、插入排序和冒泡排序;快速排序和归并排序
选择排序 选关键字最小的靠左,不稳定。比较次数与序列的初始状态无关,次数为 n(n-
1)/2,复杂度为 O(n2)
插入排序 1)直接插入排序;2)对半插入排序。是稳定的。
冒泡排序
各种方法的运算特点:
排序方法 运算特点
选择 选择-交换 插入 移动-插入
冒泡 两两交换 快速 交换-分区