如何在C中制作树？

发布时间：2020-12-16 03:44:35 所属栏目：百科来源：网络整理

导读：如何在C中创建使用迭代器而不是指针的树数据结构？我在STL中找不到可以做到这一点的任何东西.我想做的是能够像这样创建和操作树： #include iostream#include treeusing namespace std;int main(){ treeint myTree; treeint::iterator i = myTree.root(); *i

如何在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 rootn";

    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.

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

解决方法

这是 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的开发者可能想要在不浏览树的情况下访问一些信息,例如树的大小.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!