劍指offer之分行從上到下打印二叉樹

1 題目

分行從上到下打印二叉樹

                      2
                   3    5           
                 1  4  2  3

我們打印如下

    2
     
    3     5
     
    1     4     2     3

 
2 分析

之前這篇博客寫了通過隊列按層打印劍指offer之按層打印樹節(jié)點

 現(xiàn)在無非就是還要按照條件打印，第一次打印1個，然后第二次打印2個，第三次打印4個，我們可以這樣，搞2個變量，第一個變量表示這行還沒有打印的個數(shù)，另外一個變量是下列需要打印的個數(shù)，如果這一行還沒有打印的個數(shù)是0了，我們就把下列需要打印值個數(shù)賦值給它，然后下一列變量的個數(shù)變量賦值為0.
 
 
3 代碼實現(xiàn)

    #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);
        //下一列需要打印節(jié)點的個數(shù)
        int next_print_count = 0;
        //當前這一列還需要打印節(jié)點的個數(shù)
        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 運行結(jié)果

    2
    3       5
    1       4       2       3

 
 
5 總結(jié)

通過第一行的打印的個數(shù)，我們找到第二列打印的個數(shù)，通過第二行打印的個數(shù)，我們需要打印第三行需要打印的個數(shù)，我們可以用2個變量來搞定。


 


作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)