itérations d'arbre C++

Question

Recherche d'exemples sur des itérations d'arbre simples en C++, à la fois récursives et itératives. (post, pre et in-order)

Answer 1

This page montre un exemple d'arbre binaire et comment l'itérer.

Answer 2

La bibliothèque Adobe Source Library adobe::forest<T> est un conteneur générique pouvant être itéré en amont ou en aval. La documentation contient des exemples d'exécution de ces différents types d'itérations.

Answer 3

si votre arbre ressemble à ceci:

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

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

alors c'est la façon dont vous faites une récursive en ordre itération:

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

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

Si vous changez les lignes avec n> gauche et n -> à droite l'arbre sera itéré dans l'ordre inverse.

Ce sont les pré-commande et itérations post-ordre:

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 
} 

L'itération non récurrent est un peu plus compliqué. La première chose dont vous avez besoin est de trouver un premier noeud dans l'arbre (comme vector<T>::begin())

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

Ensuite, vous avez besoin d'un moyen d'obtenir l'élément suivant de l'arbre (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; 
} 

(cette fonction essaie de trouver un premier noeud dans le sous-arbre droit et si ce n'est pas possible, monte l'arbre jusqu'à ce que le chemin vient du sous-arbre à droite)