您如何从顶部开始逐级打印二进制树中的数据？

一尘不染

您如何从顶部开始逐级打印二进制树中的数据？

algorithm

这是一个面试问题

我想到一个解决方案。它使用队列。

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

有什么能比不使用Queue的解决方案更好的解决方案了吗？

阅读 268

2020-07-28

共1个答案

一尘不染

逐级遍历称为广度优先遍历。使用队列是执行此操作的正确方法。如果要进行深度优先遍历，则可以使用堆栈。

您拥有它的方式并不是很标准。这应该是这样。

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

编辑

这是起作用的算法。假设您有一棵这样的树：

首先，将根（1）排队。然后进入循环。队列（1）中的第一项出队并打印。1的孩子从左到右入队，队列现在包含{2，3}返回循环开始队列（2）中的第一个项目出队并打印2的孩子从左到右入队，队列现在包含{3，
4}回到循环开始…

队列将在每个循环中包含这些值

1：{1}

2：{2，3}

3：{3，4}

4：{4、5、6}

5：{5，6}

6：{6}

7：{} //空，循环终止

输出：

1个

2020-07-28