剑指offer之先序非递归打印二叉树
【摘要】 1 问题
先序非递归打印二叉树
比如二叉树如下
* 2 * 3 5 * 1 4 2 3 * 3 2 1 5 1 4 2 3
先序原则：中左右打印节点，如果左边有节点继续要打做节点，打印会是如下结果
231324155214323
2 分析
我们可以用st...
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没有限制。
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/90348148
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）