1 问题
先序非递归打印二叉树
比如二叉树如下
* 2 * 3 5 * 1 4 2 3 * 3 2 1 5 1 4 2 3
先序原则：中左右打印节点，如果左边有节点继续要打做节点，打印会是如下结果
2 3 1 3 2 4 1 5 5 2 1 4 3 2 3
2 分析
我们可以用stack,先进后出，我们先push头结点，然后再push它的右节点和左节点，依次类推
3 代码实现
#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(); } }
一开始我出现了2个问题
问题1：没有调用stack.pop()函数，导致死循环。
问题2：我把那个stack.pop()写出上面的那个位置，很明显这里是栈，如果node->right或者node->left加到栈里面去了，这个时候再弹出来肯定不是我想要的效果，受之前使用queue的影响，因为pop()函数放哪里都行，想下如果是queue的话，因为是先进先出，所以如果node->right或者node->left加到队列里面去了，再pop()依然是弹出的最顶上的位置，所以不受位置限制。
小结：要记得使用pop()函数弹出来，然后stack调用pop()函数有位置限制，但是queue没有限制。
