二叉树，你如何将打印出来的数据，一层一层地从顶部开始？ [英] How would you print out the data in a binary tree, level by level, starting at the top?

问题描述

这是一个面试问题

我想到了解决办法。 它使用队列。

I think of a solution. It uses queue.

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

有什么东西能想到更好的解决方案比这个，不使用队列？

Can anything think of better solution than this, which doesn't use Queue?

推荐答案

按级别穿越被称为广度优先遍历的水平。使用队列是正确的方式来做到这一点。如果你想做一个深度优先遍历你会使用堆栈。

Level by level traversal is known as Breadth-first traversal. Using a Queue is the proper way to do this. If you wanted to do a depth first traversal you would use a stack.

您有它的方式是不是很标准，但。 下面是应该的。

The way you have it is not quite standard though. Here's how it should be.

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

修改的

下面是该算法在工作。 假设你有一个像这样一棵树：

Here's the algorithm at work. Say you had a tree like so:

     1
    / \
   2   3
  /   / \
 4   5   6

首先，根（1）将被加入队列。该循环然后输入。 在队列（1）第一项出列并打印。 1的儿童被从左至右入队，队列现在包含{2,3} 回到开始循环 在队列（2）第一项出列和印刷 2的孩子们排队的形式从左到右，队列现在包含{3,4} 回到开始循环 ......

First, the root (1) would be enqueued. The loop is then entered. first item in queue (1) is dequeued and printed. 1's children are enqueued from left to right, the queue now contains {2, 3} back to start of loop first item in queue (2) is dequeued and printed 2's children are enqueued form left to right, the queue now contains {3, 4} back to start of loop ...

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

The queue will contain these values over each loop

1：{1}

2：{2,3}

3：{3,4}

4：{4，5，6}

4: {4, 5, 6}

5：{5,6}

6：{6}

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

7: {}//empty, loop terminates

输出：

1

2

3

4

5

6

这篇关于二叉树，你如何将打印出来的数据，一层一层地从顶部开始？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！