C ++でツリーを作るには?

How to make a tree in C++?

出典: link タグ:c++treeiterator 更新時間:

  問題

ポインタの代わりにイテレータを使用する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
";

    return 0;
}

ありがとう、tree.hhは私が探していたもののようです。

これが利益を得るためなら 任意のデータ構造 検索に最適化されたインデックス型 挿入が得意な場合は、 地図を使って。

マップは、 パフォーマンスは ツリーのものへ:対数 検索、対数挿入、 対数削除、線形空間。 内部的には 赤黒の木として、それは 保証ではありません。それでも、STLユーザーとして あなたが気にするのは STLのパフォーマンス保証 アルゴリズムとデータ構造 木として実装されているかどうか 小さな緑色の男性は関係ありません あなたに

私は地図が私が必要とするものかどうかはわかりませんが、情報に感謝します。私は木を実装するのではなく、可能な限りマップを使用することを覚えています。

  ベストアンサー

ここに 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の開発者はおそらく、ツリーのサイズなど、ツリーを閲覧せずにいくつかの情報にアクセスできるようにしたいと考えていました。

私はまた、彼がパフォーマンス上の理由からすべてのノードにルートを格納したくなかったと仮定します。 だからあなたのやり方でそれを実装したい場合は、ほとんどのロジックを保持し、イテレータの親ツリーへのリンクを追加し、少し書き換えることをお勧めします。

  同じタグがついた質問を見る

c++treeiterator
前へ:
次へ: