#include<iostream> #include<assert.h> #include<stack> #include<queue> using namespace std; struct Node {     int v;     Node *leftChild,*rightChild;     Node():leftChild(NULL),rightChild(NULL){}     Node(int vv):leftChild(NULL),rightChild(NULL)     {         v=vv;     } }; void print(int v) {     cout<<v<<"   "; } void PreOrderTraverse(Node *n, void (* visit)(int)) {     assert(n!=NULL&&visit!=NULL);     (*visit)(n->v);     if(n->leftChild!=NULL) PreOrderTraverse(n->leftChild,visit);     if(n->rightChild!=NULL) PreOrderTraverse(n->rightChild,visit); } void InOrderTraverse(Node *n, void (* visit)(int)) {     assert(n!=NULL&&visit!=NULL);     if(n->leftChild!=NULL) InOrderTraverse(n->leftChild,visit);     (*visit)(n->v);     if(n->rightChild!=NULL) InOrderTraverse(n->rightChild,visit); } void PostOrderTraverse(Node *n, void (* visit)(int)) {     assert(n!=NULL&&visit!=NULL);     if(n->leftChild!=NULL) PostOrderTraverse(n->leftChild,visit);     if(n->rightChild!=NULL) PostOrderTraverse(n->rightChild,visit);     (*visit)(n->v); } //非递归版本，将递归改成非递归一般都要利用一个栈 //每次访问一个结点后，在向左子树遍历下去之前，利用这个栈记录该结点的右子女（如果有的话）结点的地址， //以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续右子树的遍历 void PreOrder(Node *n, void (* visit)(int)) {     stack<Node*> sta;     sta.push(n);     while(!sta.empty())     {         Node * t=sta.top();         sta.pop();         assert(t!=NULL);         (*visit)(t->v);         if(t->rightChild!=NULL) sta.push(t->rightChild);         if(t->leftChild!=NULL) sta.push(t->leftChild);     } } //非递归中序遍历 void InOrder(Node * n , void (* visit) (int)) {     stack<Node *> sta;     sta.push(n);     Node * p= n;     while(!sta.empty()&&p!=NULL)     {         p=sta.top();         while(p!=NULL&&!sta.empty())         {             sta.push(p->leftChild);             p=p->leftChild;         }         sta.pop();//弹出空指针         if(!sta.empty())         {             p=sta.top();             sta.pop();             (*visit)(p->v);             sta.push(p->rightChild);         }     } } //非递归后续遍历 struct StkNode {     Node * ptr;     bool tag;//false=left and true=right     StkNode():ptr(NULL),tag(false)     {} }; void PostOrder(Node * n ,void (*visit) (int)) {     stack<StkNode> sta;     StkNode w;     Node * p = n;     do {         while(p!=NULL)         {             w.ptr=p;             w.tag=false;             sta.push(w);             p=p->leftChild;         }         bool flag=true;         while(flag&&!sta.empty())         {             w=sta.top();             sta.pop();             p=w.ptr;             if(!w.tag)//left,如果从左子树返回，则开始遍历右子树             {                 w.tag=true;//标记右子树                 sta.push(w);                 flag=false;                 p=p->rightChild;             }             else             {                 (*visit)(p->v);             }         }     } while(!sta.empty()); } //层序遍历，利用队列 void LevelOrderTraverse(Node * n , void (* visit )(int)) {     assert(n!=NULL&&visit!=NULL);     queue<Node * > que;     que.push(n);     while(!que.empty())     {         Node * t=que.front();         (*visit)(t->v);         que.pop();         if(t->leftChild!=NULL) que.push(t->leftChild);         if(t->rightChild!=NULL) que.push(t->rightChild);     } } int main() {     Node * head= new Node(0);     Node * node1= new Node(1);     Node * node2= new Node(2);     Node * node3= new Node(3);     Node * node4= new Node(4);     Node * node5= new Node(5);     Node * node6= new Node(6);     head->leftChild=node1;     head->rightChild=node2;        node1->leftChild=node3;     node1->rightChild=node4;     node2->rightChild=node5;     node4->leftChild=node6;     /*    LevelOrderTraverse(head,print);     cout<<endl;     PreOrderTraverse(head,print);     cout<<endl;*/     InOrder(head,print);     cout<<endl;     InOrderTraverse(head,print);     cout<<endl;     PostOrder(head,print);     cout<<endl;     PostOrderTraverse(head,print);     cout<<endl;     return 0; }