为什么c++ STL不提供任何“树”容器，用什么代替最好?
我想将对象的层次结构存储为树，而不是使用树来增强性能……
当前回答
使用树有两个原因:
你想用树形结构来镜像问题: 为此我们有boost图形库
或者您想要一个具有树形访问特征的容器 我们有
Std::map(和Std::multimap) Std::set(和Std::multiset)
基本上，这两个容器的特点是，它们实际上必须使用树来实现(尽管这实际上不是一个要求)。
还有这个问题: C树实现
其他回答
我认为没有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.
就我个人而言，如果它以一种良好的形式出现在标准中，我会很高兴。
如果您正在寻找一个rb树实现，那么stl_tree.h可能也适合您。
这一个看起来很有前途，似乎是你正在寻找的: http://tree.phi-sci.com/
在我看来，这是个疏忽。但是我认为有很好的理由不在STL中包含Tree结构。维护树有很多逻辑，最好将树作为成员函数编写到基本TreeNode对象中。当TreeNode被封装在STL头中时，它会变得更加混乱。
例如:
template <typename T>
struct TreeNode
{
T* DATA ; // data of type T to be stored at this TreeNode
vector< TreeNode<T>* > children ;
// insertion logic for if an insert is asked of me.
// may append to children, or may pass off to one of the child nodes
void insert( T* newData ) ;
} ;
template <typename T>
struct Tree
{
TreeNode<T>* root;
// TREE LEVEL functions
void clear() { delete root ; root=0; }
void insert( T* data ) { if(root)root->insert(data); }
} ;
可能与boost中没有树容器的原因相同。有许多方法可以实现这样的容器，没有一种好方法可以满足所有使用它的人。
需要考虑的一些问题:
节点的子节点数是固定的还是可变的? 每个节点的开销是多少?-即，你需要父指针，兄弟指针等。 提供什么算法?-不同的迭代器，搜索算法等。
最后的问题是，一个对所有人都足够有用的树容器，会因为太过重量级而无法满足大多数使用它的人。如果您正在寻找功能强大的东西，Boost Graph Library本质上是树库的超集。
下面是其他一些通用树的实现:
卡斯珀·彼得斯的树 Adobe的森林 核心:树
