std::map基于红黑树。您还可以使用其他容器来帮助您实现自己的树类型。

std::map基于红黑树。您还可以使用其他容器来帮助您实现自己的树类型。

在某种程度上，std::map是一棵树(它被要求具有与平衡二叉树相同的性能特征)，但它不公开其他树功能。不包含真正的树数据结构的原因可能只是不包含stl中的所有内容。stl可以被视为一个框架，用于实现您自己的算法和数据结构。

一般来说，如果你想要一个基本的库功能，而它不在stl中，修复方法是查看BOOST。

除此之外，还有很多库，这取决于树的需要。

The STL's philosophy is that you choose a container based on guarantees and not based on how the container is implemented. For example, your choice of container may be based on a need for fast lookups. For all you care, the container may be implemented as a unidirectional list -- as long as searching is very fast you'd be happy. That's because you're not touching the internals anyhow, you're using iterators or member functions for the access. Your code is not bound to how the container is implemented but to how fast it is, or whether it has a fixed and defined ordering, or whether it is efficient on space, and so on.

如果您正在寻找一个rb树实现，那么stl_tree.h可能也适合您。

我认为没有STL树有几个原因。树是一种递归数据结构，就像容器(列表，向量，集合)一样，具有非常不同的精细结构，这使得正确的选择非常棘手。使用STL也很容易以基本形式构造它们。

一个有限根树可以被认为是一个容器，它有一个值或有效负载，比如一个类A的实例和一个可能为空的根树(子)集合;具有空子树集合的树被认为是叶树。

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

人们必须考虑一下迭代器的设计等，以及允许在树之间定义哪些积和积操作并使之高效——原始的STL必须写得很好——这样在默认情况下，空的集合、向量或列表容器就真的是空的。

树在许多数学结构中起着至关重要的作用(参见Butcher、Grossman和Larsen的经典论文;还有康内斯和克里默的论文，他们可以结合的例子，以及他们是如何用来列举的)。认为它们的作用只是促进某些其他行动是不正确的。相反，由于它们作为数据结构的基本角色，它们有助于完成这些任务。

然而，除了树，还有“协同树”;上面这些树都有一个特性，如果你删除根，你就删除了所有东西。

考虑树中的迭代器，它们可能会被实现为一个简单的迭代器堆栈，指向一个节点，以及它的父节点……一直到根部。

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

但是，你想要多少就可以有多少;它们共同组成了一个“树”，但所有的箭头都指向根，这个协同树可以通过迭代器迭代平凡迭代器和根;但是它不能向下或向下导航(它不知道其他迭代器)，也不能删除迭代器集合，除非通过跟踪所有实例。

Trees are incredibly useful, they have a lot of structure, this makes it a serious challenge to get the definitively correct approach. In my view this is why they are not implemented in the STL. Moreover, in the past, I have seen people get religious and find the idea of a type of container containing instances of its own type challenging - but they have to face it - that is what a tree type represents - it is a node containing a possibly empty collection of (smaller) trees. The current language permits it without challenge providing the default constructor for container<B> does not allocate space on the heap (or anywhere else) for an B, etc.

就我个人而言，如果它以一种良好的形式出现在标准中，我会很高兴。