Elian's blog page

哈夫曼树与哈夫曼编码路径、权和 WPL 路径：从一个结点到另一个结点经过的分支序列。 路径长度：路径上的边数。 结点的权：赋给结点的数值，常表示频度、代价等。 结点的带权路径长度：从根到该结点的路径长度乘以该结点权值。 树的带权路径长度 WPL：所有叶子结点带权路径长度之和。 $$WPL=\sum_{i=1}^{n} w_i l_i$$ 其中 $w_i$ 是第 i 个叶子权值，$l_i$ 是该叶子到根的路径长度。 哈夫曼树定义在含有 n 个带权叶结点的二叉树中，WPL 最小的二叉树称为哈夫曼树，也称最优二叉树。 同一组权值可以构造出很多棵不同形态的二叉树。比较它们时只看所有叶子的 WPL：例如某组权值在几种树形下可能得到 26、25、25、34 等不同 WPL，其中 WPL 为 25 的树形都是哈夫曼树。哈夫曼树不要求形态唯一，只要求 WPL 达到最小。 ↻ + − 构造算法给定权值 $w_1,w_2,\ldots,w_n$： 将 n 个权值分别作为 n...

树、森林与二叉树转换树的存储方式双亲表示法用数组保存结点，每个结点额外保存双亲下标。 1234typedef struct { ElemType data; int parent;} PTNode; 根结点的 parent = -1。双亲表示法找双亲方便，找孩子需要扫描数组。 适用场景：经常需要找双亲、较少需要找孩子的结构，例如并查集。 存储森林时，可以让每棵树的根结点 parent = -1；需要额外知道哪些结点是根，或扫描所有 parent = -1 的位置得到森林的根集合。 孩子表示法每个结点保存一个孩子链表，链表中记录所有孩子的位置。找孩子方便，找双亲不方便。 123456789typedef struct ChildNode { int childIndex; struct ChildNode *next;} ChildNode;typedef struct { ElemType data; ChildNode *firstChild;}...

线索二叉树为什么需要线索在含 n 个结点的二叉链表中，有 n+1 个空指针域，即 n+1 个空指针域 是可被利用的冗余链域。普通二叉链表只能方便地找到某结点的左右孩子；若要找遍历序列中的前驱或后继，通常还要重新遍历。 线索二叉树利用空指针域保存遍历序列中的前驱或后继。 结点结构1234567typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild; struct ThreadNode *rchild; int ltag; int rtag;} ThreadNode, *ThreadTree; 标志位含义： 标志 值 含义 ltag 0 lchild 指向左孩子 ltag 1 lchild 指向遍历前驱 rtag 0 rchild 指向右孩子 rtag 1 rchild 指向遍历后继 中序线索化线索化时用 pre 记录刚访问过的结点。 12345678910111213141516171819ThreadNode *pre...

二叉树遍历遍历是按照某种次序把二叉树中所有结点访问一遍，且每个结点只访问一次。 ↻ + − 三种递归遍历三种深度优先遍历只改变“访问根”的时机： 遍历 缩写 次序 先序遍历 NLR 根、左、右 中序遍历 LNR 左、根、右 后序遍历 LRN 左、右、根 手算时可以把递归遍历理解为沿树的外轮廓走一圈，每个结点会被路过三次： 第一次路过结点时访问，是先序遍历。 第二次路过结点时访问，是中序遍历。 第三次路过结点时访问，是后序遍历。 这个技巧适合快速检查手算序列，尤其是左右子树不完整时。 1234567891011121314151617181920void PreOrder(BiTree root) { if (root == NULL) return; visit(root); PreOrder(root->lchild); PreOrder(root->rchild);}void InOrder(BiTree root) { if (root == NULL)...

二叉树的存储结构顺序存储二叉树顺序存储时，必须把二叉树结点编号与完全二叉树的层序编号对应起来。 若编号从 1 开始： 结点 i 的左孩子编号为 2i。 结点 i 的右孩子编号为 2i+1。 结点 i 的双亲编号为 ⌊i/2⌋。 顺序存储适合完全二叉树。若普通二叉树也强行按完全二叉树位置存储，需要为缺失结点保留空位，可能造成严重浪费。 若编号从 0 开始： 结点 i 的左孩子编号为 2i+1。 结点 i 的右孩子编号为 2i+2。 结点 i 的双亲编号为 (i-1)/2。 链式存储二叉树最常用二叉链表： 12345typedef struct BiTNode { ElemType data; struct BiTNode *lchild; struct BiTNode *rchild;} BiTNode, *BiTree; 含 n 个结点的二叉链表有 2n 个孩子指针域。由于二叉树中实际边数为...

二叉树常考性质叶子结点与二分支结点设非空二叉树中度为 0、1、2 的结点数分别为 $n_0,n_1,n_2$，则： $$n_0=n_2+1$$ 推导： $$n=n_0+n_1+n_2$$ 又因为树中结点数等于总度数加 1： $$n=n_1+2n_2+1$$ 两式相减得 $n_0=n_2+1$。 第 i 层最多结点数二叉树第 i 层至多有： $$2^{i-1}\quad(i\ge 1)$$ 这是 m 叉树性质在 m=2 时的特例。 高度为 h 的二叉树最多结点数高度为 h 的二叉树至多有： $$2^h-1$$ 达到上界时是满二叉树。 高度为 h 的二叉树至少有 h 个结点，即每层只有一个结点。 完全二叉树高度具有 n(n>0) 个结点的完全二叉树高度为： $$h=\lceil \log_2(n+1)\rceil$$ 也可写作： $$h=\lfloor \log_2 n\rfloor+1$$ 理解方式： $$2^{h-1}\le n < 2^h$$ 或： $$2^{h-1}-1<n\le...

树的常考性质结点数与总度数树中边数等于结点数减 1。每条边都对应某个结点的一个孩子分支，所以： $$结点数 = 总度数 + 1$$ 这是普通树计数题的基础公式。 度为 m 的树与 m 叉树 项目 度为 m 的树 m 叉树 每个结点孩子数 至多 m 个 至多 m 个 是否必须有度为 m 的结点 必须至少有一个 不要求 是否可为空树 不可为空 可以为空 最少结点数 至少 $m+1$ 可以为 0 不要把“度为 m 的树”和“m 叉树”混用。前者强调整棵树的最大度恰好为 m；后者只是限制每个结点最多有 m 个孩子。 第 i 层最多结点数度为 m 的树或 m 叉树，第 i 层至多有： $$m^{i-1}\quad(i\ge 1)$$ 根在第 1 层，所以第 1 层最多 $m^0=1$ 个结点。 高度为 h 的 m 叉树最多结点数高度为 h 的 m 叉树至多有： $$1+m+m^2+\cdots+m^{h-1}=\frac{m^h-1}{m-1}$$ 达到上界时，每一层都满。 最少结点数 高度为 h 的 m 叉树至少有 h...

树的基本概念树的定义树是 $n(n \ge 0)$ 个结点的有限集合。 $n=0$ 时为空树。 非空树有且仅有一个根结点。 当 $n>1$ 时，其余结点可分为 $m(m>0)$ 个互不相交的有限集合 $T_1,T_2,\ldots,T_m$，每个集合本身又是一棵树，称为根的子树。 树是递归定义的数据结构。 非空树的基本特性 有且仅有一个根结点。 没有后继的结点称为叶子结点或终端结点。 有后继的结点称为分支结点或非终端结点。 除根结点外，任何结点都有且仅有一个前驱。 每个结点可以有 0...

KMP 的 nextval 优化next 数组已经避免了主串指针回退，但仍可能产生无效比较。 为什么需要 nextval若 next[j] = k 且 T[j] == T[k]，那么当 T[j] 与当前主串字符失配时，当前主串字符一定也不等于 T[k]。此时再退到 k 比较一次，必然再次失配。 因此可以直接跳到 next[k]，跳过这次必败比较。 递推关系常见写法： 1234567891011void GetNextval(SString t, int next[], int nextval[]) { nextval[1] = 0; for (int j = 2; j <= t.length; ++j) { int k = next[j]; if (k != 0 && t.ch[j] == t.ch[k]) { nextval[j] = nextval[k]; } else { nextval[j] = k; ...

KMP 的分界线法与 next 数组KMP 解决的问题与朴素模式匹配相同：在主串中查找模式串第一次出现的位置。区别在于：KMP 发生失配时，主串指针 i 不回退，只根据模式串自身结构调整模式串指针 j。 ↻ + − 核心思想当 S[i] != T[j] 时，T[1..j-1] 已经与主串中的一段字符完全相同。KMP 利用这段“已知匹配信息”，判断模式串应该滑到哪里继续比较。 更直观的手算方式： 在失配位置前画一条分界线。 只看分界线之前已经匹配的部分。 让模式串一步一步后退，直到分界线之前模式串部分能与相应位置的主串部分还能对上，或分界线前的模式串部分为$\emptyset$ 此时 j 指向的位置，就是 next[j]。 这种做法和“最大相等前后缀”本质等价，但计算时更贴近匹配过程：每个 next[j] 都对应“T[j] 失配后该拿谁继续和当前 S[i] 比”。 next 的含义采用教材常见的 1-based 串下标： 123456if (S.ch[i] == T.ch[j]) { ++i; // 当前字符匹配，主串继续看下一个字符 ...