Recorrido de orden de nivel de un árbol binario

Question

void traverse(Node* root) 
{ 
    queue<Node*> q; 

    Node* temp_node= root; 

    while(temp_node) 
    { 
     cout<<temp_node->value<<endl; 

     if(temp_node->left) 
      q.push(temp_node->left); 

     if(temp_node->right) 
      q.push(temp_node->right); 

     if(!q.empty()) 
     { 
      temp_node = q.front(); 
      q.pop(); 
     } 
     else 
      temp_node = NULL; 
    } 
} 

El código publicado anteriormente es mi código de cruce de orden de nivel. Este código funciona bien para mí, pero una cosa que no me gusta es que estoy inicializando explícitamente temp_node = NULL o uso Break. Pero no parece ser un buen código para mí.

¿Existe una clara implementación de esto o cómo puedo mejorar este código?

Answer 1

void traverse(Node* root) 
{ 
    queue<Node*> q; 

    if (root) { 
     q.push(root); 
    } 
    while (!q.empty()) 
    { 
     const Node * const temp_node = q.front(); 
     q.pop(); 
     cout<<temp_node->value<<"\n"; 

     if (temp_node->left) { 
      q.push(temp_node->left); 
     } 
     if (temp_node->right) { 
      q.push(temp_node->right); 
     } 
    } 
} 

No hay más casos especiales. Y la sangría se limpia para que pueda entenderse más fácilmente.

Alternativamente:

hecho hasta como un bucle for. Personalmente, me gusta la variable extra. El nombre de la variable es una taquigrafía más agradable que decir 'q.front() `todo el tiempo.

Answer 2

Probar:

void traverse(Node* root) 
{ 
    queue<Node*> q; 
    q.push(root); 

    while(!q.empty()) 
    { 
     Node* temp_node = q.front(); 
     q.pop(); 
     if (temp_node == NULL) 
     { continue; 
     } 

     cout << temp_node->value << endl; 

     q.push(temp_node->left); 
     q.push(temp_node->right); 
    } 
} 

Answer 3

Un problema serio con su código existente es que se bloquea cuando se le llama en un árbol vacío (root = NULL).

Debe decidir si desea tener NULL punteros en la cola o no.

Si no es así, solo puede poner en cola valores que no sean NULL.

void traverse(Node* root) { 
    queue<Node*> q; 

    // no tree no level order. 
    if(root == NULL) { 
     return; 
    } 

    // push the root to start with as we know it is not NULL. 
    q.push(root); 

    // loop till there are nodes in the queue. 
    while(!q.empty()) { 
     // dequeue the front node. 
     Node *tmpNode = q.front(); 
     q.pop(); 

     // print it..we are sure it is not NULL. 
     cout<<tmpNode->value<<" "; 

     // enqueue left child if it exists. 
     if(tmpNode->left) { 
      q.push(tmpNode->left); 
     } 
     // enqueue right child if it exists. 
     if(tmpNode->right) { 
      q.push(tmpNode->right); 
     } 
    } 
} 

Alternativamente, si usted decide tener NULL en la cola que puede hacer:

void traverse(Node* root) { 
    queue<Node*> q; 

    // push the root..even if it is NULL. 
    q.push(root); 

    // loop till the queue is not empty. 
    while(!q.empty()) { 
     // dequeue the front node. 
     Node *tmpNode = q.front(); 
     q.pop(); 

     // the dequeued pointer can be NULL or can point to a node. 
     // process the node only if it is not NULL.  
     if(tmpNode) {  
      cout<<tmpNode->value<<" "; 
      q.push(tmpNode->left); 
      q.push(tmpNode->right); 
     } 
    } 
} 

El primer método es preferido como un gran árbol tiene un montón de NULL niños (hijos de nodos hoja) y hay no tiene sentido que se pongan en cola en la cola cuando más tarde simplemente no los procesemos.

Answer 4

Usted puede tratar de esta manera:

struct Node 
{ 
    char data; 
    Node* left; 
    Node* right; 
}; 
void LevelOrder(Node* root) 
{ 
    if(root == NULL) return; 
    queue<Node*> Q; 
    Q.push(root); 
    while(!Q.empty()) 
    { 
     Node* current = Q.front(); 
     cout<< current->data << " "; 
     if(current->left != NULL) Q.push(current->left); 
     if(current->right != NULL) Q.push(current->right); 
     Q.pop(); 
    } 
} 

Answer 5

creo fragmentos de código anteriores permiten imprimir el recorrido de fin de nivel en formato de matriz. Este código puede ayudar a escribir la solución en forma de orden de nivel.

vector<vector<int>> levelOrder(TreeNode* root) { 
    vector<vector<int>> a ; 
    vector<int> b; 
    if (root == NULL) return a; 
    std::queue<TreeNode *> q; 
    q.push(root); 
    int nodeCount ; 
    TreeNode* temp; 
    while(true){ 
     nodeCount = q.size(); 
     if (nodeCount == 0) break; 
     while(!nodeCount){ 
      temp = q.front(); 
      b.push_back(temp->val); 
      q.pop(); 
      if(temp->left != NULL) q.push(temp->left); 
      if(temp->right!= NULL) q.push(temp->right); 
      nodeCount-- ; 
     } 
     a.push_back(b); 
     b.resize(0); 
    } 
    return a; 
} 

Salida:

[ [1], 
    [2,3], 
    [4,5] 
] 

Answer 6

Mi solución Java utilizando la estructura de datos de la cola y el algoritmo BFS:

void levelOrder(Node root) { 
     //LinkedList is class of Queue interface 
     Queue<Node> queue=new LinkedList<>(); 
     queue.add(root); 

     //Using BFS algorithm and queue used in BFS solution 
     while(!queue.isEmpty()) { 
       Node node=queue.poll(); 
       System.out.print(node.data+" "); 
       if(node.left!=null) 
       queue.add(node.left); 
       if(node.right!=null) 
       queue.add(node.right); 
       } 
    }