BFS en arbre binary

J’essaie d’écrire les codes pour une recherche en largeur d’abord dans un arbre binary. J’ai stocké toutes les données dans une queue, mais je n’arrive pas à comprendre comment accéder à tous les nœuds et consumr tous leurs enfants.

Voici mon code en C:

void breadthFirstSearch (btree *bt, queue **q) { if (bt != NULL) { //store the data to queue if there is if (bt->left != NULL) enqueue (q, bt->left->data); if (bt->right != NULL) enqueue (q, bt->right->data); //recursive if (bt->left != NULL) breadthFirstSearch (bt->left, q); if (bt->right != NULL) breadthFirstSearch (bt->right, q); } } 

J’ai déjà mis en queue les données racine, mais cela ne fonctionne toujours pas. Quelqu’un peut-il signaler mon erreur?

Un BFS peut être facilement écrit sans récursivité. Utilisez simplement une queue pour commander vos extensions:

 void BFS(btree *start) { std::deque q; q.push_back(start); while (q.size() != 0) { btree *next = q.front(); // you may want to print the current node here or do other processing q.pop_front(); if (next->left) q.push_back(next->left); if (next->right) q.push_back(next->right); } } 

La clé est qu’il n’est pas nécessaire de parcourir l’arbre de manière récursive; vous laissez simplement votre structure de données gérer l’ordre dans lequel vous visitez les nœuds.

Notez que j’utilise le deque C ++ ici, mais tout ce qui vous permet de placer des éléments à l’arrière et de les obtenir de l’avant fonctionnera correctement.

 void bfs_bintree (btree_t *head) { queue_t *q; btree_t *temp; q = queue_allocate (); queue_insert (q, head); while (!queue_is_empty (q)) { temp = queue_remove (q); if (temp->left) queue_insert (temp->left); if (temp->right) queue_insert (temp->right); } queue_free (q); return; } 

Le nœud principal est d’abord inséré dans la queue. La boucle va itérer tant que la queue n’est pas vide. À partir du nœud principal, à chaque itération, un nœud est supprimé et les enfants non nuls sont insérés dans la queue. À chaque itération, un nœud sort et ses enfants non nuls sont poussés. Lors de la prochaine itération, le prochain sumt découvert le plus ancien, qui se trouve maintenant au début de la queue, est extrait (dans l’ordre dans lequel ils ont été découverts), puis il est traité pour vérifier son enfant.

  A / \ / \ BC / \ \ / \ \ DEF / \ / \ / \ / \ GHIJ iteration Vertex Selection Discovery Queue State initial : A 1 A : BC {A is removed and its children inserted} 2 B : CDE {B is removed and its only child inserted} 3 C : DEF {C is removed and its children inserted} 4 D : EFGH {D is removed and its children inserted} 5 E : FGH {E is removed and has not children} 6 F : GHIJ {F is removed and its children inserted} 7 G : HIJ {G is removed has no children} 8 H : IJ {H is removed has no children} 9 I : J {I is removed has no children} 10 J : (empty) {J is removed has no children} 

Au-dessus de l’itération s’arrête lorsque nous constatons qu’il n’y a plus de sumt découvert en attente de sélection dans la queue, de sorte que tous les sumts découverts dans l’arborescence binary (composant connecté au graphe) sont sélectionnés.

Dans un premier temps, votre code vous permet de mettre en queue les noeuds de la queue, puis de les parcourir à nouveau de manière récursive, ce qui crée un modèle DFS. Si vous devez faire de la récursivité, vous devez vérifier si la queue est vide en tant que condition de base. Vérifiez également que vous passez la queue. Je pense que cela peut être incorrect. Je suggérerais une solution itérative.

Vous ne faites pas une première traversée large ici. Au lieu de cela, vous mettez en queue les éléments gauche et droit dans la queue et passez à la sous-arborescence gauche. Vous épuisez d’abord le sous-arbre de gauche, puis passez au sous-arbre de droite.

Ecrivez une procédure pour mettre le nœud en queue.

 void breadthFirstSearch (btree *bt, queue **q) { btree *tmpNode; enqueue(q,bt); //Assuming your root node has data while (!isempty(q)) //Assume isempty returns false when queue is not empty { tmpNode = dequeue(q); //Do whatever you want to do with tmpNode->data enqueue(tmpNode->left); enqueue(tmpNode->right); /* If this is a acyclic graph(tree) then this procedure should do, else you have to mark the nodes you have visited in-order not to end in a cycle */ } } int main() { breadthFirstSearch(bt,q) return 0 }