Travesía de orden de nivel de árbol binario

Question

Tres tipos de recorridos de árbol son de orden inorder, preorder y posterior.

Un cuarto recorrido, menos utilizado, es el recorrido de nivel de orden. En un recorrido de nivel , todos los nodos a profundidad "d" se procesan antes de cualquier nodo a profundidad d + 1. El recorrido de nivel de nivel difiere de los otros recorridos en que no se realiza recursivamente; se utiliza una cola, en lugar de la pila implícita de recursión.

Mis preguntas sobre fragmento de texto de arriba son

1. Por qué recorridos orden de nivel no se realizan de forma recursiva?
2. ¿Cómo se utiliza la cola en el recorrido de nivel de nivel? Solicitar aclaración con Pseudo código será útil.

¡Gracias!

Answer 1

Level order traversal es en realidad un BFS, que no es recursivo por naturaleza. Utiliza Queue en lugar de Stack para contener los siguientes vértices que se deben abrir. La razón para ello es en este recorrido, que desea abrir los nodos en un orden FIFO, en lugar de una orden LIFO, obtenido por la recursividad

como he mencionado, la orden de nivel es en realidad un BFS, y su [BFS] seudo código [tomado de Wikipedia] es:

1 procedure BFS(Graph,source): 
2  create a queue Q 
3  enqueue source onto Q 
4  mark source 
5  while Q is not empty: 
6   dequeue an item from Q into v 
7   for each edge e incident on v in Graph: 
8    let w be the other end of e 
9    if w is not marked: 
10     mark w 
11     enqueue w onto Q 

(*) en un árbol, marcando los vértices es no es necesario, ya que no puede llegar al mismo nodo en 2 caminos diferentes.

Answer 2

Encontrará una buena visión general en Wikipedia incluso con fragmentos de código.

Answer 3

void levelorder(Node *n) 
{ queue < Node * >q; 

    q.push(n); 


    while(!q.empty()) 
    { 
      Node *node = q.front(); 
      cout<<node->value; 
      q.pop(); 
      if(node->left != NULL) 
      q.push(node->left); 
      if (node->right != NULL) 
      q.push(node->right); 

    } 

} 

Answer 4

En lugar de una cola, utilicé un mapa para resolver esto. Eche un vistazo, si está interesado. Como hago un recorrido postorden, I mantener la profundidad a la que se coloca y utiliza esta profundidad como la clave en un mapa para recoger valores en el mismo nivel

class Solution { public: map<int, vector<int> > levelValues; void recursivePrint(TreeNode *root, int depth){ if(root == NULL) return; if(levelValues.count(root->val) == 0) levelValues.insert(make_pair(depth, vector<int>())); levelValues[depth].push_back(root->val); recursivePrint(root->left, depth+1); recursivePrint(root->right, depth+1); } vector<vector<int> > levelOrder(TreeNode *root) { recursivePrint(root, 1); vector<vector<int> > result; for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){ result.push_back(it->second); } return result; } };

Toda la solución se puede encontrar aquí cada nodo - http://ideone.com/zFMGKU La solución devuelve un vector de vectores con cada vector interior que contiene los elementos en el árbol en el orden correcto.

puede intentar resolverlo aquí - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

Y, como se puede ver, también podemos hacer esto de forma recursiva en el mismo espacio de tiempo y la complejidad como la solución de cola!

Answer 5

https://github.com/arun2pratap/data-structure/blob/master/src/main/java/com/ds/tree/binarytree/BinaryTree.java

por completo se puede mirar hacia fuera para el enlace anterior.

public void levelOrderTreeTraversal(List<Node<T>> nodes){ 
    if(nodes == null || nodes.isEmpty()){ 
     return; 
    } 
    List<Node<T>> levelNodes = new ArrayList<>(); 
    nodes.stream().forEach(node -> { 
     if(node != null) { 
      System.out.print(" " + node.value); 
      levelNodes.add(node.left); 
      levelNodes.add(node.right); 
     } 
    }); 
    System.out.println(""); 
    levelOrderTreeTraversal(levelNodes); 
} 

También se puede extraer http://www.geeksforgeeks.org/

aquí encontrará respuestas relacionadas Casi toda la estructura de datos.