Как бы вы распечатали данные в двоичном дереве, уровень за уровнем, начиная сверху?

Question

Это вопрос интервью

Я думаю о решении. Использует очередь.

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

Может ли кто-нибудь придумать лучшее решение, чем это, которое не использует очередь?

Answer 1

Я настроил ответ так, чтобы он показывал нулевые узлы и печатал его по высоте. На самом деле было довольно прилично для проверки баланса красного черного дерева. может
также добавьте цвет в линию печати, чтобы проверить высоту черного цвета.

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