algorithm - recorrido - ejemplos de arboles en python

¿Cómo imprimiría los datos en un árbol binario, nivel por nivel, comenzando desde arriba?

Question

Esta es una pregunta de 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);  
        }   
    }
}    

¿Alguien puede pensar en una solución mejor que esta, que no use la Cola?

Answer 1

Ajusté la respuesta para que muestre los nodos nulos y los imprima por altura. En realidad era bastante decente para probar el equilibrio de un árbol rojo negro. puede
También agregue 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 2

Creo que lo que esperan es imprimir los nodos en cada nivel separados por un espacio o una coma y los niveles se separarán por una nueva línea. Así es como codificaría el algoritmo. Sabemos que cuando hacemos una primera búsqueda de amplitud en un gráfico o árbol e insertamos los nodos en una cola, todos los nodos en la cola que salgan estarán al mismo nivel que el anterior o un nuevo nivel que sea el nivel primario + 1 y nada más.

Entonces, cuando esté en un nivel, continúe imprimiendo los valores del nodo y tan pronto como encuentre que el nivel del nodo aumenta en 1, inserte una nueva línea antes de comenzar a imprimir todos los nodos a ese nivel.

Este es mi código que no usa mucha memoria y solo se necesita la cola para todo.

Asumiendo que el árbol comienza desde la raíz.

queue = [(root, 0)]  # Store the node along with its level. 
prev = 0
while queue:
  node, level = queue.pop(0)
  if level == prev:
    print(node.val, end = "")
  else:
    print()
    print(node.val, end = "")
  if node.left:
    queue.append((node.left, level + 1))
  if node.right:
    queue.append((node.right, level + 1))
  prev = level

Al final, todo lo que necesita es la cola para todo el procesamiento.

Answer 3

Dado que la pregunta requiere imprimir el nivel del árbol por nivel, debe haber una manera de determinar cuándo imprimir el nuevo carácter de línea en la consola. Aquí está mi código que intenta hacer lo mismo agregando el 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 4

Intenta con el siguiente código.

public void printLevelOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> nodesToVisit = new LinkedList<>();
    nodesToVisit.add(root);

    int count = nodesToVisit.size();

    while (count != 0) {
        TreeNode node = nodesToVisit.remove();

        System.out.print(" " + node.data);

        if (node.left != null) {
            nodesToVisit.add(node.left);
        }

        if (node.right != null) {
            nodesToVisit.add(node.right);
        }

        count--;

        if (count == 0) {
            System.out.println("");
            count = nodesToVisit.size();
        }
    }
}

Answer 5

Nivel por nivel de recorrido se conoce como primer recorrido de amplitud. Usar una cola es la forma correcta de hacer esto. Si quisieras hacer un recorrido primero en profundidad, usarías una pila.

La forma en que lo tienes no es del todo estándar. Así es como debe 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
    }
 }
}

Editar

Aquí está el algoritmo en el trabajo. Digamos que tenías un árbol así:

     1
    / /
   2   3
  /   / /
 4   5   6

Primero, la raíz (1) sería puesta en cola. Entonces se introduce el bucle. El primer elemento en la cola (1) se saca de la cola y se imprime. Los hijos de 1 se ponen en cola de izquierda a derecha, la cola ahora contiene {2, 3} volver al inicio del bucle. El primer elemento en la cola (2) se borra y se imprimen. Los hijos de 2 se ponen en cola de izquierda a derecha. 4} volver al inicio del bucle ...

La cola contendrá estos valores sobre cada bucle.

1: {1}

2: {2, 3}

3: {3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

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

Salida:

1

2

3

4

5

6

Answer 6

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 se 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 7

Por supuesto que no necesitas usar 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)

Answer 8

Prueba 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 9

Veamos algunas soluciones de Scala. Primero, 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

Definís el árbol así:

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))
                       )
                  )
             )

Definiremos una función breadthFirst que atravesará el árbol aplicando la función deseada a cada elemento. Con esto, definiremos una función de impresión y la usaremos así:

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

printTree(myTree)

Ahora, la solución de Scala, recursiva, enumera 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 de Scala, la cola, sin recursión:

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 tengo una sensación incómoda de que puede simplificarse aún más.

La versión de cola no es funcional, pero es altamente efectiva. Lo poco acerca de importar un objeto es inusual en Scala, pero se le da un buen uso aquí.

Answer 10

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;
    }
  }

Entrada:

Árbol 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. Cree una lista de arrays de nodos de listas vinculadas.
2. Realice el recorrido de orden de nivel usando la cola (búsqueda de amplitud).
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 lo llama nodos de nivel.
4. Ahora, mientras levelNodes> 0, saque los nodos e imprímalos y agregue a sus hijos en la cola.
5. Después de esto, el bucle pone un salto de línea.

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

Answer 11

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();
            }
        }           
    }

}