如何在C++中创建树？

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

#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似乎正是我一直在寻找。

如果这是获得的利益一个数据结构保存任意索引类型，用于搜索优化，在插入良好然后使用地图考虑。

的地图是具有性能保证相同那些树的关联容器：对数搜索，对数插入，对数缺失，线性空间。在内部他们经常被实施为作为红黑树，尽管那不是保证。尽管如此，作为STL用户，您应该关心的是STL 算法和数据结构的性能保证。无论他们是否实施为树或小绿人不应该给你。

我不确定地图是否是我需要的，但感谢您的信息。我会记得尽可能使用地图而不是树木。

来源

2008-08-21 jeffythedragonslayer

这是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; 
     } 
     } 
    }

现在有什么不同？当涉及到将节点追加到树中时，您的实现更简单。虽然你的版本是不可思议的简单，但这个lib的开发者可能希望在不浏览树的情况下访问某些信息，例如树的大小。

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

来源

2008-08-21 02:57:14 fulmicoton

你为什么要这么做？如果这是为了学习的目的，那么你可以编写自己的树数据结构。如果这是为了获得持有任意索引类型的数据结构的优点，为搜索和优化插入进行优化，请考虑使用地图。

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

作为一个方面说明，没有这样的事情作为root（）函数。所有的STL容器都有begin（）函数实现容器的概念开始。该函数返回的迭代器的类型取决于容器的特性。

来源

2008-08-21 01:47:02 wilhelmtell

如何在C++中创建树？

回答

相关问题