0

これまで、ツリー データ構造について多くの質問をしてきましたが、C++ での正しい方法を理解していなかったようです。

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

現在、私のツリー構造の目標は次のとおりです。1) ブランチを 1 つのツリーから別のツリーにできるだけ早く移動します。2) 各ブランチはそれ自体がツリーである必要があります。また、ツリーで動作するアクションは、ブランチでも実行できる必要があります。

私が行ったことは、ベクトルを含むクラスを作成するだけです。- ベクター内には、このクラスの他のオブジェクトがあります。例 (現在直面している最大の問題は、クラスが大きすぎて処理できないことであるため、ここでは最小限の例のみを投稿しています):

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

これでわかるように、何かを取り出しsubtreesて、ツリーとして使用するか、コピーすることができます。ただし、最上位ツリーにはサブツリーの数 (またはレベルの数) が示されていないため、「終了反復子」を述べるのは不可能ですか? std::find() のようなアルゴリズムは、ツリー全体 (およびそのすべてのサブツリー) を反復処理しませんか?

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

4

2 に答える 2

1

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

end()このベクトルの反復子は、単に空のスタックになります。

于 2012-01-17T15:07:46.943 に答える
0

これでわかるように、サブツリーから何かを取り出して、それをツリーとして使用するか、コピーすることができます。ただし、最上位ツリーにはサブツリーの数 (またはレベルの数) が示されていないため、「終了反復子」を述べるのは不可能ですか? 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)この知識を使用して、ツリー内の子の数をカウントするアルゴリズムを簡単に作成できます。

ツリーは、再帰アクセス用に設計されています。非再帰的なアクセスが必要な場合、探しているのはツリーではないでしょうか? - この構造体は、どのようなアクセス頻度で、どのようなデータを保持しますか?

于 2012-01-17T15:22:43.970 に答える