爲什麼我的printLevel函數不工作？

Question

我寫過這段代碼來完成二叉搜索樹的順序遍歷。錯誤僅在printLevel函數中，因爲所有其他函數都正常工作。

#include <queue> 
using namespace std; 
struct node{ 
int data; 
struct node* left; 
struct node* right; 
}; 

struct node* newNode(int data){ 
struct node* node = new (struct node); 
node->data=data; 
node->left=NULL; 
node->right=NULL; 
return (node); 
}; 
struct node* insert (struct node* node, int data){ 
if (node==NULL){ 
    return (newNode(data)); 
} 
else { 
    if (data<=node->data) node-> left=insert(node->left,data); 
    else node->right=insert(node->right,data); 
    return (node); 
} 

} 

void printLevel(struct node* node){ 
    queue<struct node*> q; 
    while(node!=NULL){ 
     cout << node->data << " "; 
     q.push(node->left); 
     q.push(node->right); 
     node=q.front(); 
    } 
} 
int main(){ 
    int n; 
    cin >>n; 
    int m; 
    cin >>m; 
    struct node* root=newNode(m); 
    for (int i=0;i<n-1;i++){ 
     cin>>m; 
     insert(root,m); 
    } 
    printLevel(root); 
// printPostOrder(root); 
// cout <<maxDepth(root); 
// debug(maxDepth(root), minValue(root), printTree(root)); 
    //struct node* root=build123(); 
} 

這裏是算法：（http://www.geeksforgeeks.org/level-order-tree-traversal/）

printLevelorder（樹）

1）創建一個空隊列q

2）temp_node =根/ 從根開始/

3）當temp_node不爲NULL時迴路

a) print temp_node->data. 

b) Enqueue temp_node’s children (first left then right children) to q 

c) Dequeue a node from q and assign it’s value to temp_node 

我正在爲7個節點輸入3,1,4,2,7,6,5。它陷入無限循環。我還實施以下根據另一種方法，兩個功能，它是工作的罰款：

void levelOrder(struct node* node, int level){ 
    if (node==NULL){ 
     return; 
    } 
    if (level==1){ 
     cout << node->data; 
    } 
    else if (level>1){ 
     levelOrder(node->left,level-1); 
     levelOrder(node->right,level-1); 

    } 
} 
void printLevelOrder(struct node* root){ 
    for (int i=1;i<=maxDepth(root);i++){ 
     levelOrder(root,i); 
    } 
} 

它是O（n^2），但高於一個爲O（n）。我的代碼有什麼問題？謝謝。

Answer 1

我懷疑你的循環終止是錯誤的。

而不是node != NULL，你應該檢查，看看!q.empty()。

此外，呼叫q.front不會從隊列中刪除元素;要做到這一點，您需要pop（撥打front後）。

此代碼的工作對我來說：

void printLevel(struct node* node){ 
    std::queue<struct node*> q; 
    q.push(node); 
    while(!q.empty()) { 
     node=q.front(); 
     q.pop(); 
     if (node != NULL) { 
      std::cout << node->data << " "; 
      q.push(node->left); 
      q.push(node->right); 
      } 
    } 
}