¿Cómo imprimiría los datos en un árbol binario, nivel por nivel, comenzando en la parte superior?

Question

Esta es una pregunta de la entrevista

Pienso en una solución. Utiliza la cola.

public Void BFS()  
{ 
    Queue q = new Queue();  
    q.Enqueue(root);  
    Console.WriteLine(root.Value); 

    while (q.count > 0) 
    { 
     Node n = q.DeQueue(); 
     if (n.left !=null) 
     { 
      Console.Writeln(n.left); 
      q.EnQueue(n.left); 
     } 
     if (n.right !=null) 
     { 
      Console.Writeln(n.right); 
      q.EnQueue(n.right); 
     } 
    } 
}  

¿Se puede pensar en algo mejor que esto, que no utiliza la cola?

Answer 1

El nivel por el recorrido del nivel se conoce como ancho del primer cruce. Usar una cola es la forma correcta de hacer esto. Si quisieras hacer un primer recorrido profundo, usarías una pila.

Sin embargo, la forma en que la tiene no es del todo estándar. Así es como debería ser.

public Void BFS()  
{  
Queue q = new Queue(); 
q.Enqueue(root);//You don't need to write the root here, it will be written in the loop 
while (q.count > 0) 
{ 
    Node n = q.DeQueue(); 
    Console.Writeln(n.Value); //Only write the value when you dequeue it 
    if (n.left !=null) 
    { 
     q.EnQueue(n.left);//enqueue the left child 
    } 
    if (n.right !=null) 
    { 
     q.EnQueue(n.right);//enque the right child 
    } 
} 
} 

Edición

Aquí es el algoritmo en el trabajo. Supongamos que tenía un árbol de este modo:

 1 
    /\ 
    2 3 
//\ 
4 5 6 

En primer lugar, la raíz (1) se pone en cola. El bucle se ingresa. el primer elemento de la cola (1) se quita de la cola y se imprime. Los hijos de 1 están enrutados de izquierda a derecha, la cola ahora contiene {2, 3} al inicio del ciclo primer elemento en la cola (2) se cancela e imprime 2 hijos son enrutados de izquierda a derecha, la cola ahora contiene {3, 4} volver a empezar de bucle ...

La cola contendrá estos valores a lo largo de cada bucle

1: {1}

2: {2, 3}

3: { 3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

7: {} // vacío, bucle termina

de salida:

Answer 2

Veamos algunas soluciones Scala.En primer lugar, voy a definir un árbol binario muy básico:

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]]) 

Usaremos el siguiente árbol:

1 
/\ 
    2 3 
//\ 
4 5 6 

Se define el árbol de la siguiente manera:

val myTree = Tree(1, 
        Some(Tree(2, 
          Some(Tree(4, None, None)), 
          None 
         ) 
       ), 
        Some(Tree(3, 
          Some(Tree(5, None, None)), 
          Some(Tree(6, None, None)) 
         ) 
       ) 
      ) 

Hemos Definiremos una función breadthFirst que recorra el árbol aplicando la función deseada a cada elemento. Con esto, vamos a definir una función de impresión y utilizar de esta manera:

def printTree(tree: Tree[Any]) = 
    breadthFirst(tree, (t: Tree[Any]) => println(t.value)) 

printTree(myTree) 

Ahora, la solución Scala, recursiva, listas, pero no hay colas:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = { 
    def traverse(trees: List[Tree[T]]): Unit = trees match { 
    case Nil => // do nothing 
    case _ => 
     val children = for{tree <- trees 
         Some(child) <- List(tree.left, tree.right)} 
         yield child 
     trees map f 
     traverse(children) 
    } 

    traverse(List(t)) 
} 

A continuación, la solución Scala, colas, sin recursividad:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = { 
    import scala.collection.mutable.Queue 
    val queue = new Queue[Option[Tree[T]]] 
    import queue._ 

    enqueue(Some(t)) 

    while(!isEmpty) 
    dequeue match { 
     case Some(tree) => 
     f(tree) 
     enqueue(tree.left) 
     enqueue(tree.right) 
     case None => 
    } 
} 

esa solución recursiva es completamente funcional, aunque no tengo la incómoda sensación de que puede ser aún más simplificado.

La versión de la cola no es funcional, pero es muy efectiva. El truco sobre la importación de un objeto es inusual en Scala, pero se le da un buen uso aquí.

Answer 3

Para imprimir por nivel, puede almacenar la información de nivel con el nodo como una tupla para agregar a la cola. Luego puede imprimir una nueva línea cada vez que cambie el nivel. Aquí hay un código de Python para hacerlo.

from collections import deque 
class BTreeNode: 
    def __init__(self, data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 

    def printLevel(self): 
     """ Breadth-first traversal, print out the data by level """ 
     level = 0 
     lastPrintedLevel = 0 
     visit = deque([]) 
     visit.append((self, level)) 
     while len(visit) != 0: 
      item = visit.popleft() 
      if item[1] != lastPrintedLevel: #New line for a new level 
       lastPrintedLevel +=1 
       print 
      print item[0].data, 
      if item[0].left != None: 
       visit.append((item[0].left, item[1] + 1)) 
      if item[0].right != None: 
       visit.append((item[0].right, item[1] + 1)) 

Answer 4

Dado que la cuestión requiere imprimir el nivel de árbol por nivel, debe haber una manera de determinar cuándo se debe imprimir el carácter de línea nueva en la consola. Aquí está mi código que trata de hacer lo mismo añadiendo nodo NewLine a la cola,

void PrintByLevel(Node *root) 
{ 
    Queue q; 
    Node *newline = new Node("\n"); 
    Node *v; 
    q->enque(root); 
    q->enque(newline); 

    while(!q->empty()) { 
     v = q->deque(); 
     if(v == newline) { 
     printf("\n"); 
     if(!q->empty()) 
      q->enque(newline); 
     } 
     else { 
     printf("%s", v->val); 
     if(v->Left) 
      q-enque(v->left); 
     if(v->right) 
      q->enque(v->right); 
     } 
    } 
    delete newline; 
} 

Answer 5

public class LevelOrderTraversalQueue {  

    Queue<Nodes> qe = new LinkedList<Nodes>(); 

    public void printLevelOrder(Nodes root)  
    { 
     if(root == null) return; 

     qe.add(root); 
     int count = qe.size(); 

     while(count!=0) 
     { 
      System.out.print(qe.peek().getValue()); 
      System.out.print(" "); 
      if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft()); 
      if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight()); 
      qe.remove(); count = count -1; 
      if(count == 0) 
      { 
       System.out.println(" "); 
       count = qe.size(); 
      } 
     }   
    } 

} 

Answer 6

pellizqué la respuesta para que muestre los nodos nulos y lo imprime por la altura. Era realmente bastante decente para probar el equilibrio de un árbol negro rojo. puede
también agregar el color en la línea de impresión para verificar la altura del negro.

Queue<node> q = new Queue<node>(); 
    int[] arr = new int[]{1,2,4,8,16,32,64,128,256}; 
    int i =0; 
    int b = 0; 
    int keeper = 0; 
    public void BFS() 
    { 


     q.Enqueue(root); 
     while (q.Count > 0) 
     { 

      node n = q.Dequeue(); 

      if (i == arr[b]) 
      { 

       System.Diagnostics.Debug.Write("\r\n"+"("+n.id+")"); 
       b++; 
       i =0 ; 
      } 
      else { 

       System.Diagnostics.Debug.Write("(" + n.id + ")"); 

      } 
      i++; 


      if (n.id != -1) 
      { 



       if (n.left != null) 
       { 

        q.Enqueue(n.left); 
       } 
       else 
       { 
        node c = new node(); 
        c.id = -1; 
        c.color = 'b'; 
        q.Enqueue(c); 
       } 

       if (n.right != null) 
       { 

        q.Enqueue(n.right); 
       } 
       else 
       { 
        node c = new node(); 
        c.id = -1; 
        c.color = 'b'; 
        q.Enqueue(c); 

       } 
      } 

     } 
     i = 0; 
     b = 0; 
     System.Diagnostics.Debug.Write("\r\n"); 
    } 

Answer 7

Pruebe este (Código completo):

class HisTree 
{ 
    public static class HisNode 
    { 
     private int data; 
     private HisNode left; 
     private HisNode right; 

     public HisNode() {} 
     public HisNode(int _data , HisNode _left , HisNode _right) 
     { 
      data = _data; 
      right = _right; 
      left = _left; 
     } 
     public HisNode(int _data) 
     { 
      data = _data; 
     } 
    } 

    public static int height(HisNode root) 
    { 
     if (root == null) 
     { 
      return 0; 
     } 

     else 
     { 
      return 1 + Math.max(height(root.left), height(root.right)); 
     } 
    } 


    public static void main(String[] args) 
    { 
//   1 
//  /\ 
//  / \ 
//  2  3 
// /\ /\ 
//  4 5 6 7 
// /
// 21 

     HisNode root1 = new HisNode(3 , new HisNode(6) , new HisNode(7)); 
     HisNode root3 = new HisNode(4 , new HisNode(21) , null); 
     HisNode root2 = new HisNode(2 , root3 , new HisNode(5)); 
     HisNode root = new HisNode(1 , root2 , root1); 
     printByLevels(root); 
    } 


    private static void printByLevels(HisNode root) { 

     List<HisNode> nodes = Arrays.asList(root); 
     printByLevels(nodes); 

    } 

    private static void printByLevels(List<HisNode> nodes) 
    { 
     if (nodes == null || (nodes != null && nodes.size() <= 0)) 
     { 
      return; 
     } 
     List <HisNode> nodeList = new LinkedList<HisNode>(); 
     for (HisNode node : nodes) 
     { 
      if (node != null) 
      { 
       System.out.print(node.data); 
       System.out.print(" , "); 
       nodeList.add(node.left); 
       nodeList.add(node.right); 
      } 
     } 
     System.out.println(); 
     if (nodeList != null && !CheckIfNull(nodeList)) 
     { 
      printByLevels(nodeList);  
     } 
     else 
     { 
      return; 
     } 

    } 


    private static boolean CheckIfNull(List<HisNode> list) 
    { 
     for(HisNode elem : list) 
     { 
      if (elem != null) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

Answer 8

C++:

struct node{ 
    string key; 
    struct node *left, *right; 
    }; 

    void printBFS(struct node *root){ 
    std::queue<struct node *> q; 
    q.push(root); 

    while(q.size() > 0){ 
     int levelNodes = q.size(); 
     while(levelNodes > 0){ 
     struct node *p = q.front(); 
     q.pop(); 
     cout << " " << p->key ; 
     if(p->left != NULL) q.push(p->left); 
     if(p->right != NULL) q.push(p->right); 
     levelNodes--; 
     } 
     cout << endl; 
    } 
    } 

de entrada:

árbol de equilibrado creado a partir de:

string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"}; 

Salida:

g 
c k 
a e i m 
b d f h j l n 

Algorithm:

1. Crear un ArrayList de nodos lista enlazada.
2. Haga el recorrido de la orden de nivel utilizando la cola (Búsqueda inicial de ancho).
3. Para obtener todos los nodos en cada nivel, antes de sacar un nodo de la cola, almacene el tamaño de la cola en una variable, digamos que la llama como levelNodes.
4. Ahora, mientras LevelNodes> 0, saca los nodos e imprime y agrega sus hijos a la cola.
5. Después de esto, while loop ponga un salto de línea.

P.S: Sé que OP dijo, no queue. Mi respuesta es solo para mostrar si alguien está buscando una solución C++ usando cola.

Answer 9

Por supuesto, no necesita utilizar la cola. Esto está en Python.

# Function to print level order traversal of tree 
def printLevelOrder(root): 
    h = height(root) 
    for i in range(1, h+1): 
     printGivenLevel(root, i) 


# Print nodes at a given level 
def printGivenLevel(root , level): 
    if root is None: 
     return 
    if level == 1: 
     print "%d" %(root.data), 
    elif level > 1 : 
     printGivenLevel(root.left , level-1) 
     printGivenLevel(root.right , level-1) 


""" Compute the height of a tree--the number of nodes 
    along the longest path from the root node down to 
    the farthest leaf node 
""" 
def height(node): 
    if node is None: 
     return 0 
    else : 
     # Compute the height of each subtree 
     lheight = height(node.left) 
     rheight = height(node.right) 
     return max(lheight, reight)