二叉树的递归遍历和非递归（循环）遍历实现

二叉树的递归遍历和非递归（循环）遍历实现struct BinTree{int data;BinTree * left;BinTree * right;};

递归版本

void PreOrder（BinTree * root）{if（root ！= nullptr）{cout << root->data;PreOrder（root->left）;PreOrder（root->right）;}}

循环版本

访问节点 p 并将节点 p 入栈
判断节点 p 的左孩子是否为空，若不为空，则输出左孩子，并将 P 指向新的左孩子，直至左孩子为空
若左孩子为空，这时候左孩子的父节点都已经输出完毕，此时父节点在栈中，因此将 p 指向出栈的节点的右孩子，遍历右分支
直至指针为空并栈为空，遍历结束
中序遍历只需要调整输出语句即可

void PreOrder（BinTree * root）{stack<BinTree *> s;BinTree *p = root;while（p ！= nullptr || ！s.empty（））{while（p ！= nullptr）{cout << p->data << " ";s.push（p）;p = p->left;}if（！s.empty（））{p = s.top（）;s.pop（）;p = p->right;}}}

后序遍历的循环实现难一些

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问

void postOrder（BinTree *root） //非递归后序遍历{stack<BinTree*> s;BinTree *cur;//当前结点 BinTree *pre=NULL; //前一次访问的结点 s.push（root）;while（！s.empty（））{cur=s.top（）;if（（cur->lchild==NULL&&cur->rchild==NULL）|| （pre！=NULL&&（pre==cur->lchild||pre==cur->rchild）））{cout<<cur->data<<" ";//如果当前结点没有孩子结点或者孩子节点都已被访问过 s.pop（）;pre=cur; }else{if（cur->rchild！=NULL）s.push（cur->rchild）;if（cur->lchild！=NULL）s.push（cur->lchild）;}}}

二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-04/116022.htm