笺札

前序遍历：递归与非递归实现 基本概念 前序遍历（Preorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：根结点 → 左子树 → 右子树。 递归实现简洁直观，符合二叉树递归定义。 非递归（迭代）实现需要显式使用栈模拟系统调用栈，避免递归深度过大导致的栈溢出。 算法步骤 递归版： 若当前结点为空，直接返回。 访问当前结点（如记录值）。 递归遍历左子树。 递归遍历右子树。 非递归版（栈）： 初始化栈，将根结点压入栈中。 循环直到栈为空： 弹出栈顶结点，访问它。 先将右孩子压栈（因为栈是后进先出，希望左孩子先被处理）。 再将左孩子压栈。 注意：压栈顺序为先右后左，则弹出顺序为先左后右，符合前序遍历要求。 内部实现 12345678910111213141516171819202122232425262728293031323334from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=N...

后序遍历：递归+非递归实现 基本概念 后序遍历（Postorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：左子树 → 右子树 → 根结点。 后序遍历常用于需要先处理子结点再处理父结点的场景（如删除树、计算表达式树的值）。 递归实现简单，非递归实现相对复杂，需要借助双栈或标记法来记录结点是否已访问过右子树。 算法步骤 递归版： 若当前结点为空，直接返回。 递归遍历左子树。 递归遍历右子树。 访问当前结点（如记录值）。 非递归版（双栈法）： 利用两个栈 s1 和 s2。 将根结点压入 s1。 循环弹出 s1 栈顶结点，将其压入 s2，然后将其左孩子和右孩子依次压入 s1（先左后右，则弹出时顺序不影响）。 最终 s2 的出栈顺序即为后序遍历顺序（根在最后）。 非递归版（单栈+标记法）： 使用一个栈，每个元素为 (node, visited)，visited 表示右子树是否已处理。 初始压入 (root, False)。 循环处理： 弹出栈顶。 若结点为空则跳过。 若 visited 为 True，则访问该结点。 否则，重新...

二叉树的五条核心性质 以下性质默认非空二叉树，根结点层次为 1。 性质 1：第 iii 层最多有 2i−12^{i-1}2i−1 个结点 证明：第 1 层最多 1 个（202^020），第 2 层最多 2 个（212^121），……，第 iii 层最多 2i−12^{i-1}2i−1 个。 性质 2：深度为 hhh 的二叉树最多有 2h−12^h - 12h−1 个结点 证明：各层最多结点数之和：20+21+⋯+2h−1=2h−12^0 + 2^1 + \dots + 2^{h-1} = 2^h - 120+21+⋯+2h−1=2h−1。 注意：当树为满二叉树时达到最大值。 性质 3：对任意二叉树，若叶子结点数为 n0n_0n0​，度为 2 的结点数为 n2n_2n2​，则 n0=n2+1n_0 = n_2 + 1n0​=n2​+1 证明：设总结点数 n=n0+n1+n2n = n_0 + n_1 + n_2n=n0​+n1​+n2​，总分支数（边数）B=n−1=n1+2n2B = n - 1 = n_1 + 2n_2B=n−1=n1​+2n2​。两式联立消...

二叉树的定义与特点 二叉树的定义 二叉树（Binary Tree） 是 nnn（n≥0n \ge 0n≥0）个结点的有限集合。当 n=0n = 0n=0 时为空二叉树。当 n>0n > 0n>0 时： 有且仅有一个根结点。 其余结点分为两个互不相交的子集 TLT_LTL​ 和 TRT_RTR​，分别称为左子树和右子树，且它们本身也是二叉树。 与一般树的区别 特性 一般树 二叉树 最大度数 无限制 2 子树顺序 无顺序（无序树） 严格区分左、右子树 空树 允许 允许 子树数量 任意 0, 1, 2 二叉树的特点 每个结点最多有两棵子树（度 ≤ 2）。 左右子树有序，交换后成为不同的二叉树（除非是空树或单结点）。 递归定义：二叉树本身是由根和左右子树递归构成。 二叉树可以是空树。 二叉树有五种基本形态： 空二叉树 只有根结点 只有左子树 只有右子树 左、右子树均非空 重要性质 详见 [[二叉树的五条核心性质]]。 应用场景 表达式树（编译器） 哈夫曼树（数据压缩） 二叉搜索树（高效查找） 堆（优先队列）

二叉树的存储：顺序存储/链式存储 1. 顺序存储（数组） 适用：完全二叉树或满二叉树。 原理：按层序编号，将结点存入数组对应下标位置。 优点：无需指针，内存紧凑，访问快速（通过下标计算父子关系）。 缺点：一般二叉树会浪费大量空间（存储 NULL 标记）。 存储方式 123# 用数组存储完全二叉树，索引从 1 开始tree = [None] * (n + 1) # tree[1] 为根# 结点 i 的左孩子为 2*i，右孩子为 2*i+1 空间浪费举例 深度为 h 的右斜树，需要 2h−12^h - 12h−1 个数组空间，实际只用了 h 个。 2. 链式存储（二叉链表） 适用：一般二叉树。 结构：每个结点包含数据域、左指针（lchild）、右指针（rchild）。 优点：无空间浪费，灵活。 缺点：需要额外指针开销（约 2n2n2n 个指针域）。 1234typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild;} BiTN...

层序遍历：递归实现 基本概念 层序遍历（Level Order Traversal），又称广度优先遍历（BFS），按照树的层次从上到下、从左到右依次访问结点。 通常使用队列实现迭代版。 递归实现相对不直观，但可以通过传递当前结点所在的层级（深度），将结点值按层存储到结果列表中。 递归版的核心思想：深度优先（DFS）的遍历顺序 + 按层收集。 算法步骤 定义递归函数 dfs(node, level)： 若当前结点为空，直接返回。 若 level 等于结果列表 res 的长度，说明这是该层第一个被访问的结点，需要新增一个空列表。 将当前结点值加入 res[level]。 递归处理左子树，层级加 1。 递归处理右子树，层级加 1。 从根结点（level=0）开始调用 dfs。 返回 res，即按层存储的二维列表。 费曼理解 想象你有一棵家族树，你想按辈分（层）列出所有人。你可以从老祖宗开始，每遇到一个人，就把他加入当前辈分的名单，然后继续找他的孩子们（下一辈）。即使你是按深度优先的方式（一条道走到黑）去拜访，只要记得每个人是第几辈，就能把大家正确放进对应的辈分名...

Sunday 算法 基本概念 Sunday 算法是一种字符串匹配算法，由 Daniel M. Sunday 于 1990 年提出。它是对 Boyer-Moore 算法的简化与改进，仅使用一种启发式规则：当发生失配时，考察文本串中当前匹配窗口末尾的下一个字符（即 T[i+m]），并根据该字符在模式串中的最右出现位置决定模式串向右移动的步数。该规则通常能使模式串移动更远，从而在随机文本中获得极高的平均效率。 核心思想：匹配窗口从左向右滑动，但比较顺序通常从左到右（也可从右到左，但典型实现为从左到右）。当失配时，关注窗口之后的下一个字符 c，若 c 在模式串中出现，则将模式串向右移动，使 c 与模式串中该字符最后一次出现的位置对齐；否则，整个窗口跳过 c（即移动 m+1 位）。这种策略使算法在大部分情况下具有接近线性的时间性能。 算法步骤 预处理：构建一个位移表，记录模式串中每个字符最右边的位置（从 0 开始计数）。 对于模式串 p 中的每个字符 c，记录其最后出现的位置 lastPos[c]（若字符重复，只保留最右侧的索引）。 位移值（移动步数）的计算方法： 当失配...

Horspool 算法 基本概念 Horspool 算法是 Boyer-Moore 算法的一种简化版本，由 Nigel Horspool 于 1980 年提出。它仅使用 Boyer-Moore 算法中的“坏字符规则”，舍弃了“好后缀规则”，因此实现更简单，但在大多数实际场景中依然具有较高的效率。 核心思想：将模式串与文本串从左到右对齐，但从右向左进行字符比较。当发生不匹配时，根据文本串中当前对齐位置的字符（即造成失配的字符）在模式串中最右出现的位置，决定模式串向右移动的步数。这种跳跃策略能够跳过大量不可能匹配的位置，从而提升匹配速度。 算法步骤 预处理：构建一个位移表（也称坏字符表），记录模式串中每个字符在失配时应该移动的步数。 对于模式串 p 的长度 m，除最后一个字符外，每个字符 c 的位移值为 m - 1 - i，其中 i 是该字符在模式串中最后一次出现的位置（从 0 开始计数）。 对于不在模式串中的字符，位移值设为 m。 注意：若一个字符出现多次，只保留最右侧出现的位置。 匹配过程： 将模式串与文本串左端对齐，设文本指针 i = m - 1（指向文本串...

Boyer Moore 算法 基本概念 Boyer Moore 算法（BM 算法）：由 Robert S. Boyer 和 J Strother Moore 于 1977 年提出，是一种高效的字符串搜索算法，实际应用中通常比 KMP 算法快 3~5 倍。 BM 算法核心思想：先对模式串 p 预处理，生成辅助表。在匹配过程中，如果文本串T某字符与模式串p不匹配，通过启发式规则，直接跳过不可能匹配的位置，将模式串整体向后滑动多位。 算法步骤 计算文本串T的长度n和模式串p的长度m。 对模式串p进行预处理，分别生成坏字符表bc_table和好后缀规则后移位数表 gs_table。 将模式串p的头部与文本串T的当前位置i对齐，初始i=0。每次从模式串的末尾（j=m−1）开始向前逐位比较： 如果 T[i+j]与 p[j]T[i+j]与 p[j]T[i+j]与 p[j]相等，则继续向前比较下一个字符。 如果模式串所有字符均匹配，则返回当前匹配的起始位置 ii。 如果 T[i+j]与p[j]T[i+j]与p[j]T[i+j]与p[j] 不相等： 分别根据坏字符表和好后缀表...

一、实验目的 理解算术编码的原理，掌握区间划分与概率累加方法。 实现算术编码的编码与解码过程，并生成最短二进制码字。 验证编码的正确性，确保解码后能完全恢复原字符串 二、实验环境 编程语言：Python 关键库：decimal（高精度十进制运算） 输入参数：   - 字符集：['W', 'X', 'Y', 'Z']   - 概率分布：[0.2, 0.3, 0.1, 0.4]   - 待编码字符串：'YWXZWYX' 三、实验原理 算术编码将整个输入序列映射为实数区间 [0,1)[0, 1)[0,1) 中的一个子区间，并用该区间内的一个二进制小数表示。其核心是区间递归划分 初始区间：[0,1)[0, 1)[0,1)。 根据符号概率，将当前区间按符号的概率比例划分为子区间。 读入一个符号，将当前区间更新为该符号对应的子区间。 重复直到所有符号处理完毕。 输出编码：从最终区间内选择一个二进制小数，使得该小数能够唯一标识该区间，且位数尽可能少。 解码时，根据二进制码字还原出小数，再根据相同的概率模型逐步确定符号。 四、关键函数 4.1 区间构建函数 build_in...