algorithm - 如何从顶部开始逐层打印二叉树中的数据？

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

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

虽然您拥有它的方式并不十分标准。它应该是这样的。

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
    / \
   2   3
  /   / \
 4   5   6

首先，根 (1) 将被排队。然后进入循环。队列 (1) 中的第一项被出列并打印。1 的 child 从左到右排队，队列现在包含 {2, 3}回到循环开始队列 (2) 中的第一项出队并打印2 的 child 从左到右排队，队列现在包含 {3, 4}回到循环开始...

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

1:{1}

2: {2, 3}

3: {3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

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

输出:

1

2

3

4

5

6