BST Nivel Transversal

Question

Ok, así que estoy tratando de hacer un recorrido en orden de nivel de un árbol de búsqueda binario y no su trabajo. El código de abajo tiene sentido para mí, pero eso es probablemente porque he estado buscando en ella para siempre y me he convencido de que se debe trabajar.

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

Tal vez ustedes podrían señalar lo que estoy haciendo, porque mal, aunque entiendo el concepto de un árbol de búsqueda binaria, no estoy 100% en todas las entradas y salidas.

Answer 1

No hay nada malo con el resultado.

Puede explicar cómo se llega a 24,12,18?

Usted asume inserto 12 en primer lugar a nivel de la raíz, entonces inserto 24 que termina como nodo de la derecha de la raíz 12, entonces inserto 18, que termina como nodo izquierdo de 24 - porque 18 es más grande que la raíz 12 así que ir a la derecha, entonces 18 es menos de 24 por lo que se inserta como nodo derecho de 24

Así que:

12


12
  \
  24

12
  \
  24
 /
18

Así que hay 3 niveles, nivel 1 (12), nivel 2 (24), nivel 3 (18) por lo que el nivel transversal 12,24,18 como su algoritmo es la inserción.