如何用C++创建一个树？

如何在C++中创建使用迭代器而不是指针的树数据结构？我在STL中找不到可以做到这一点的任何东西.我想做的是能够像这样创建和操作树:

#include 
#include 
using namespace std;

int main()
{
    tree myTree;

    tree::iterator i = myTree.root();
    *i = 42;

    tree::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";

    return 0;
}

谢谢你,tree.hh似乎正是我想要的.

如果这是为了获得保存任意索引类型的数据结构的好处,优化搜索和擅长插入,那么考虑使用映射.

映射是一个关联容器,其性能保证与树的性能保证相同:对数搜索,对数插入,对数删除,线性空间.在内部,它们通常被实施为红黑树,尽管这不是保证.尽管如此,作为STL用户,您应该关心的是STL算法和数据结构的性能保证.无论他们是以树木还是小绿人实施,都不应该对你有用.

我不确定地图是否是我需要的,但感谢您的信息.我会记得尽可能使用地图而不是实现树.

这是tree.hh ,它有点接近你想要做的,虽然有点不同.

这是从其网站中提取的一段代码.

int main(int, char **)
   {
   tree tr;
   tree::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree::iterator sib2=tr.begin(loc);
      tree::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i

现在有什么不同？在将节点附加到树时,您的实现更简单.虽然你的版本简单易懂,但是这个lib的开发者可能想要在不浏览树的情况下访问一些信息,例如树的大小.

我还假设他不希望出于性能原因将根存储在所有节点上.因此,如果你想按照自己的方式实现它,我建议你保留大部分逻辑并将链接添加到迭代器中的父树,并重写一点.