C++ でツリーを作成するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/19193

  •  09-06-2019
  •  | 
  •  

質問

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 はまさに私が探していたもののようです。

もし、これが、「ヴェルディ・ワールドカップ」の利益を得るためのものであるなら 任意の 検索に最適化されたインデックスタイプ 挿入が得意な場合は、次のように考える。 地図を使って。

マップは、次のような連想コンテナです。 同じ性能保証がある を木のものに置き換えた：対数的 検索、対数挿入、 対数削除、線形空間。内部的には、以下のように実装されることが多い。 赤黒い木として 保証するものではない。それでもSTLユーザーとして を気にする必要がある。 STLの性能保証 アルゴリズムとデータ構造。ツリーとして実装されるかどうか リトル・グリーン・マンも関係ない あなたに

地図が必要かどうかわかりませんが、情報ありがとうございます。ツリーを実装する代わりに、可能な限りマップを使用することを忘れないでください。

役に立ちましたか？

解決

ここは 木.hh これはあなたのやりたいことに少し近い。 違う。

以下は、Web サイトから抜粋したコードの一部です。

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

さて、何が違うのでしょうか？に関しては、実装はよりシンプルになる。 ツリーにノードを追加する。あなたのバージョンは議論の余地なく単純ですが、このライブラリの開発者はおそらくツリーを参照せずに、たとえばツリーのサイズなどの情報にアクセスできるようにしたいと考えていました。

また、パフォーマンス上の理由から、すべてのノードにルートを保存したくなかったのだと思います。したがって、独自の方法で実装したい場合は、ロジックの大部分を保持し、イテレータ内の親ツリーへのリンクを追加し、追加を少し書き直すことをお勧めします。

他のヒント

なぜそれをしたいのですか？これが学習目的の場合は、独自のツリー データ構造を作成できます。任意のインデックス タイプを保持し、検索用に最適化され、挿入が得意なデータ構造の利点を得ることが目的の場合は、マップの使用を検討してください。

マップは、ツリーと同様のパフォーマンス保証を持つ連想コンテナです。対数検索、対数挿入、対数削除、線形空間。内部的には赤黒ツリーとして実装されることがよくありますが、それが保証されるわけではありません。それでも、STL ユーザーが気にすべきことは、STL アルゴリズムとデータ構造のパフォーマンス保証だけです。それらが木として実装されているか、小さな緑色の人として実装されているかは、あなたにとっては重要ではありません。

余談ですが、root() 関数のようなものはありません。すべての STL コンテナには、コンテナの概念的な開始を実装する begin() 関数があります。その関数によって返されるイテレータの種類は、コンテナの特性によって異なります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top