什么是一个好的和稳定的C++树实现？

我想知道是否有人可以推荐一个好的C++树实现,希望有一个stl兼容,如果可能的话.

为了记录,我之前已经多次编写树算法,我知道它可以很有趣,但是如果可能的话,我想要务实和懒惰.因此,实际的工作解决方案链接就是目标.

注意:我正在寻找一个通用树,而不是平衡树或地图/集,在这种情况下,结构本身和树的连接性很重要,而不仅仅是数据.因此,每个分支都需要能够保存任意数量的数据,并且每个分支应该是可单独迭代的.

1> Roel..：

---

我不知道你的要求,但如果你对结构感兴趣而不是树特定的好处,比如速度平衡,你不会更好地使用图形(例如Boost图中的实现) ？您可以通过图形"模拟"树,也许它(概念上)更接近您正在寻找的树.

2> MvdD..：

---

看看这个.

用于C++的tree.hh库为n-ary树提供类似STL的容器类,模板化存储在节点上的数据.提供了各种类型的迭代器(下订单,预订等).在可能的情况下,访问方法与STL兼容,或者可以使用替代算法.

HTH

---

看起来不错,但它的GNU.这对树来说是一个非常沉重的代价

---

首先,这个项目不是GNU的一部分.其次,如果你谈论GPL,这不一定要支付任何代价.这取决于是否想要发布代码以及在什么条件下发布.

3> Martin York..：

---

我建议使用std :: map而不是树.

树的复杂性特征是:

插入:O(ln(n))
删除:O(ln(n))
查找:O(ln(n))

这些是std :: map保证的相同特征.
因此,大多数std :: map的实现都使用了封面下的树(红黑树)(虽然从技术上讲这不是必需的).

---

能够在单个分支上操作是整点或树.例子可能是文件系统文件夹,数据布局,场景图,语言分析,类似xml的结构化数据,可能还有很多我现在想不到的案例.

---

关于(通用)树的好处是你可以将n个子节点添加到一个分支,并将操作应用到不同的分支上,但是std :: map将所有这些都抽象出来,或者使用红黑色(子节点n = 2),将结构抽象为平面界面.