劍指offer之按層打印樹節(jié)點(diǎn)

1 問題

按層打印樹節(jié)點(diǎn)，比如我們有樹如下

                        2
                     3    5           
                   1  4  2  3

這樣打印：2 3 5 1 4 2 3

 
2 分析

隊(duì)列：先進(jìn)后出，這里我們先打印2，然后再打印3和5，我們這里可以使用隊(duì)列，我們先把2入隊(duì)列，然后我們需要彈出這2節(jié)點(diǎn)，先打印隊(duì)列最前面的節(jié)點(diǎn)，然后再把這個(gè)節(jié)點(diǎn)的的左右節(jié)點(diǎn)都入隊(duì)列，然后再?gòu)棾鲎钋懊娴墓?jié)點(diǎn)，也就是3了，打印出來了就要彈出這個(gè)節(jié)點(diǎn)，我們希望下次彈出來最前面的節(jié)點(diǎn)才是我們需要打印的，然后再一次把這個(gè)彈出的節(jié)點(diǎn)左右節(jié)點(diǎn)分別入隊(duì)列，以次類推，然后循環(huán)的條件是隊(duì)列為空。

 
3 代碼實(shí)現(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);
        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 運(yùn)行結(jié)果

    2
    3
    5
    1
    4
    2
    3

 


 


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