ツリーデータ構造の作成 - 別のアプローチ

Question

渡された私は木のデータ構造について多くの質問をしましたが、C++で正しい方法にしなかったようです。

私がデータ構造を書いたやり方では、「終了」または「開始」イテレータを持つ方法について単一のやり方を考えることができませんでした。私はすべての機能をメンバーメソッドとして取り入れるというアプローチに移りました。代わりにイテレータの標準的なアプローチを使用する代わりに&アルゴリズム。

私のツリー構造の目標は、1）できるだけ早く1つのツリーから別のツリーへブランチを移動させることです。 2）各ブランチはそれ自身のツリーでなければなりません。また、ツリー上で動作するアクションも、ブランチ上で実行できる必要があります。

私が行ったことは、単純にベクトルを含むクラスを作成することです。 - ベクトルの内部には、このクラスの他のオブジェクトがあります。例（私が今直面している最大の問題は、クラスが単純に扱うには大きすぎるということであると私は、ここでは最小限の例を掲載しています）：

template <typename ValTy> 
class Tree { 
private: 
    std::vector<std::unique_ptr<Tree> > subtrees; 
    ValTy value; 
}; 

あなたは、私はちょうど何かを取り出すことができるこれを見ることができるようにsubtrees - それをツリーとして使うか、それをコピーしてください。 トップレベルのツリーには、いくつのサブツリー（またはいくつのレベル）があるかについての情報がないので、「終了イテレータ」を記述することは不可能ですか？そして、std :: find（）のようなアルゴリズムは、ツリー全体（およびすべてのサブツリー）に対して反復処理を行いませんか？

簡単な「分岐」構造を維持しながら、これらのアルゴリズムを使用することは可能ですか？

Answer 1

サブツリーベクトルのイテレーターのペアのスタックを保持することで、このようなツリーを反復処理できます。そのようなベクトルの増分は、最上位のサブツリーイテレータの増分を意味し、最下位のイテレータがその最後にある場合はクリーンアップが続きます。

end()このベクトルのイテレータは、単に空のスタックになります。

Answer 2

これでわかるように、サブツリーから何かを取り出して、 をツリーとして使用したり、コピーしたりすることができます。しかし、上部の レベルツリーには、いくつのサブツリー（またはいくつのレベルが何個あるか）が表示されていないので、「終了イテレータ」を記述することは不可能ですか？そして、 のようなアルゴリズムは、std :: find（）のように、ツリー全体を反復処理しません。 （そしてそのすべてがサブツリーです）？

ここでの問題は概念的な問題です。

私は、再帰を伴うツリー構造内で常にCRUDの機能を解決します。再帰はサブツリーの数を知る必要はなく、これはO(log n)の挿入、検索、および削除を可能にするものの1つです。

挿入例：

void insertNode(Node* &treeNode, Node *newNode) { 
    if (treeNode) treeNode = newNode; 
    else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode); 
    else insertNode(treeNode->right, newNode); 
} 

あなただけのNULLまで、左の子を行く木の上にあるどのように多くのレベルを知る必要がある場合。この知識を使用して、ツリー内の子どもの数を数えるのに、O(log n)アルゴリズムを簡単に試すことができます。

---

ツリーは再帰アクセス用に設計されています。非再帰的なアクセスが必要な場合、おそらくツリーはあなたが探しているものではありませんか？どのアクセス頻度でこの構造が保持するデータは？