Обход уровня 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 по мере добавления вашего алгоритма.