c++ - ツリーの反復 C++

Question

再帰的および反復的な C++ での単純なツリー反復の例を探しています。（ポスト、プレ、インオーダー）

Answer 1

ツリーが次のようになっている場合：

struct Node{
    Node *left, *right, *parent;

    int value; // or some other important data :-)
}

次に、これが再帰的な順序どおりの反復を行う方法です。

void iterate(Node *n){
    if(!n)
        return;

    iterate(n->left);
    cout << n->value; // do something with the value
    iterate(n->right);
}

行をn->leftとn->rightで入れ替えると、ツリーは逆の順序で繰り返されます。

これらは、プレオーダーとポストオーダーの反復です。

void iterate_pre(Node *n){
    if(!n)
        return;

    cout << n->value; // do something with the value
    iterate_pre(n->left);
    iterate_pre(n->right);
}

void iterate_post(Node *n){
    if(!n)
        return;

    iterate_post(n->left);
    iterate_post(n->right);
    cout << n->value; // do something with the value
}

非再帰的な反復はもう少し複雑です。最初に必要なのは、ツリーの最初のノードを見つけることです（のようにvector<T>::begin()）

Node *find_first(Node *tree){
    Node *tmp;
    while(tree){
        tmp = tree;
        tree = tree->left
    }
    return tmp;
}

次に、ツリーの次のアイテムを取得する方法が必要です（vector<T>::iterator::operator++()）。

Node *next(Node *n){
    assert(n);

    if(n->right)
        return find_first(n->right)

    while(n->parent && n->parent->right == n)
        n = n->parent;

    if(!n->parent)
        return NULL;

    return n;
}

（この関数は、右側のサブツリーで最初のノードを見つけようとします。それが不可能な場合は、パスが右側のサブツリーから来るまでツリーを上に移動します）

Answer 2

このページでは、バイナリ ツリーの例と、それを反復処理する方法を示します。

Answer 3

Adobe Source Libraryadobe::forest<T>は、ポストプレまたはインオーダーで反復できる汎用ツリー コンテナです。ドキュメントには、これらのさまざまなタイプの反復を実行する方法の例があります。