visit1.h

二叉树的建立,遍历(两种方法),以及用txt文件存储二叉树的方式,还包括队列 堆栈的操作

#include <Tree2.h>

/*----------------/*前序遍历(循环结构)2004.8.07--2004.8.19------------------------*/

void re_preorder(TREE2 * head)
{
  TREE2 * t=head;

	while(1) {
		printf("%c",t->data);				/**/
	    if(t->rlink)push(t->rlink,&top);	/*右子节点入栈*/
		if(t->llink)t=t->llink;			/*沿着左子树遍历*/
		else 
			if(pop(&t,&top))  break;		/*转入右子节点访问*/
    }
	
	while(top!=NULL)	/*清理堆栈*/
		{ pop(&t,&top); t->access=0; }

}

/*----------------/*中序遍历(循环结构)2004.8.25--2004.9.2--------------------------*/
void re_midorder(TREE2 * head)
{
   TREE2 * t=head;
   
   do {

	 while(t!=NULL) {	/*沿着左子树将节点压入堆栈*/
   	    push(t,&top);
		t=t->llink;
     }/*while*/
	 
	 pop(&t,&top);			/*将最后一个压入堆栈的左子树节点(该节点无左子树)弹出访问*/
     printf("%c",t->data);  /*访问*/
     
	 if(t->rlink) t=t->rlink;	/*判断被访问后的节点是否右子树，有则转入右子树*/
     else						/*否则，没有右子树*/
     {
	   do {						/*这个do-while循环的功能是从栈顶节点(当前节点的父节点)开始回溯访问,到有右子树的节点为止*/
	   
		 if(pop(&t,&top)){ t=NULL; break; } /*从栈中取节点,如果堆栈中没有节点将t置空,破坏最外层do-while结构的循环条件*/
		 printf("%c",t->data);				/*堆栈不空,访问弹出的节点*/

	   }while((t=t->rlink)==NULL);			/*先将t指向它的右子节点,再判断原先t(父)节点是否有右子树,没有继续循环*/

     }/*if-else end*/

   }while(top!=NULL || t);

   while(top!=NULL)		/*清理堆栈*/
	 { pop(&t,&top); t->access=0; } 
}

/*--------------------后序遍历(循环法结构)2004.7.30--2004.8.7-------------------------*/

void re_posorder(TREE2 * head)
{
  TREE2 * t=head;

  while(head->access==0)	/*头节点最后访问,每循环一次,访问一个节点*/
  {
	/*从根节点开始沿着左子树边压栈边搜索,
	  先将当前节点压入堆栈后,再判断将当前节点有无右子节点,有,则也将其右子节点压入堆栈,
	  当遇到:左叶子 或 其左子节点已访问过的节点时,退出'搜索'循环。
	  显然,第一次循环时是不会出现后一种情况的,因为此时整棵二叉树所有节点都还未被访问*/

	 while(t->llink && (t->llink->access==0))	/* '搜索'循环,每循环一次就沿着左子树向下推进一层*/
     {
	   push(t,&top);
       if(t->rlink && (t->rlink->access==0))	push(t->rlink,&top);

	   t=t->llink;
     }
	
	  /*上面的while循环结束后,t 可能指向:叶子、左空型节点 (第一次'搜索'循环结束时)
							   也可能指向 其左子节点已访问过的节点 (访问若干个节点后).
	  下面的 if-else结构,判断t指向的这个节点是否是叶节点以及是否已被访问过,	
	  如果是叶子且未被访问过则执行if语句访问数据,
	  如果不是叶子,则肯定是左空型节点, (例如图中的节点T)
	  还需判断'逻辑或'右边的条件,	检查该节点的右子节点的访问标记,	 (即图中J节点的访问标记)
	  
	  如果该节点的右子节点已访问过,根据后序遍历规则就可访问该节点的数据,	
	  否则t指向的就即不是叶子也不是允许访问的左空型节点则转入
	  else语句内,将节点压入堆栈后再访问右子节点*/

	 if( (t->rlink==NULL && (t->access==0)) || (t->rlink->access!=0) )
     {
	   printf("%c",t->data);		/*是叶子,访问节点*/
       t->access=1;					/*给访问过的节点打标记*/
	   if(pop(&t,&top)) break;		/*从新定位指针t(回溯),为访问下一个节点作准备,如果栈空退出最外层循环*/
     }
     else				/*是右子节点还未被访问过的左空型节点*/
	 {
	   push(t,&top);
       t=t->rlink;		/*将指针t指向右子树*/
	 }

  }/*while end*/

  clearmark(head);				  /*由于后序遍历中使用了访问标记,所以要清理访问标记*/
  while(top!=NULL) pop(&t,&top);  /*清理堆栈*/
}

void rankorder(TREE2 * head)	/*层次序遍历2004.9.5*/
{
  TREE2 * p;

  inQueue(head);
  do{
	  if(outQueue(&p)){ printf("empty queue");break; }
	  printf("%c",p->data);
	  if(p->llink!=NULL){ inQueue(p->llink); p->llink=NULL; }
	  if(p->rlink!=NULL){ inQueue(p->rlink); p->rlink=NULL; }
  }while(front!=NULL);
}