二叉树-----二叉链表-----遍历（7种）(二)
LL)
{
s.push(t);
t=t->lchild;
}
else
{
t=s.top();
s.pop();
cout << t->data;
t=t->rchild;
}
}
}
template
void BTtree::nrec_post_order(treenode* t)
{
// struct ND
// {
// treenode* x;
// int flag;
// };
// ND temp;
// stack s;
// temp.x=t;
// while(temp.x!=NULL||!s.empty())
// {
// if(temp.x!=NULL)
// {
// temp.flag=1;
// s.push(temp);
// temp.x=temp.x->lchild;
// }
// else
// {
// if(s.top().flag==2)
// {
// s.pop();
// cout << s.top().x->data;
// }
// else
// {
// s.top().flag=2;
// temp.x=s.top().x->rchild;
// }
// }
// }//不知道为什么用STL这段不行！
struct STACK
{
treenode* tree;
int flag;
} S[maxlen];
int top=maxlen;
treenode* temp;
temp=t;
while(temp!=NULL||top!=maxlen)
{
if(temp!=NULL)
{
S[--top].tree=temp;
S[top].flag=1;
temp=temp->lchild;
}
else
{
if(S[top].flag==2)
{
t=S[top++].tree;
cout << t->data;
}
else
{
S[top].flag=2;
temp=S[top].tree->rchild;
}
}
}
}
template
void BTtree::level_order(treenode* t)
{
queue*> q;
treenode* p;
if(t==NULL) return ;
q.push(t);
while(!q.empty())
{
p=q.front();
cout << p->data;
if(p->lchild)
q.push(p->lchild);
if(p->rchild)
q.push(p->rchild);
q.pop();
}
}
#endif
[cpp]
//main.cpp
#include "BTtree.h"
int main()
{
BTtree tree;
tree.pre_create();
tree.pre_order(tree.return_root());
cout << endl;
tree.in_order(tree.return_root());
cout << endl;
tree.post_order(tree.return_root());
cout << endl << endl;
tree.nrec_pre_order(tree.return_root());
cout << endl;
tree.nrec_in_order(tree.return_root());
cout << endl;
tree.nrec_post_order(tree.return_root());
cout << endl << endl;
tree.level_order(tree.return_root());
return 0;
}
//ABDH##I##E##CF#J##G##
//ABDHIECFJG
//HDIBEAFJCG
//HIDEBJFGCA
//
//ABDHIECFJG
//HDIBEAFJCG
//HIDEBJFGCA
//
//ABCDEFGHIJ