二叉树的非递归遍历（借鉴递归思想实现非递归遍历）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的非递归遍历（借鉴递归思想实现非递归遍历），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1568字，纯文字阅读大概需要3分钟。
内容图文
1
//
树结点定义
2 typedef struct TNode
3{
4int value;
5 TNode *left;
6 TNode *right;
7 }*PTNode;
1. 前序遍历的非递归实现（借鉴递归思想实现）
思想：
- 访问到一结点时，先将其入栈，假设入栈节点为P。
- 访问P，将P的右孩子和左孩子依次入栈，这样就保证了每次左孩子在右孩子前面被访问。
1
void
preOrderNoneRecursion(PTNode root)
2
{
3
if(root == NULL)
4return;
5 PTNode p = root;
6 stack<PTNode> nodeStack;
7 nodeStack.push(p);
8while(!nodeStack.empty())
9 {
10 p = nodeStack.top();
11 nodeStack.pop();
12 cout << p->value;
13if(p->right != NULL)
14 nodeStack.push(p->right);
15if(p->left != NULL)
16 nodeStack.push(p->left);
17 }
18 }
2. 中序遍历的非递归实现（借鉴递归思想实现）
// 还没有想出来“借鉴递归思想实现---中序遍历的非递归实现”
3. 后序遍历的非递归实现（借鉴递归思想实现）
思想：
- 访问到一结点时，先将其入栈，假设入栈节点为P。
- 如果P没有左孩子和右孩子，则直接访问P；或者P存在左孩子或者右孩子，但是P的左孩子和右孩子都已被访问过，则同样直接访问P。
- 若不是上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
1
void
postOrderNoneRecursion(PTNode root)
2
{
3
if(root == NULL)
4return;
5 PTNode p = root;
6 PTNode pre = NULL;
7 stack<PTNode> nodeStack;
8 nodeStack.push(p);
9while(!nodeStack.empty())
10 {
11 p = nodeStack.top()
1213if( (p->left == NULL && p->right == NULL)
14 || ((pre! == NULL) && (pre == p->left || pre == p->right))
15 {
16 cout << p->value;
17 nodeStack.pop();
18 pre = p;
19 }
20else21 {
22if(p->right != NULL)
23 nodeStack.push(p->right);
24if(p->left != NULL)
25 nodeStack.push(p->left);
26 }
27 }
28 }
参看文章：
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html
http://blog.csdn.net/sjf0115/article/details/8645991
原文：http://www.cnblogs.com/maybob/p/3935421.html
内容总结
以上是互联网集市为您收集整理的二叉树的非递归遍历（借鉴递归思想实现非递归遍历）全部内容，希望文章能够帮你解决二叉树的非递归遍历（借鉴递归思想实现非递归遍历）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。