Elian's blog page

图的定义图由顶点集和边集组成，记为： $$G=(V,E)$$ G：graph，表示图。 V：vertex set，表示顶点集。 E：edge set，表示边集。 V(G)：图 G 的顶点集，是有限非空集。 E(G)：图 G 中顶点之间关系的集合，可以为空。 若： $$V={v_1,v_2,\ldots,v_n}$$ 则： $|V|$ 表示图中顶点个数，也称图的阶。 $|E|$ 表示图中边的条数。 图不能为空线性表可以是空表，树可以是空树，但图不可以没有顶点。 图允许： V 非空，E 非空。 V 非空，E = ∅。 图不允许： V = ∅。 因此，只有顶点而没有边的结构仍然是图；没有顶点的结构不是图。 图逻辑结构的应用图适合表示“多对多”的关系： 顶点 V 边 E 关系含义 车站 铁路 车站之间是否有铁路连接 路口 道路 路口之间是否有道路连接 用户 好友关系 两个用户是否互为好友 用户 关注关系 一个用户是否关注另一个用户 若关系没有方向，通常抽象为无向图；若关系有方向，通常抽象为有向图。

简单图与多重图图还可以按是否允许重复边、自环分为简单图和多重图。 简单图简单图满足两个条件： 不存在重复边。 不存在顶点到自身的边。 顶点到自身的边称为自环。简单图中不允许自环。 数据结构课程中，除非题目特别说明，通常默认讨论简单图。 多重图若图中某两个顶点之间的边数多于一条，或者允许顶点通过同一条边和自己关联，则称为多重图。 多重图可以出现： 重复边：同一对顶点之间有多条边。 自环：某条边的两个端点是同一个顶点。 对比 类型 重复边 自环 常规数据结构题默认 简单图 不允许 不允许 是 多重图 允许 允许 否 后续若题目没有特别说明，计算边数上界、邻接矩阵、邻接表、遍历等内容时，都按简单图处理。

无向图与有向图图的边是否有方向，决定它是无向图还是有向图。 无向图若 E 是无向边的有限集合，则图 G 为无向图。 无向边是顶点的无序对，记为： $$(v,w)$$ 因为没有方向，所以： $$(v,w)=(w,v)$$ 相关术语： 顶点 v 和 w 互为邻接点。 边 (v,w) 依附于顶点 v 和 w。 也可以说边 (v,w) 与顶点 v、w 相关联。 例如： $$V={A,B,C,D,E}$$ $$E={(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)}$$ 有向图若 E 是有向边的有限集合，则图 G 为有向图。有向边$v\to w$也称为弧。 弧是顶点的有序对，记为： $$\langle v,w\rangle$$ 其中： v 称为弧尾。 w 称为弧头。 $\langle v,w\rangle$ 表示从 v 到 w 的弧。 也称 v 邻接到 w，或 w 邻接自 v。 有向边有方向，因此： $$\langle v,w\rangle \ne \langle...

平衡二叉树概念平衡二叉树要求树上任一结点的左子树和右子树高度差不超过 1。 定义要点 限制对象是“任一结点”，不是只检查根结点。 比较的是左子树高度和右子树高度。 高度差的绝对值不能超过 1。 若用平衡因子表示： $$BF = h_{left} - h_{right}$$ 则平衡二叉树中任一结点的平衡因子只能是 -1、0 或 1。 为什么需要平衡普通二叉排序树在插入顺序不利时可能退化成接近链表的形态，查找路径变长。 平衡二叉树通过限制左右子树高度差，使树高保持较低，从而提高搜索效率。后续学习 AVL 树时，插入和删除都要在保持二叉排序树性质的同时恢复平衡。

二叉排序树概念二叉排序树又称二叉查找树。它或者是空二叉树，或者满足以下递归性质： 左子树上所有结点关键字均小于根结点关键字。 右子树上所有结点关键字均大于根结点关键字。 左子树和右子树也分别是二叉排序树。 查找与排序含义二叉排序树可用于元素查找和排序： 查找时，从根开始比较关键字，小于根就进入左子树，大于根就进入右子树。 中序遍历二叉排序树，可以得到关键字的递增序列。 例如图中以 50 为根： 左子树中的 26, 21, 30 都小于 50。 右子树中的 66, 60, 70, 68 都大于 50。 对任一子树也要继续满足“左小、根中、右大”。 二叉排序树的查找、插入、删除通常在查找章节展开；这里先记住定义和中序遍历性质。

二叉树的五种基本形态二叉树允许为空，并且左右子树的位置有含义。因此，从根结点角度看，二叉树有五种基本形态。 五种形态 形态 说明 空二叉树 没有任何结点，是递归定义和算法递归结束的边界。 只有根结点 根结点没有左子树，也没有右子树。 只有左子树 根结点有左子树，右子树为空。 只有右子树 根结点有右子树，左子树为空。 左右子树都有 根结点同时有左子树和右子树。 查阅重点只含一个孩子时，不要只说“有一个孩子”，要明确是左孩子还是右孩子。这个位置差异会影响： 遍历序列 顺序存储中的空位 完全二叉树的判断 线索二叉树中前驱、后继线索的含义

二叉树定义二叉树是 $n(n\ge 0)$ 个结点的有限集合： 当 n = 0 时，称为空二叉树。 当 n > 0 时，由一个根结点和两棵互不相交的左子树、右子树组成。 左子树和右子树本身又分别是一棵二叉树。 二叉树是递归定义的数据结构。讨论二叉树的遍历、存储、线索化时，很多算法都可以自然写成“处理根、递归处理左子树、递归处理右子树”的形式。 基本特点 每个结点至多有两棵子树。 左子树和右子树有次序，不能随意颠倒。 即使某个结点只有一个孩子，也要区分它是左孩子还是右孩子。 空树也是二叉树，这是递归定义成立的边界情况。 每个节点的度只有三种选择：$0,1,2$ 与“度为 2 的有序树”的区别二叉树不是简单的“度为 2 的有序树”： 二叉树可以为空；普通树通常至少有一个结点。 二叉树中一个结点只有一个孩子时，必须说明它是左孩子还是右孩子。 度为 2 的有序树只强调孩子之间有顺序，不天然保留“左空、右非空”或“左非空、右空”这种位置区别。 这个区别会影响二叉树顺序存储：普通二叉树若按完全二叉树位置存储，缺失的左/右位置也可能需要保留空位。

完全二叉树当一棵二叉树的结点与同高度满二叉树中编号 1..n 的结点一一对应时，称为完全二叉树。 定义的等价理解完全二叉树可以理解为：从满二叉树最下一层的最右侧开始，连续删去若干结点后得到的二叉树。 也可以按层序扫描理解： 从上到下、从左到右依次编号。 结点编号必须连续占据 1..n。 一旦层序位置上出现空缺，后面不能再出现非空结点。 特点 只有最后两层可能有叶子结点。 最多只有一个度为 1 的结点。 如果某结点只有一个孩子，则一定是左孩子。 按层序编号后，仍满足左孩子 2i、右孩子 2i+1、双亲 $\lfloor i/2\rfloor$。 i <= ⌊n/2⌋ 的结点是分支结点，i > ⌊n/2⌋ 的结点是叶子结点。 常见判断错误若某个结点没有左孩子却有右孩子，则一定不是完全二叉树。 若最后一层中间出现空位，而右侧还有结点，也不是完全二叉树。完全二叉树的最后一层必须从左向右连续填充。 完全二叉树的高度、叶子数、度为 1 的结点数等推导见二叉树常考性质。

满二叉树高度为 h 且含有 $2^h-1$ 个结点的二叉树称为满二叉树。 定义要点 只有最后一层有叶子结点。 所有非叶结点都有两个孩子，不存在度为 1 的结点。 第 i 层结点数达到二叉树第 i 层的最大值 $2^{i-1}$。 高度为 h 时，总结点数达到二叉树高度为 h 时的最大值 $2^h-1$。 编号性质按层序从 1 开始编号时： 结点 i 的左孩子编号为 2i。 结点 i 的右孩子编号为 2i+1。 若 i > 1，结点 i 的双亲编号为 $\lfloor i/2\rfloor$。 这些编号关系也适用于完全二叉树中实际存在的结点。 容易混淆点满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。 判断满二叉树时，不能只看“形状比较饱满”，要看是否满足高度 h 与结点数 $2^h-1$ 的严格关系。

并查集并查集是集合逻辑结构的一种实现，用互不相交的树表示多个集合，只支持两类核心操作： Find：查找元素属于哪个集合。 Union：合并两个互不相交的集合。 ↻ + − 存储结构并查集通常使用数组形式的双亲表示法： 根结点用负数表示，其绝对值表示树的总结点数。 非根结点保存双亲结点的数组下标。 12345678#define SIZE 100int parent[SIZE];void InitSet(int parent[], int n) { for (int i = 0; i < n; ++i) { parent[i] = -1; }} 初始时每个元素各自构成一个集合，因此每个位置都是根。 Find 操作123456int Find(int parent[], int x) { while (parent[x] >= 0) { x = parent[x]; } return...