二叉树的遍历算法(详细示例分析)
#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;
}