首页 > 代码库 > 非递归遍历二叉树
非递归遍历二叉树
使用递归可以非常方便地实现二叉树的遍历。如果不使用递归呢，请听我一一道来。
首先给出二叉树遍历的递归版本：
struct BTNode { char data; BTNode *lchild, *rchild;};void visit(BTNode *p){ cout<<p->data<<" ";}//先序遍历void preOrder(BTNode *T){ if(T != NULL) { visit(T); preOrder(T->lchild); preOrder(T->rchild); }}//中序遍历void inOrder(BTNode *T){ if(T != NULL) { inOrder(T->lchild); visit(T); inOrder(T->rchild); }}//后序遍历void postOrder(BTNode *T){ if(T != NULL) { postOrder(T->lchild); postOrder(T->rchild); visit(T); }}
下面给出二叉树遍历的非递归版本：
//非递归先序遍历void preOrder1(BTNode *T){ stack<BTNode*> s; BTNode *p = T; while (p !=NULL || !s.empty()) { while (p != NULL) { visit(p); s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); s.pop(); p = p->rchild; } }}//非递归中序遍历void inOrder1(BTNode *T){ stack<BTNode*> s; BTNode *p = T; while (p !=NULL || !s.empty()) { while (p != NULL) { s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); visit(p); s.pop(); p = p->rchild; } }}//非递归后序遍历void postOrder1(BTNode *T){ stack<BTNode*> s; BTNode *p = T; BTNode *pre = NULL; while (p !=NULL || !s.empty()) { if (p) { s.push(p); p = p->lchild; } else { p = s.top(); if (p->rchild && p->rchild != pre) { p = p->rchild; } else { p = s.top(); visit(p); s.pop(); pre = p; p = NULL; } } }}
参考文章：http://blog.csdn.net/kofsky/article/details/2886453
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html
http://wu-yudong.iteye.com/blog/1992542
http://zisong.me/post/suan-fa/geng-jian-dan-de-bian-li-er-cha-shu-de-fang-fa
再补充一个层次遍历版本：
//层次遍历void levelOrder(BTNode *T){ if (T != NULL) { queue<BTNode*> que; BTNode *p = T; que.push(p); while (!que.empty()) { p = que.front(); visit(p); que.pop(); if(p->lchild) que.push(p->lchild); if(p->rchild) que.push(p->rchild); } }}
最后给大家一个实实在在的例子：
二叉树结构如下：
创建二叉树：
//建立二叉树void createBiTree(BTNode* &T){ char ch = getchar(); if (ch == ‘#‘) T = NULL; else { T = new BTNode; T->data =http://www.mamicode.com/ ch; createBiTree(T->lchild); createBiTree(T->rchild); }}
主函数代码：
int main(){ BTNode *T; cout<<"请按先序遍历顺序输入二叉树，‘#’表示空节点"<<endl; createBiTree(T); cout<<"递归先序遍历："<<endl; preOrder(T); cout<<endl; cout<<"递归中序遍历："<<endl; inOrder(T); cout<<endl; cout<<"递归后序遍历："<<endl; postOrder(T); cout<<endl; cout<<"非递归先序遍历："<<endl; preOrder1(T); cout<<endl; cout<<"非递归中序遍历："<<endl; inOrder1(T); cout<<endl; cout<<"非递归后序遍历："<<endl; postOrder1(T); cout<<endl; cout<<"层次遍历:"<<endl; levelOrder(T); cout<<endl; return 0;}
输出：
树是一种非常重要的数据结构，以后还会有相关文章发表。如有问题，欢迎来稿。
非递归遍历二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。