BST Niveau Traversal

Question

Ok, donc je suis en train de faire une commande de niveau, de l'arbre de recherche binaire et sa ne fonctionne pas. Le code ci-dessous me semble logique, mais qui est probablement parce que je l'ai regardé pour toujours et je me suis convaincu que cela devrait fonctionner.

void BST<T>::levelByLevel(ostream &out) { 
 Queue<BinNodePointer> q; 
 BinNodePointer subtreeRoot; 

 if(myRoot == NULL) 
  return; 
 q.enqueue(myRoot); 
 while(!q.empty()) {
  subtreeRoot = q.front(); 
  out << subtreeRoot->data << " "; 
  q.dequeue(); 

  if(subtreeRoot->left != NULL) 
   q.enqueue(subtreeRoot->left); 
  if(subtreeRoot->right != NULL) 
   q.enqueue(subtreeRoot->right); 
 } 
}

Peut-être que vous avez pu remarquer ce que je fais mal parce que, même si je comprends le concept d'un arbre de recherche binaire, je ne suis pas à 100% sur tous les tenants et les aboutissants.

Answer 1

Il est faux rien du résultat.

Pouvez-vous expliquer comment vous arrivez à 24,12,18?

Je suppose que vous insérer 12 d'abord au niveau de la racine, puis vous insérez 24 qui se termine comme nœud droite de la racine 12 puis vous insérez 18 qui se termine comme noeud gauche de 24 - parce que 18 est plus grande que la racine 12 afin d'aller à droite, puis 18 est inférieur à 24, de sorte qu'il est inséré en tant que noeud de droite 24

12


12
  \
  24

12
  \
  24
 /
18

Vous avez donc 3 niveaux, niveau 1 (12), niveau 2 (24), niveau 3 (18), de sorte que le niveau traversal 12,24,18 votre algorithme est insérait.