traverse.cpp

实现了对家谱管理系统的添加

#include"Tree.h"

memberTree* PreOrdermemberTree(Stack &S,memberTree *root,int n)//按前序形成树并返回
{
   memberTree *r;
   r=root;
   while(r||S.base!=S.top)
   {

	  if(r)
	  {  
		 if(r->data!=n)
		 {
			Push(S,r);
		    r=r->child;
		 }
		 else  
		 {
			 return r;
		 }
	  }
	  else
	  {
		 r=Pop(S);
		 r=r->brother;
	  }

   }
   return r;

}

void PreOrderprintTree(memberTree * root)//前序打印家谱序列
{
   Stack S=InitStack();
   memberTree *T;
   T=root;
   while(T||S.base!=S.top)
   {

	  if(T)
	  {
		 cout<<T->data<<ends;
		 Push(S,T);
		 T=T->child;
	  }
	  else
	  {
	     T=Pop(S);
		 T=T->brother;
	  }

   }
}

void InOrderprintTree(memberTree * root)
{
   Stack S=InitStack();
   memberTree *T;
   T=root;
   while(T||S.base!=S.top)
   {

	  if(T)
	  {
		 Push(S,T);
		 T=T->child;
	  }
	  else
	  {  
	     T=Pop(S);
		 cout<<T->data<<ends;
		 T=T->brother;
	  }

   }
}




 
void LastOrdermemberTree(memberTree *& h,Queue &Q,List* &head)
{
   
   Stack S=InitStack();

   memberTree *p,*q;
   int tag[200],top=0;
   if(h->child==NULL)
   {  
       if(h->parent->child==h)
	   {
	      h->parent->child=NULL;
		  deleteInformation(Q,head,h->data);
		  delete h;
	   }
	   else
	   {
	      q=h->parent->child;
		  while(q->brother!=h)
		  {
		     q=q->brother;
		  }
		  q->brother=NULL;
          deleteInformation(Q,head,h->data);
		  delete h;
	   }
   }
   else
   {
       
       if(h->parent->child==h)
	   {
	      h->parent->child=NULL;
	   }
	   else
	   {
	      q=h->parent->child;
		  while(q->brother!=h)
		  {
		     q=q->brother;
		  }
		  q->brother=NULL;
	   }

       p=h->child;
       do
	   {
	      while(p)
		  {
		     top++;
             tag[top]=0;
		     Push(S,p);
		     p=p->child;
		  }
		  while(top>0&&tag[top]==1)  //tag[top]=1 说明 堆栈最上面的的节点的 左右 
                                  //子树都访问过了。所以打印本节点
		  {
			p=Pop(S);
			q=p;
			top--;
			deleteInformation(Q,head,q->data);
			delete q;
		  }

		  if(top>0)
		  {
			 p=Pop(S);
			 Push(S,p);
			 p=p->brother;
			 tag[top]=1;  //访问右子树，做标记
		  }
	   }while(top>0);
	deleteInformation(Q,head,h->data);
	delete h;
   }
}

void printRootLeave(memberTree* root)
{
   memberTree *p=root;
   memberTree *q;
   Stack S=InitStack();
  
   while(p||S.base!=S.top)
   {

	  if(p)
	  {
		 if(!p->child)
		 {
			q=p;
			RootLeave(root,q);
		 }
		 Push(S,p);
		 p=p->child;
	  }
	  else
	  {
	     p=Pop(S);
		 p=p->brother;
	  }

   }
}


void RootLeave(memberTree* root,memberTree *q)
{
    Stack s=InitStack();
    if(q==root)
	{
	   cout<<q->data <<endl;
	   return;
	}
	else
	{
	   while(q!=root)
	   {
		  Push(s,q);
		  q=q->parent;
	   }
	   Push(s,q);
	   while(s.base!=s.top)
	   {
	     q=Pop(s);
	     cout<<q->data<<ends;
	   }
	}
	
	cout<<endl;
}

void writeRootLeave(memberTree* &root)
{
	ofstream outfile("relation.txt",ios::out);
	if(!outfile)
	{
	   cout<<"无法打开文件!"<<endl;
	   abort();
	}

   memberTree *p=root;
   memberTree *q;
   Stack S=InitStack();

   while(p||S.base!=S.top)
   {

	  if(p)
	  {
		 if(!p->child)
		 {
			q=p;
			Rootleave(root,q,outfile);
		 }
		 Push(S,p);
		 p=p->child;
	  }
	  else
	  {
	     p=Pop(S);
		 p=p->brother;
	  }
   }

   outfile.close();
}

void Rootleave(memberTree* &root,memberTree *q,ofstream outfile)
{
    Stack s=InitStack();
    if(q==root)
	{
	   //cout<<"此家谱中只有祖先. "<<endl;
	   outfile<<q->data<<ends<<2<<endl;
	   return;
	}
	else
	{
	   while(q!=root)
	   {
		  Push(s,q);
		  q=q->parent;
	   }
	   Push(s,root);
	   while(s.base!=s.top)
	   {
	     q=Pop(s);
	     outfile<<q->data<<ends;
	   }outfile<<endl;
	}
}