顯示二叉樹的空兒輸出

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

您從隊列中取下一個節點的指針來打印數據。如果此節點有子節點（即指向子節點的指針不爲空），則將它們放入隊列中。這意味着在隊列中你永遠不會有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 
}