字符串简称串，计算机中非数值处理的对象基本上都是字符串数据。常见的信息检索系统(如搜索引擎)、文本编辑程序(如 Word)、问答系统、自然语言翻译系统等，均以字符串作为核心处理对象。本章将详细介绍字符串的存储结构及其相关操作。

模式匹配是指在主串中查找与模式串(待搜索的字符串)完全相同的子串，并返回其首次出现的位置。本节基于定长顺序存储结构，介绍一种不依赖其他串操作的暴力匹配算法。

树是 n (n \geq 0) 个结点的有限集。当 n = 0 时，称为空树。在任意一棵非空树中必须满足：

二叉树是一种特殊的树形结构，其核心特征在于：每个结点至多拥有两棵子树(不存在度大于2的结点)，且这两棵子树具有明确的左右之分，其次序是固定的，不可交换。

二叉树的遍历是指按照某种搜索路径访问树中的每个结点，使得每个结点均被访问一次且仅被访问一次。由于二叉树是一种非线性结构，每个结点最多有两棵子树，因此需要确定一种系统性的访问顺序，将树中结点排列成一个线性序列，以便于后续处理。

树的存储方式有多种，既可采用顺序存储结构，也可采用链式存储结构。无论采用何种方式，都必须能够唯一地反映树中各结点之间的逻辑关系。下面介绍三种常用的存储结构。

在介绍哈夫曼树之前，先明确几个相关概念：

图 G 由顶点集 V 和边集 E 组成，记为 G = (V, E)。其中，V(G) 表示图 G 中顶点的有限非空集；E(G) 表示图 G 中顶点之间的关系(边)集合。若 V = \{v_1, v_2, \cdots, v_n\}，则用 |V| 表示图 G 中顶点的数量，E = \{(u, v) \mid u \in V, v \in V\}，用 |E| 表示图 G 中边的数量。