buildtree.h

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

/*从TXT文件，采用非递归方法建立二叉树*/

#include <Tree2.h>

int buildtree(TREE2 ** head)
{
	/*在此模块中节点的access数据项用来指示节点是否为右空型或叶子节点,等于1时表示该节点为右空型或叶子节点*/

  int fhandle=NULL,    /*数据文件句柄*/
	  steering=LEFT;   /*steering=LEFT时节点挂入左子树,=LEFT时节点挂入右子树*/

  TREE2 * temp=NULL;   /*temp是临时指针,指向新节点*/
  char data[2],
	   filename[15];	/*文件名*/
	   

  printf("file name :"); gets(filename);            /*打开文件*/
  fhandle=open(filename,O_RDONLY);

  if(fhandle==-1)
	  { puts("file not open!!!!"); exit(1); }

  for(;1!=eof(fhandle);)				/*直到所有节点全部挂入二叉树,此循环结束*/
  {
    if(0 > read(fhandle,&data,csize))     /*从文件读取数据*/
    {
      puts("error read file");
      exit(1);
    }
    t=(TREE2 *)malloc(tsize);			/*生成新节点*/
    t->rlink=NULL;	t->llink=NULL;		/*初始化指针*/
    t->next=NULL;	t->access=0;

    if((top==NULL)&&(temp==NULL))		/*是头节点?*/
    {
      *head=t;		     /*是头节点挂入头指针*/
      t->data=data[0];   /*向节点填数据*/
      push(t,&top);
/*
      if(data[1]==R)		/*分析节点描述符,确定 steering 取值 ( if-else 结构)*
		  steering=RIGHT;
      else
          steering=LEFT; */
	  steering = (data[1]==R) ? RIGHT : LEFT;	/*分析节点描述符,确定 steering 取值*/
    }
    else							/*不是头节点*/
    {
     if( ('0'>=data[0]<='z')&&('{'>=data[1]<='~')) 	/*判读数据是否正确*/
     {
       t->data=data[0];   /*向节点填数据*/
       switch(data[1])
       {
         case LEAFAGE:  /*叶子节点处理*/
         {
                if( steering==LEFT ){        /*当作左叶子挂入*/
                   top->llink=t;   steering=RIGHT;
                   t->access=1;    push(t,&top);
                }
                else  {						 /*当作右叶子挂入处理,在这个else中*/
                					
                   while(top->access==1){		/*向父亲节点挂入右子树前清除堆栈中的叶子或右空型节点*/
					    pop(&temp,&top);
						temp->access=0;
				   }
                   top->rlink=t;				  /*向父亲节点挂入右子树*/
                   if(pop(&temp,&top)) return -1; /*将父亲节点从栈顶弹出*/

                   steering=RIGHT;
                }/*else*/

                break;
         }
         case L:   /*右空节点处理*/
         {
                t->access=1;
                if(steering==LEFT) {    /**/
                  top->llink=t;
				  push(t,&top);
				}
                else         /**/
                {					
                  while(top->access==1){			/*向父亲节点挂入右子树前清除堆栈中的叶子或右空型节点*/
					   pop(&temp,&top);
					   temp->access=0;
				  }

                  top->rlink=t;					   /*向父亲节点挂入右子树*/
                  if(pop(&temp,&top)) return -1;	/*将父亲节点从栈顶弹出*/

                  push(t,&top);					   /*右子节点压入堆栈*/
                  steering=LEFT;
                }
                break;
         }
         case R:  /*左空节点处理*/
         {
                if(steering==LEFT) {            /**/
                  top->llink=t;
				  steering=RIGHT;
				  push(t,&top);
				}
                else {   /**/
                					
                  while(top->access==1)	{		/*向父亲节点挂入右子树前清除堆栈中的叶子或右空型节点*/
					   pop(&temp,&top);
					   temp->access=0;
				  }

                  top->rlink=t;					/*向父亲节点挂入右子树*/
                  if(pop(&temp,&top))return -1; /*将父亲节点从栈顶弹出*/
                  push(t,&top);					/*右子节点压入堆栈*/
                }
                break;
         }
         case FULL:  /*满节点处理*/
         {
                if(steering==LEFT) {          /**/
                    top->llink=t; 
					push(t,&top); 
				}
                else        /**/
                {					
                  while(top->access==1)	{		/*向父亲节点挂入右子树前清除堆栈中的叶子或右空型节点*/
					  pop(&temp,&top);
					  temp->access=0; 
				  }

	              top->rlink=t;					/*向父亲节点挂入右子树*/

                  if(pop(&temp,&top))
					  return -1;				/*将父亲节点从栈顶弹出*/

	              push(t,&top);					/*右子节点压入堆栈*/
                  steering=LEFT;
                }
         }
       }/*switch*/
     }
     else		/*判读数据出错*/
     {
       printf("error data in file %s",filename);
       break;
     }

   }/*else*/
  }/*While*/

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

}