劍指offer之先序非遞歸打印二叉樹

1 問題

先序非遞歸打印二叉樹

比如二叉樹如下

         *                  2
         *            3            5           
         *         1     4      2      3       
         *      3    2 1   5  1   4  2   3  

先序原則：中左右打印節(jié)點，如果左邊有節(jié)點繼續(xù)要打做節(jié)點，打印會是如下結果

    2
    3
    1
    3
    2
    4
    1
    5
    5
    2
    1
    4
    3
    2
    3

 
2 分析

我們可以用stack,先進后出，我們先push頭結點，然后再push它的右節(jié)點和左節(jié)點，依次類推

 
3 代碼實現(xiàn)

    #include <iostream>
    #include <stack>
     
    using namespace std;
     
    typedef struct Node
    {
        int value;
        struct Node* left;
        struct Node* right;
    } Node;
     
     
    void start_print(Node *head)
    {
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return;
        }
        std::stack<Node *> stack;
        stack.push(head);
        while (stack.size())
        {
            Node *node = stack.top();
            std::cout << node->value << std::endl;
            //do not remember pop node
                    stack.pop();
            if (node->right)
            {
                stack.push(node->right);
            }
            if (node->left)
            {
                stack.push(node->left);
            }
        }
    }
     
     
    int main()
    {
        /*                  2
         *            3            5           
         *         1     4      2      3       
         *      3    2 1   5  1   4  2   3   
         */
        Node head1, node1, node2, node3, node4, node5, node6;
        Node node7, node8, node9, node10, node11, node12, node13, node14;
        head1.value = 2;
        node1.value = 3;
        node2.value = 5;
        node3.value = 1;
        node4.value = 4;
        node5.value = 2;
        node6.value = 3;
        node7.value = 3;
        node8.value = 2;
        node9.value = 1;
        node10.value = 5;
        node11.value = 1;
        node12.value = 4;
        node13.value = 2;
        node14.value = 3;
     
        head1.left = &node1;
        head1.right = &node2;
     
        node1.left = &node3;
        node1.right = &node4;
     
        node2.left = &node5;
        node2.right = &node6;
     
        node3.left = &node7;
        node3.right = &node8;
        node4.left = &node9;
        node4.right = &node10;
        node5.left = &node11;
        node5.right = &node12;
        node6.left = &node13;
        node6.right = &node14;
       
        node7.left = NULL;
        node7.right = NULL;
        node8.left = NULL;
        node8.right =  NULL;
        node9.left = NULL;
        node9.right = NULL;
        node10.left = NULL;
        node10.right = NULL;
        node11.left = NULL;
        node11.right = NULL;
        node12.left = NULL;
        node12.right = NULL;
        node13.left = NULL;
        node13.right = NULL;
        node14.left = NULL;
        node14.right = NULL;
        start_print(&head1);
        return 0;
    }


 
4 運行結果

    2
    3
    1
    3
    2
    4
    1
    5
    5
    2
    1
    4
    3
    2
    3


 
5 總結

    void start_print(Node *head)
    {
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return;
        }
        std::stack<Node *> stack;
        stack.push(head);
        while (stack.size())
        {
            Node *node = stack.top();
            std::cout << node->value << std::endl;
            if (node->right)
            {
                stack.push(node->right);
            }
            if (node->left)
            {
                stack.push(node->left);
            }
            //do not remember pop node
                    stack.pop();
        }
    }

一開始我出現(xiàn)了2個問題

問題1：沒有調(diào)用stack.pop()函數(shù)，導致死循環(huán)。

問題2：我把那個stack.pop()寫出上面的那個位置，很明顯這里是棧，如果node->right或者node->left加到棧里面去了，這個時候再彈出來肯定不是我想要的效果，受之前使用queue的影響，因為pop()函數(shù)放哪里都行，想下如果是queue的話，因為是先進先出，所以如果node->right或者node->left加到隊列里面去了，再pop()依然是彈出的最頂上的位置，所以不受位置限制。

小結：要記得使用pop()函數(shù)彈出來，然后stack調(diào)用pop()函數(shù)有位置限制，但是queue沒有限制。


 


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