两种方式遍历二叉树--递归方式和非递归方式

用递归的方法遍历二叉树很简单，但是非递归的遍历二叉树就比较困难了。在非递归方法中，我们需要栈stack的帮助。以下是分别用递归方式和非递归方式写的前、中、后序遍历二叉树的方法，经过验证结果是正确的。

#include <iostream>#include <stack>using namespace std;struct Node {int num;Node* pLeft;Node* pRight;};void insert(Node* &p,int num){Node* pTmp=new Node();pTmp->num=num;pTmp->pLeft=pTmp->pRight=NULL;if(p==NULL){p=pTmp;return;}if(num<p->num)insert(p->pLeft,num);else if(num>p->num)insert(p->pRight,num);elsereturn;}void PreOrder(Node* p){if(p==NULL)return;else{cout<<p->num<<" ";PreOrder(p->pLeft);PreOrder(p->pRight);}}void InOrder(Node* p){if (p==NULL)return;else{InOrder(p->pLeft);cout<<p->num<<" ";InOrder(p->pRight);}}void PostOrder(Node* p){if (p==NULL)return;else{PostOrder(p->pLeft);PostOrder(p->pRight);cout<<p->num<<" ";}}void PreOrderByLoop(Node* p){stack<Node*> MyStack;if(p==NULL)return;while(p!=NULL||!MyStack.empty())//p和栈都为空是结束循环的条件{while(p!=NULL){MyStack.push(p);cout<<p->num<<" ";p=p->pLeft;}if(!MyStack.empty())//从栈中取出一个节点的指针 {p=MyStack.top();MyStack.pop();p=p->pRight;//当前节点的右孩子 当做一个子树的根节点 从新开始循环}}cout<<endl;}void InOrderByLoop(Node* p){stack<Node*> Mystack;while(p!=NULL||!Mystack.empty()){while(p!=NULL){Mystack.push(p);p=p->pLeft;}if(!Mystack.empty()){p=Mystack.top();Mystack.pop();cout<<p->num<<" ";p=p->pRight;}}cout<<endl;}void PostOrderByLoop(Node* p){stack<Node*> Mystack;Node* pre=NULL;//刚刚访问过的节点while(p!=NULL||!Mystack.empty()){while(p!=NULL){Mystack.push(p);p=p->pLeft;}p=Mystack.top();if(p->pRight==NULL||p->pRight==pre)//没有右孩子 或者右孩子刚刚遍历过了{cout<<p->num<<" ";Mystack.pop();pre=p;p=NULL;//加这一句是为了跳过入栈那部分程序}elsep=p->pRight;}cout<<endl;}void main(){Node* p=NULL;insert(p,10);insert(p,6);insert(p,14);insert(p,4);insert(p,8);insert(p,12);insert(p,16);insert(p,1);insert(p,5);insert(p,15);insert(p,17);insert(p,7);insert(p,9); cout<<"Preorder:"<<endl; PreOrder(p);cout<<endl<<"preorderbyLoop:"<<endl;PreOrderByLoop(p);cout<<endl<<"Inorder:"<<endl;InOrder(p);cout<<endl<<"InorderbyLoop:"<<endl;InOrderByLoop(p);cout<<endl<<"Postorder:"<<endl;PostOrder(p);cout<<endl<<"PostOrderByLoop:"<<endl;PostOrderByLoop(p);}