0

私は次のようなノードクラスを使用してC++でツリー構造を実装しています。

class Node {
protected:
    // relations
    Node *_parent;
    std::vector<Node*> _children;

public:
    // some example method 
    void someMethod(Node *node) {

        // do something with *node

        for (int i = 0; i < node->_children; i++) {
            _children[i]->myFunction;
        }
    }
}

ここで、ツリー内のノードで作業するためsomeMethodに、例のように再帰関数を実装しています。

それは機能しますが、ツリーで機能する新しい関数ごとに同じ再帰コードを何度も書くことになります。

プレーン配列の場合のようにツリー構造を反復する一般的な方法はありますか？ブランチ全体が完了するまで、次のオブジェクトを返すメソッド。

編集：

これまでコメントしてくださった皆様、ありがとうございました。あなたの助けを借りて、問題を絞り込むことができました。私の理解から（私はc ++を初めて使用します）、ツリーをトラバースするためのコードをカプセル化するイテレータークラスが必要です。

すべてのツリーメンバーへのアクセスは、次のように簡単にする必要があります。

for (Node<Node*>::iterator it = _node.begin(); it != _node.end(); ++it) {
    Node *node = *it;
    // do something with *node
}

今の質問は：

このようなイテレータを実装するにはどうすればよいですか？

4

2 に答える 2

1

探しているノードを返す再帰関数に関数ポインターを渡します。

これが、C/C++ における関数ポインターと関数ポインター配列の威力です。

于 2013-02-10T14:22:52.290 に答える
0

多くの関数は、単純にすべてのノードを反復処理するわけではありません。ツリーが (通常は) ソートされている場合、最大値を見つけるには、右側のサブツリーのみを調べます。

最小値を検索すると、それは一番左のサブツリーにあります。

したがって、ツリー全体を反復するイテレータを使用することが常に意味があるとは限りません。
ただし、すべてのノードを正確に反復処理する必要がある場合は、関数ポインターまたはビジター パターン (Erich Gamma、デザイン パターン) を使用できます。

于 2013-02-10T14:29:22.637 に答える