Question de conception C++ sur la traversée d'arbres binaires

Question

J'ai un arbre binaire T que je voudrais copier dans un autre arbre.

Supposons que j'ai une méthode de visite qui obtient une évaluation à chaque noeud:

struct visit 
{ 
virtual void operator() (node* n)=0; 

}; 

et j'ai un algorithme de visiteur

void visitor(node* t, visit& v) 
{ 
//do a preorder traversal using stack or recursion 
if (!t) return; 
v(t); 
visitor(t->left, v); 
visitor(t->right, v); 

} 

J'ai 2 questions:

1. Je me suis installé sur l'utilisation de l'approche basée sur les foncteurs parce que je vois que le graphique boost fait cela (visiteurs du vertex). Aussi, j'ai tendance à répéter le même code pour traverser l'arbre et faire des choses différentes à chaque nœud. Est-ce un bon design pour se débarrasser du code dupliqué? Quelles autres conceptions alternatives sont là?
2. Comment l'utiliser pour créer un nouvel arbre binaire à partir d'un arbre existant? Je peux garder une pile sur le foncteur de visite si je veux, mais il est lié à l'algorithme dans le visiteur.
3. Comment est-ce que j'incorporerais des traversées d'ordre postérieur ici? Une autre classe de foncteurs?

Answer 1

1. Sous le visiteur et fournir différents visiteurs pour chaque tâche individuelle, et fusionner comme des tâches (ou connexes) dans le même visiteur. La meilleure approche dépend fortement de ce que vous essayez de faire.
2. Un visiteur peut construire un arbre différent. En visitant les nœuds, il construit les nouvelles copies de nœuds et les lie dans l'ordre "correct".
3. Vous réécrivez l'ordre dans lequel les nœuds sont visités.

Un visiteur est une technique. Il semble que vous ayez confondu la technique avec une solution particulière. L'utilisation d'un visiteur signifie que certains services de navigation sont fournis par la structure de données qui communiquera avec un objet externe (le visiteur) par rappel.

Answer 2

3: Créer une méthode supplémentaire pour chaque type de parcours que vous voulez faire et réorganiser les appels visiteur:

void preorder_visitor(node* t, visit& v) 
{ 
if (!t) return; 
v(t); 
visitor(t->left, v); 
visitor(t->right, v); 
} 

void postorder_visitor(node* t, visit& v) 
{ 
if (!t) return; 
visitor(t->left, v); 
visitor(t->right, v); 
v(t); 
}