字典树
字典树 基本概念 字典树(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。两式联立消...









