笺札

字典树 基本概念 字典树（Trie），又称前缀树或单词查找树，是一种用于高效存储和检索字符串集合中键值的数据结构。它的每个节点代表一个字符，从根节点到某个节点路径上的字符组成一个字符串。字典树广泛应用于字符串前缀匹配、自动补全、单词计数等场景，能够在 O(L) 时间内完成插入、查找和前缀查询（L 为字符串长度） 数据结构的三要素 逻辑结构：树形结构，每个节点包含若干指向子节点的指针（通常用字典或数组实现），根节点为空字符，每个节点可以标记是否为一个单词的结尾。 存储结构： 链式存储：每个节点维护一个字典（如 Python 的 dict）或固定大小的数组（如 26 个字母），存储指向子节点的引用。 字典实现适用于字符集较大的场景（如 Unicode），数组实现适用于小字符集（如英文小写字母），访问速度更快但空间固定。 数据的运算： 插入：从根节点开始，依次将字符串的每个字符作为键创建子节点，最后标记节点为单词结尾。 查找：沿着字符路径遍历，若路径存在且最终节点被标记为单词结尾，则查找成功。 前缀查询：给定前缀，检查是否存在以该前缀开头的单词，只需路径存在即可（无需结...

中序遍历：递归+非递归实现 基本概念 中序遍历（Inorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：左子树 → 根结点 → 右子树。 对于二叉搜索树（BST），中序遍历的结果是升序序列。 递归实现直观，非递归实现需借助栈模拟系统调用过程。 算法步骤 递归版： 若当前结点为空，直接返回。 递归遍历左子树。 访问当前结点（如记录值）。 递归遍历右子树。 非递归版（栈）： 初始化空栈，cur 指向根结点。 循环直到 cur 为空且栈为空： 将 cur 及其所有左孩子依次压栈（cur = cur.left）。 弹出栈顶结点，访问它。 将 cur 设为弹出结点的右孩子，继续循环。 内部实现 12345678910111213141516171819202122232425262728293031323334353637from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): ...

特殊二叉树：斜树 / 满二叉树 / 完全二叉树 1. 斜树（Skewed Tree） 定义：所有结点都只有左孩子（左斜树）或只有右孩子（右斜树）。 特点：退化为线性结构，树的高度等于结点数。 性能：查找、插入、删除退化为 O(n)O(n)O(n)，失去了二叉树的优势。 2. 满二叉树（Full Binary Tree / Perfect Binary Tree） 定义：所有分支结点都有左孩子和右孩子，且所有叶子都在同一层。 性质（高度为 hhh，根为第 1 层）： 第 iii 层结点数：2i−12^{i-1}2i−1 总结点数：2h−12^h - 12h−1 叶子数：2h−12^{h-1}2h−1 特点：形态完美，所有叶子深度相同。 3. 完全二叉树（Complete Binary Tree） 定义：对高度为 hhh、有 nnn 个结点的二叉树，当且仅当其每个结点都与高度为 hhh 的满二叉树中编号 1 到 nnn 的结点一一对应时，称为完全二叉树。 通俗理解：除最后一层外，其余层结点数达到最大；最后一层结点向左靠拢。 性质： 叶子结点只可能在最后两层出...

树与二叉树 · 知识地图 MOC 🌱 基础概念 [[树的定义与基本术语]] [[树的分类]] [[树的存储结构]] 🔍 二叉树核心 基础定义与性质 [[二叉树的定义与特点]] [[特殊二叉树]] [[二叉树的五条核心性质]] [[二叉树的存储]] 遍历算法（核心考点） [[前序遍历：递归+非递归实现]] [[中序遍历：递归+非递归实现]] [[后序遍历：递归+非递归实现]] [[层序遍历：递归实现]] 🚩 拓展变种二叉树 [[二叉搜索树BST]] [[平衡二叉树AVL：定义与旋转调整]] 堆 [[哈夫曼树：定义与哈夫曼编码]] [[红黑树：基本性质与应用]]

树的分类 根据不同的划分标准，树可以分为多种类型： 1. 按结点有序性 有序树：树中结点的各子树从左到右是有顺序的，不能互换。 无序树：结点的各子树之间没有顺序关系。 2. 按度数限制 一般树：结点的度不受限制（通常 mmm 叉树即每个结点最多 mmm 个孩子）。 二叉树：每个结点最多两个孩子（0,1,20,1,20,1,2），且区分左、右子树。 mmm 叉树：每个结点最多 mmm 个孩子。 3. 按节点值 有序树（如二叉搜索树）：左子树所有结点值小于根，右子树所有结点值大于根。 堆：大顶堆（根 ≥ 孩子）、小顶堆（根 ≤ 孩子）。 4. 按形态（特殊二叉树） 斜树：所有结点只有左孩子（左斜树）或只有右孩子（右斜树）。 满二叉树：所有分支结点都有左、右子树，且所有叶子都在同一层。 完全二叉树：除最后一层外，其余层结点数达到最大，最后一层结点向左靠拢。 5. 按平衡性 平衡二叉树：任意结点左右子树高度差 ≤ 1（如 AVL 树）。 非平衡二叉树：不满足平衡条件。 6. 按实际应用 二叉搜索树（BST）：快速查找、插入、删除。 堆（Heap）：优先...

树的定义与基本术语 树的定义 树（Tree） 是 nnn（n≥0n \ge 0n≥0）个结点的有限集合。当 n=0n = 0n=0 时称为空树。在任意一棵非空树中： 有且仅有一个特定的结点称为根（Root）。 当 n>1n > 1n>1 时，其余结点可分为 mmm（m>0m > 0m>0）个互不相交的有限集 T1,T2,…,TmT_1, T_2, \dots, T_mT1​,T2​,…,Tm​，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。 基本术语 术语 英文 解释 结点 Node 树中的基本元素，包含数据项和指向子树的指针。 度 Degree 结点拥有的子树个数。树的度是树内各结点度的最大值。 叶子（终端结点） Leaf 度为 0 的结点。 分支结点（非终端结点） Branch Node 度大于 0 的结点。 孩子 Child 结点子树的根称为该结点的孩子。 双亲 Parent 该结点称为其孩子的双亲（父结点）。 兄弟 Sibling 同一双亲的孩子之间互称兄弟。 祖先...

树的存储结构 树的存储结构主要分为三种：双亲表示法、孩子表示法、孩子兄弟表示法。 1. 双亲表示法 实现：用一组连续空间存储结点，每个结点附加一个指针（下标）指向其双亲。 优点：容易找到双亲。 缺点：找孩子需要遍历。 12345678typedef struct { ElemType data; int parent; // 双亲位置下标（-1 表示根）} PTNode;typedef struct { PTNode nodes[MAX_SIZE]; int n; // 结点数} PTree; 2. 孩子表示法 实现：用数组存储结点，每个结点维护一个链表，链接其所有孩子。 优点：容易找到孩子。 缺点：找双亲需要遍历。 123456789typedef struct ChildNode { int child; // 孩子下标 struct ChildNode *next;} ChildNode;typedef ...

前序遍历：递归与非递归实现 基本概念 前序遍历（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​。两式联立消...