如何按层次从顶部开始打印二叉树中的数据？

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

有没有比这个更好的解决方案，而且不使用队列？

- Learner

---

如果有人提供一种比树的 BFS 更易读的解决方案，我会感到惊讶... - Eric

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal - CodeFusionMobile

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的子项加入队列，现在队列包含 {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

2

3

4

5

6

- CodeFusionMobile

---

原文：The OP's code isn't wrong, surely? Writing when you enqueue results in the same order as writing when you dequeue, by definition. Of course your code is DRYer and (hence) better.翻译：OP的代码没错吧？按定义，入队时写入的结果和出队时写入的结果的顺序是一致的。当然，你的代码更DRY（Don't Repeat Yourself，不重复自己），因此更好。 - Steve Jessop

是的，你说得对，这段代码是正确的。我误以为看到了一个实际上并不存在的错误。最好还是只在一个地方处理节点。我已经移除了我之前的断言，即 OP 代码是错误的。 - CodeFusionMobile

Answer 2

由于问题要求逐层打印树形结构，因此需要一种方法来确定何时在控制台上打印换行符。以下是我的代码，它试图通过将NewLine节点附加到队列中来实现相同的功能，

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

- Mru

Answer 3

让我们来看一些Scala解决方案。首先，我将定义一个非常基本的二叉树：

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

我们将使用以下树形结构：

    1
   / \
  2   3
 /   / \
4   5   6

您可以这样定义树结构：

代码示例：

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

我们将定义一个breadthFirst函数，它将遍历树并将所需的函数应用于每个元素。有了这个函数，我们将定义一个print函数，并像这样使用它：

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

printTree(myTree)

现在，我们提供一种Scala解决方案，使用递归和列表，而不是队列：

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

下面是Scala解决方案，使用队列，无递归:

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

那个递归解决方案是完全可行的，虽然我有一种不安的感觉，它可以进一步简化。

队列版本没有功能，但非常有效。导入对象的部分在Scala中是不寻常的，但在这里得到了很好的应用。

- Daniel C. Sobral

Answer 4

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

输入：

创建自平衡树的数据：

 string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};

输出：

 g 
 c k 
 a e i m 
 b d f h j l n 

算法：

1. 创建一个链表节点的ArrayList。
2. 使用队列（广度优先搜索）进行层序遍历。
3. 为了获取每个层次上的所有节点，在从队列中取出一个节点之前，请将队列的大小存储在一个变量中，比如称它为levelNodes。
4. 现在，在levelNodes > 0的同时，取出这些节点并打印它们，并将它们的子节点加入队列中。
5. 这个while循环后要换行。

P.S：我知道OP说不要使用队列。我的答案只是为了展示如果有人正在寻找使用队列的C++解决方案。

- kaushal

Answer 5

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

}

- anshu

Answer 6

为了按层次打印，您可以将节点的级别信息存储为元组添加到队列中。然后，每当级别更改时，您可以打印一个新行。以下是用Python实现此操作的代码。

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

- Faruk Sahin

Answer 7

尝试这个（完整代码）：

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

- JAN

Answer 8

我认为你期望的是按层打印节点，每个节点之间用空格或逗号分隔，不同层之间用换行符分隔。以下是我编写的算法。我们知道，在对图或树进行广度优先搜索并将节点插入队列时，队列中所有出队的节点要么与前一个节点处于同一层级，要么是新的层级，即父级+1，没有其他情况。

因此，当您处于某个层级时，请继续打印节点值，并在发现节点的层级增加1时，在开始打印该层级的所有节点之前插入一个新行。

这是我的代码，它不使用太多内存，只需要队列即可完成。

假设树从根节点开始。

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

最后，您所需的只是用于处理所有内容的队列。

- Ankur Kothari

Answer 9

我调整了答案，以便显示空节点并按高度打印它。实际上非常适合测试红黑树的平衡性。还可以将颜色添加到打印行中以检查黑色高度。

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

- Travis Halvorson

Answer 10

请尝试以下代码。

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

- Naren