#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);
}
// Non-recursive version, change the recursion to non-recursive 1 Use them all 1 A stack
// Every visit 1 After 1 node, before traversing the left subtree, use this stack to record the address of the node's right child (if any) node,
// In order to get the root node of the right subtree directly from the top of the stack when the left subtree returns, continue the traversal of the right subtree
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);
}
}
// Nonrecursive order traversal
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();// Eject null pointer
if(!sta.empty())
{
p=sta.top();
sta.pop();
(*visit)(p->v);
sta.push(p->rightChild);
}
}
}
// Non-recursive subsequent traversal
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, If you return from the left subtree, begin traversing the right subtree
{
w.tag=true;// Mark the right subtree
sta.push(w);
flag=false;
p=p->rightChild;
}
else
{
(*visit)(p->v);
}
}
} while(!sta.empty());
}
// Order traversal, using queues
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;
}