BST Stufe Traversal

Question

Ok, also versuche ich bin ein Niveau um Traversal eines binären Suchbaum zu tun und seine Arbeit nicht. Der folgende Code macht Sinn für mich, aber das ist wahrscheinlich, weil ich es war schon immer suchen und ich habe mich davon überzeugt, dass es funktionieren soll.

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); 
 } 
}

Vielleicht könnte euch darauf hinweisen, was ich falsch mache, weil, obwohl ich das Konzept eines binären Suchbaum verstehen, ich bin nicht 100% auf alle die Ins und Outs.

Answer 1

Es ist nichts falsch mit dem Ergebnis.

Können Sie erklären, wie kommen Sie auf 24,12,18?

Ich nehme an, Sie Einsatz 12 zunächst auf Root-Ebene, dann sind Sie Einsatz 24, das endet, als rechter Knoten der Wurzel bis 12 dann Sie Einsatz 18, die als linker Knoten von 24 endet - weil 18 größer ist dann Wurzel 12 so richtig abgeht, dann ist 18 weniger als 24, so wie es von den rechten Knoten 24

eingefügt wird

So:

12


12
  \
  24

12
  \
  24
 /
18

Sie haben also 3 Stufen, Stufe 1 (12), Stufe 2 (24), Stufe 3 (18) so Niveau Traversal 12,24,18 als Algorithmus eingesetzt wird.