同学们好 我们接下来的这一章 将以树作为主题 在此前我们所介绍的两种 主要的数据结构 也就是向量以及列表 从分类上讲 都属于所谓的线性结构 而我们很快就会看到 树结构并不是严格的线性结构 因此这一章将是我们这门课的 又一里程碑 在进入这样一个新的阶段之前 或许我们应该首先来 回答一个问题 此前所介绍的向量以及列表 难道的确不够用吗？ 没错 是这样的 我们来考察一下这两种结构 我们此前所要求的 也是我们此后 将要要求的典型的几类操作 第一类也就是所谓的静态操作 以查找作为代表；而第二类呢 是动态操作 也就是典型的 插入或者是删除 我们此前看到过 向量的查找操作效率非常高 比如说以典型的二分查找为例 可以做到logn的效率 然而遗憾的是 向量的动态操作 无论是插入和删除 在最坏情况以至平均情况 都非常的差 具体来说 需要线性的时间 而同时我们也注意到列表呈现出一种 完全对称的特性 也就是说 如果希望在列表中进行查找 无论是有序组织的 还是无序组织的 性能在最坏情况下以至平均情况下 也都是线性的 这种效率非常低 得益于列表的寻位置访问的方式 一旦我们能够给定一个具体的操作位置 对于列表的动态操作 都将只是在局部进行 换而言之 它只需要O(1)的时间 由此可见 无论是向量还是列表 都没有办法兼顾静态和动态操作的 同时高效性 而如何将二者的优势结合起来 也将是我们接下来要讨论的 一个重点话题 联想到本章的主题 我想大家不难猜出来 我们的解法 恰好就是在树这种数据结构 没错 树这种数据结构可以认为是 将二者的优点融合起来 我们将会看到 它可以理解为是 列表的列表 也可以认为是二维的列表 也正因为这个原因 可以认为树型结构 既不是我们此前所讲的 狭义的线性结构 同时它也带有一定的线性特征 为了与稍后非线性的图结构相区别 我们不妨称树型结构为半线性结构 那么接下来 我们首先来了解一下 什么是树 当然如果你对这种概念 以及相关的一些术语 已经非常了解 可以直接跳过接下来的一节