c++ - 如何在C++中制作一棵树？

Question

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

#include <iostream>
#include <tree>
using namespace std;

int main()
{
    tree<int> myTree;

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

    tree<int>::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 似乎正是我要找的。

If this is for gaining the benefit of a data-structure holding arbitrary index types, optimized for searching and good at insertion then consider using a map.

A map is an associative container that has performance guarantees identical to those of a tree: logarithmic searching, logarithmic insertion, logarithmic deletion, linear space. Internally they are often implemented as red-black trees, although that is not a guarantee. Still, as an STL user all you should care about is the performance guarantees of the STL algorithms and data-structures. Whether they're implemented as trees or little green men shouldn't matter to you.

我不确定 map 是否是我所需要的，但感谢您提供的信息。我会记得尽可能使用 map 而不是实现树。

Answer 1

这里是 tree.hh这有点接近你想做的，虽然有点不同。

这是从其网站上提取的一段代码。

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::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<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i) 
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

现在有什么不同？您的实现更简单将一个节点添加到树中。尽管您的版本明显更简单，但此库的开发人员可能希望无需浏览树即可访问一些信息，例如树的大小。

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