c++ - 逐级遍历树找出层次

Question

我想知道如何找出每个节点所在的级别。但我想不通。

这是部分代码，但我必须修改它。

if(root == NULL)
return;
q.enqueue(root);
while(!queue.empty()){
 queue.dequeue(cur);
 if( cur != NULL){
   cout<<cur->data<<" ";
   if(cur->left != NULL)
   queue.enqueue(cur->left);
   if(cur->right != NULL)
   queue.enqueue(cur->right);
  }
}

如何修改代码，让我知道每个节点的级别？希望大家能给我一些关于这个问题的算法。

Answer 1

您正在以正确的方向进行水平顺序遍历。如果你需要打印你在哪个级别:

if(root == NULL)  
   return;  
int level = 1;  
q.enqueue(root);  
q.enqueue(NULL);    
while(!queue.empty()){  
 queue.dequeue(cur);  
 if(cur == NULL){  
    //going to next level  
    level++;      
    if(queue.empty()){  
       break;  
    }  
    queue.enqueue(NULL);  
 }    
 else {  
   cout << "LEVEL is: " << level;  
   cout<<cur->data<<" ";
   if(cur->left != NULL){
      queue.enqueue(cur->left);  
   }  
   if(cur->right != NULL){  
      queue.enqueue(cur->right);  
   }  
 }    
}