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 nodestack.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 nodestack.pop();} }

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

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

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

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

總結

以上是生活随笔為你收集整理的剑指offer之先序非递归打印二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。