Отображение нулевых детей бинарного дерева на выходе

Question

У меня есть метод, который печатает уровни бинарного дерева:

template<class BTNode> 
void breadthfirstByLevel(BTNode* node_ptr) { 
if (node_ptr == NULL) 
{ 
    return; 
} 
    queue<BTNode *> q1; 
    queue<BTNode *> q2; 

    q1.push(node_ptr); 

    while (!q1.empty() || !q2.empty()) { 
     while (!q1.empty()) 
     { 
      node_ptr = q1.front(); 
      q1.pop(); 
      cout << node_ptr->data() << " "; 
      if (node_ptr->left() != NULL) 
      { 
       q2.push(node_ptr->left()); 
      } 

      if (node_ptr->right() != NULL) 
      { 
       q2.push(node_ptr->right()); 
      } 
     } 
      cout << endl; 
      while (!q2.empty()) 
      { 
       node_ptr = q2.front(); 
       q2.pop(); 
       cout << node_ptr->data() << " "; 

       if (node_ptr->left() != NULL) 
       { 
        q1.push(node_ptr->left()); 
       } 
       if (node_ptr->right() != NULL) 
       { 
        q1.push(node_ptr->right()); 
       } 
      } 
     cout << endl; 
    } 
    } 

я проверяю для детей текущего узла быть нулевыми и толкать их в очередь. Как я могу отобразить «NULL» на выходном уровне, а не просто пропускать его и ничего не печатать?

Answer 1

Вы берете указатель следующего узла из очереди для печати данных. Если этот узел имеет дочерние элементы (т. Е. Указатель на дочерний элемент не равно null), вы помещаете их в очередь. Это означает, что в очереди у вас никогда не будет nullptr.

Вы можете решить это, используя вариант алгоритма: вы можете поместить nullptr в очередь в отсутствие дочернего элемента. Но тогда вам нужно убедиться, когда вы получите указатели из очереди, чтобы не разыменовать их.

... 
while (!q1.empty() || !q2.empty()) { 
    while (!q1.empty()) 
    { 
     node_ptr = q1.front(); 
     q1.pop(); 
     if (node_ptr==nullptr) { // if nullptr was on queue 
      cout << "<NULL> ";  // tell it 
     } 
     else {      // otherwise handle data and queue its children 
      cout << node_ptr->data() << " "; 
      q2.push(node_ptr->left()); // push even if it's nullptr 
      q2.push(node_ptr->right()); //  "   " 
     } 
    } 
    ... // then same for q2 
}