树容器库
4.85/5 (28投票s)
一个用于将数据存储在树状结构中的通用模板类库。
引言
标准模板库 (STL) 为 C++ 开发人员提供了许多有用的通用容器类。STL 中未包含的一种容器是树容器。本文介绍的 Tree Container Library (TCL) 是一个通用的树容器库，它不仅功能与 STL 非常相似，而且与 STL 算法兼容。该库和本文提供的所有示例都兼容 VC6、VC7 和 VC8 (Visual Studio 2005) 以及 GCC。如果其他 C++ 编译器符合 C++ 模板标准，那么它们应该也能轻松支持该库。
完整的库可在上面的源代码下载中找到。第二个下载中还提供了 TCL 的完整文档，格式为 CHM 文件。该文档包含数百页内容，并附有清晰描述 TCL 用法的示例。文档中详细解释并举例说明了 TCL 中每个容器的每项操作，还包含了其他示例（以及源代码文件）。
TCL 由四个容器类模板组成，与 STL 中的容器类似。这些容器允许将基本数据类型或用户定义类型存储在树形结构中的节点里。树的每个节点本身都被视为一棵树（或子树），具有它所属的树容器的所有属性。因此，对树容器执行的所有操作同样可以对树中的任何节点执行。提供了迭代器以允许遍历树节点。还提供了插入和查找操作以及各种其他操作。
TCL 提供了四个树容器，根据其使用意图而有所不同
- tree
- multitree
- unique_tree
- sequential_tree
tree 容器用于树结构，其中每个兄弟节点都是唯一的，或者说，特定父节点的每个子节点都可以唯一地区分。非兄弟节点不必唯一。
multitree 容器用于树结构，其中兄弟节点不必唯一，或者说，具有相同父节点的子节点不必可区分。
unique_tree 容器用于树结构，其中树中的每个节点都是唯一的。由于保证了树中的每个节点都是唯一的，因此 unique_tree 除了 tree 和 multitree 中找到的操作外，还提供了 find_deep() 操作以及其他操作。
sequential_tree 容器用于树结构，其中树节点没有自然顺序。如果需要，子节点可以在插入后排序。排序顺序可以由二元谓词、函数对象确定，或者默认情况下由元素的 < 运算符确定。
下面简单的类图显示了基类与值类（树容器类）之间的关系。basic_tree 是所有树容器的基树，并包含所有树共有的基本操作。sequential_tree 直接派生自 basic_tree。associative_tree 也作为关联树的基类。该类包含仅对那些树（tree、multitree 和 unique_tree）特有的操作。
tree 和 multitree 在操作和接口上非常相似。两者之间的区别很大程度上类似于 STL 中的 set 和 multiset 之间的区别。unique_tree 提供了比 tree 和 multitree 更多的功能，因为树中的每个节点都是唯一的。例如，tree、multitree 和 unique_tree 都提供 find() 操作，该操作搜索单个父节点中包含的匹配子节点。unique_tree 提供了额外的操作 find_deep()，它不仅搜索父节点的直接子节点，还搜索其后代。
unique_tree 还提供了对这三种树类型常见接口的扩展。所有四种树都提供 insert(child) 操作，其中子节点被插入到发出 insert 操作的父节点中。然而，unique_tree 提供了对该操作和其他操作的扩展。例如，unique_tree 提供了另一个 insert 操作 insert(parent, child)，它将子节点插入到指定的父节点中（如果找到）。
tree、multitree 和 unique_tree 被认为是关联树容器，因为它们都使用 std::set 来内部包含子节点。然而，sequential_tree 使用 std::vector 来存储子节点。因此，sequential_tree 不提供像关联树容器那样的 find() 操作。但是，sequential_tree 有其独特的操作，例如 multiple sort() 操作，可用于对其父节点内的任何/所有子节点进行排序。关联树不需要 sort() 操作，因为它们的节点是自然排序的。
要理解 TCL 中树容器的结构以及迭代器的工作原理，需要对“节点”和“元素”的概念有深刻的理解。在 TCL 中，“节点”一词用于指代树结构中包含“stored_type”元素的某个对象。存储类型元素（您在树中存储的元素）本身不被视为节点，而是包含在节点中。然后，树结构由节点组成，最顶端的节点是根节点。树结构中的所有节点（除少数例外）都具有与树本身相同的操作和属性。元素的概念是指定正在树的节点中存储的 stored_type 对象。节点和元素被视为两个独立的实体。树结构由节点组成。节点可以包含子节点，而子节点又可以有自己的子节点。元素存在于节点中，是用户指定存储在树中的对象。
在 TCL 中，迭代器用于遍历树容器的宽度和深度。TCL 中有几种不同类别的迭代器。对迭代器的主要分类方式是它们遍历树节点的方式。从这个角度来看，有四种类型的迭代器，如下所示。
- 子节点迭代器
- 反向子节点迭代器
- 后代迭代器
- 前序遍历
- 后序遍历
- 层序遍历
- 有序迭代器
用于遍历节点的直接子节点。
用于反向遍历节点的直接子节点。
用于遍历树或子树的后代。后代迭代器遍历树/子树的宽度和深度。有三种流行的方法用于遍历树结构，以及三种类型的后代迭代器来提供这些遍历。
在此遍历中，首先访问父节点，然后立即访问该节点的子节点，从左到右。
在此遍历中，首先从左到右访问所有子节点，然后访问子节点的父节点。
在此遍历中，按顺序访问树结构的每个级别，从上到下。
这些迭代器仅适用于 unique_tree。它们为父节点中的子节点提供了替代的排序方案。
TCL 迭代器还可以按其暴露的内容进行分类。要理解这个概念，需要对“节点”和“元素”之间的区别有深刻的理解。在 TCL 中，节点被认为是树结构本身的一部分。节点用于存储树容器中的数据或元素。树结构中的每个节点都具有与树结构本身相同的属性。实际上，对树结构执行的任何操作（除少数例外）也可以对树结构中的任何节点执行。节点实际上是结构中的子树。
另一方面，元素是存储在树容器中的数据。树结构中的每个节点都包含一个元素。您可以自行决定树结构中的元素是什么。元素可以是基本类型，例如 int 或 double，也可以是用户定义的类型。
现在，子节点、反向和后代迭代器都有两种变体，这取决于迭代器暴露的内容。这两种迭代器类型以相同的方式进行迭代。唯一的区别是迭代器的解引用运算符和指针运算符返回什么。
- 元素迭代器
- 节点迭代器
元素迭代器分别通过 -> 和 * 运算符返回对底层元素的指针/引用。
节点迭代器分别通过 -> 和 * 运算符返回对底层节点的指针/引用。
子节点、反向和后代迭代器都分为上述两种变体。因此，TCL 提供了子节点“元素”迭代器、反向“元素”迭代器、后代“元素”迭代器，以及子节点“节点”迭代器、反向“节点”迭代器和后代“节点”迭代器。
通常，您将在大多数情况下使用元素迭代器。TCL 的许多操作（如 find()）返回子节点元素迭代器。这些迭代器比节点迭代器使用得更多，因此它们不像节点迭代器和操作那样带有元素前缀。
当然，所有迭代器都有 const 和非 const 两种变体。
迭代器不仅可用于以各种方式遍历树结构，而且许多对树执行的操作（如 find() 和 insert() 操作）还会返回迭代器。TCL 的许多树容器操作返回的迭代器通常是子节点元素迭代器，除非明确命名以示区分。所有迭代器的创建语法与 STL 中的迭代器相同。如果一棵树容器包含 CMyClass 类型的对象，则子节点元素迭代器将创建为 tree<CMyClass>::iterator it; 或 tree<CMyClass>::const_iterator it;。这两个子节点迭代器仅遍历父节点的直接子节点。
“子节点”和“后代”迭代器都可以与 STL 算法一起使用，并且“元素”和“节点”迭代器也都可以。这意味着，存在于树容器节点中的元素可以通过“元素”迭代器在 STL 容器之间来回复制。节点可以通过“节点”迭代器在 STL 容器之间来回复制。此外，几乎任何 STL 算法现在都可以与 TCL 树容器和迭代器一起使用。与 STL 算法一起使用时，必须清楚 TCL 的“元素”迭代器暴露的是节点的元素，而“节点”迭代器暴露的是节点本身。
如上所述，对于“元素”迭代器，* 和 -> 运算符被重载以返回指向迭代器所指向节点内的底层元素的引用/指针。所有“元素”迭代器都具有一个 node() 操作，该操作返回指向包含该元素的底层节点的指针。通过使用元素迭代器的 node() 操作，元素迭代器就可以使用节点的 insert() 和 find() 等操作。请记住，节点具有声明树（节点所属的树）相同的接口。（节点本身就是树）。声明的树容器与其节点之间的唯一区别在于，声明的树容器没有父节点。（它是根节点）。
关注点
在开发这个库的过程中，我了解了开发容器类时遇到的困难。浏览 STL 的实现给了我开发这个库所需的许多想法。
历史
TCL 的最新版本 (4.08) 将所有树容器都包含在“tcl”命名空间中。
有关设计和操作的更多信息，可以在 此处找到。