Прохождение уровня BST

Question

Итак, я пытаюсь сделать обход уровня бинарного дерева поиска, и он не работает. Приведенный ниже код имеет смысл для меня, но это, вероятно, потому, что я смотрел на него вечно и убедил себя, что он должен работать.

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

Возможно, вы, ребята, могли бы указать на то, что я делаю неправильно, потому что, хотя я понимаю концепцию бинарного дерева поиска, я не на 100% на всех входах и выходах.

Answer 1

Нет ничего плохого в результате.

Можете ли вы объяснить, как вы прибываете в 24,12,18?

Я предполагаю, что вы сначала вставляете 12 на уровне корня, затем вставляете 24, который заканчивается как правый узел корня 12, затем вы вставляете 18, который заканчивается как левый узел 24 - потому что 18 больше, чем корень 12, так что вправо, тогда 18 меньше 24, поэтому он вставляется как правый узел 24

Так:

12


12
  \
  24

12
  \
  24
 /
18

Таким образом, у вас есть 3 уровня, уровень 1 (12), уровень 2 (24), уровень 3 (18), поэтому обход уровня 12,24,18 по мере вставки вашего алгоритма.