剑指offer之分行从上到下打印二叉树

1 题目

分行从上到下打印二叉树

  

   

    

     

    
    

     

                        2
     
    
   

    

     

    
    

     

                     3    5           
     
    
   

    

     

    
    

     

                   1  4  2  3 
     
    
  
 

我们打印如下

  

   

    

     

    
    

     

      2
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      3     5
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      1     4     2     3
     
    
  
 

2 分析

之前这篇博客写了通过队列按层打印剑指offer之按层打印树节点

 现在无非就是还要按照条件打印，第一次打印1个，然后第二次打印2个，第三次打印4个，我们可以这样，搞2个变量，第一个变量表示这行还没有打印的个数，另外一个变量是下列需要打印的个数，如果这一行还没有打印的个数是0了，我们就把下列需要打印值个数赋值给它，然后下一列变量的个数变量赋值为0.

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

    

     

    
    

     
 //下一列需要打印节点的个数
     
    
   

    

     

    
    

     
 int next_print_count = 0;
     
    
   

    

     

    
    

     
 //当前这一列还需要打印节点的个数
     
    
   

    

     

    
    

     
 int has_print_count = 1;
     
    
   

    

     

    
    

     
 while(queue.size())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Node *node = queue.front();
     
    
   

    

     

    
    

     
 std::cout << node->value << "\t";
     
    
   

    

     

    
    

     
 if (node->left)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 queue.push(node->left);
     
    
   

    

     

    
    

     

       next_print_count++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (node->right) 
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 queue.push(node->right);
     
    
   

    

     

    
    

     

       next_print_count++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 queue.pop();
     
    
   

    

     

    
    

     

       has_print_count--;
     
    
   

    

     

    
    

     
 if (has_print_count == 0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       has_print_count = next_print_count;
     
    
   

    

     

    
    

     

       next_print_count = 0;
     
    
   

    

     

    
    

     
 std::cout << std::endl;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      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
     
    
  
 

5 总结

通过第一行的打印的个数，我们找到第二列打印的个数，通过第二行打印的个数，我们需要打印第三行需要打印的个数，我们可以用2个变量来搞定。

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

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