|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<iostream>
using namespace std;
const int stacksize=100;
const int m=100;
template<class T>
struct binode
{T data;
binode <T> *lchild;
binode<T> *rchild;};
template <class T>
struct node
{T data;
node<T>* next;};
template <class T>
class stack
{public :
stack() {top=NULL;};
void push(T x);
T pop();
T gettop();
bool empty();
private:
node<T> * top;
};
template <class T>
bool stack<T>::empty()
{return top=NULL?1:0;}
template<class T>
void stack<T>::push(T x)
{node<T>* s;
s=new node<T> ;
s->data=x;s->next=top;top=s;}
template <class T>
T stack<T>::pop()
{if(top==NULL) throw "下溢";
T x=top->data;
node<T> *p;
p=top;top=top->next;
delete p;
return x;}
template <class T>
T stack<T>::gettop(){
if(!empty())
return top->data;}
template <class T>
class tree
{public:
binode<T>* cretree();
void preorder(binode<T>* root);
private:
binode<T>* root;
};
template <class T>
binode<T>* tree<T>::cretree()
{binode<T>* q[m];
T ch;
int front ,rear;
binode<T> *s;
root=NULL;
front=1;rear=0;
int i,n;
cin>>n;
for(i=0;i<n;i++)
{cin>>ch;
s=NULL;
if(ch!='@'){
s=new binode<T>;s->data=ch;s->lchild=NULL;s->rchild=NULL;}
rear++;
q[rear]=s;if(rear=1) root=s;
else{if(s&&q[front])
if(rear%2==0) q[front]->lchild=s;
else q[front]->rchild=s;
if(rear%2==1) front++;}
cin>>ch;}
return root;
}
template<class T>
void tree<T>::preorder(binode<T>* root) //非递归前序遍历
{
stack<binode<T>*> s;
binode<T> *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<' ';
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.gettop();
p=p->rchild;
}
}
}
int main()
{int i,k;
cin>>k;
tree<char> *t;
t=new tree<char>;
for(i=0;i<k;i++)
t->preorder(t->cretree());
system("pause");
return 0;
} |
|