剑指offer之按层打印树节点

1 问题

按层打印树节点，比如我们有树如下

  

   

    

     

    
    

     

                          2
     
    
   

    

     

    
    

     

                       3    5           
     
    
   

    

     

    
    

     

                     1  4  2  3
     
    
  
 

这样打印：2 3 5 1 4 2 3

2 分析

队列：先进后出，这里我们先打印2，然后再打印3和5，我们这里可以使用队列，我们先把2入队列，然后我们需要弹出这2节点，先打印队列最前面的节点，然后再把这个节点的的左右节点都入队列，然后再弹出最前面的节点，也就是3了，打印出来了就要弹出这个节点，我们希望下次弹出来最前面的节点才是我们需要打印的，然后再一次把这个弹出的节点左右节点分别入队列，以次类推，然后循环的条件是队列为空。

3 代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int value;
     
    
   

    

     

    
    

     
 struct Node* left;
     
    
   

    

     

    
    

     
 struct Node* right;
     
    
   

    

     

    
    

     

      } Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void layer_print(Node *head)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (head == NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 std::cout << "head is NULL" << std::endl;
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 std::queue<Node *> queue;
     
    
   

    

     

    
    

     
 queue.push(head);
     
    
   

    

     

    
    

     
 while(queue.size())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Node *node = queue.front();
     
    
   

    

     

    
    

     
 std::cout << node->value << std::endl;
     
    
   

    

     

    
    

     
 queue.pop();
     
    
   

    

     

    
    

     
 if (node->left)
     
    
   

    

     

    
    

     
 queue.push(node->left);
     
    
   

    

     

    
    

     
 if (node->right)
     
    
   

    

     

    
    

     
 queue.push(node->right);
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 /* 2
     
    
   

    

     

    
    

     

       * 3 5 
     
    
   

    

     

    
    

     

       * 1 4 2 3 
     
    
   

    

     

    
    

     

       * 
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

       Node head1, node1, node2, node3, node4, node5, node6;
     
    
   

    

     

    
    

     

       Node head2, node7, node8;
     
    
   

    

     

    
    

     

       head1.value = 2;
     
    
   

    

     

    
    

     

       node1.value = 3;
     
    
   

    

     

    
    

     

       node2.value = 5;
     
    
   

    

     

    
    

     

       node3.value = 1;
     
    
   

    

     

    
    

     

       node4.value = 4;
     
    
   

    

     

    
    

     

       node5.value = 2;
     
    
   

    

     

    
    

     

       node6.value = 3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       head1.left = &node1;
     
    
   

    

     

    
    

     

       head1.right = &node2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       node1.left = &node3;
     
    
   

    

     

    
    

     

       node1.right = &node4;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       node2.left = &node5;
     
    
   

    

     

    
    

     

       node2.right = &node6;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       node3.left = NULL;
     
    
   

    

     

    
    

     

       node3.right = NULL;
     
    
   

    

     

    
    

     

       node4.left = NULL;
     
    
   

    

     

    
    

     

       node4.right = NULL;
     
    
   

    

     

    
    

     

       node5.left = NULL;
     
    
   

    

     

    
    

     

       node5.right = NULL;
     
    
   

    

     

    
    

     

       node6.left = NULL;
     
    
   

    

     

    
    

     

       node6.right = NULL;
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

       layer_print(&head1);
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      2
     
    
   

    

     

    
    

     

      3
     
    
   

    

     

    
    

     

      5
     
    
   

    

     

    
    

     

      1
     
    
   

    

     

    
    

     

      4
     
    
   

    

     

    
    

     

      2
     
    
   

    

     

    
    

     

      3
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/90322016