Прохождение уровня BST - PullRequest
Новая
       67

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

2 голосов
/ 03 мая 2010

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

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% во всех входах и выходах.

1 Ответ

1 голос
/ 03 мая 2010

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

Можете ли вы объяснить, как вы пришли к 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 при вставке вашего алгоритма.

...