tree.h

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

/*2004.5.11---

*/
#define R '}'
#define L '{'
#define LEAFAGE '!'
#define FULL '~'

typedef struct tree2	  /*树型结构*/
{
 char data;
 int  access;             /*访问标记,access=NULL时表示该节点未被访问过*/
 struct  tree2 * rlink;
 struct  tree2 * llink;
 struct  tree2 * next;    /*堆栈链接指针*/
}TREE2;

typedef struct stack		 /*队列结构定义 当向不循环*/
{
	TREE2 * data;			/*指向数据变量*/
	struct  stack * next;    /*队列节点链接指针*/
}Stack;

TREE2 * top=NULL;		  /*堆栈栈顶指针*/

typedef struct queue		 /*队列结构定义 当向不循环*/
{
	struct  tree2 * data;	 /*指向数据变量*/
	struct  queue * next;    /*队列节点链接指针*/
}Queue;

Queue * front=NULL;			 /*二叉树队列头尾指针*/
Queue * rear=NULL;

int buildtree(TREE2 ** head);			/*从数据文件中读取数据,建立一棵二叉树若函数出错返回-1*/
void freenode(TREE2 * head);			/*清除整个二叉树*/
void push(TREE2 * node,TREE2 ** top);
int pop(TREE2 ** node,TREE2 ** top);	/**/
void clearmark(TREE2 * head);			/*建立二叉树后用该函数清理树中节点的access标志*/
void ptstk(TREE2 * top);				/*打印堆栈内容遇到栈底用#表示*/

void displeft(TREE2 * node);
void dispright(TREE2 * node);

void preorder(TREE2 * head);	/*前序遍历(递归法)*/
void midorder(TREE2 * head);    /*中序遍历(递归法)*/
void posorder(TREE2 * head);    /*后序遍历(递归法)*/

void re_preorder(TREE2 * head);    /*前序遍历(循环法)*/
void re_midorder(TREE2 * head);    /*中序遍历(循环法*/
void re_posorder(TREE2 * head);    /*后序遍历(循环法)*/
void cascadeorder(TREE2 * head);	/*层次序遍历2004.9.5*/

void inQueue(TREE2 * tnode);
int outQueue(TREE2 ** tnode);		/*从队列取出的节点存放在指向指针tnode,如果队列空返回-1*/

	/*入栈函数,node要入栈的节点，top 栈顶指针*/
void push(TREE2 * node,TREE2 ** top)
{
  if((*top)==NULL) node->next=NULL ;   /*如果是第一个节点入栈将第一个节点(尾节点)的NEXT标为NULL*/
  else          node->next=*top;
  *top=node;                         /*新节点入栈*/
}

	/*出栈函数取出的节点存放在指向指针node,如果栈空返回-1*/
int pop(TREE2 ** node,TREE2 ** top)
{
  if ((*top)!=NULL)     /*栈不空,弹出栈元并返回0*/
  {
    *node=*top;
    *top=(*node)->next;
    (*node)->next=NULL;          /*printf("%c",(*top)->data);/*debug*/
    return 0;
  }
  else return -1;    /*若栈空返回-1*/
}

void ptstk(TREE2 * top)
{ TREE2 * j=top;
  printf("\n");
  while(1)
  { if(j==NULL){printf("#");break;}
    printf("%c",j->data);j=j->next;
  }
}

void displeft(TREE2 * node)
{ TREE2 * j=node;

  printf(" ");
  while(j!=NULL)
  {
    printf("%c",j->data);
    j=j->llink;
  }
}

void dispright(TREE2 * node)
{
  TREE2 * j=node;

  printf(" ");
  while(j!=NULL)
  {
    printf("%c",j->data);
    j=j->rlink;
  }
}

void inQueue(TREE2 * tnode)		/*2004.9.4--2004.9.5*/
{
  TREE2 * p;
  Queue * temp;

  if(front==NULL){	/*第一个节点进入空队列*/
	rear=(Queue *)malloc(sizeof(Queue));
	rear->data=tnode; front=rear;
	rear->next=NULL;
  }
  else				/*队列非空*/
  { 
	temp=(Queue *)malloc(sizeof(Queue));
	temp->data=tnode; 
	temp->next=NULL;	/*将数据装入队列节点*/
	rear->next=temp;	/*队列节点入队列*/	
	rear=temp;			/*修改队尾指针*/
  }
}

int outQueue(TREE2 ** tnode) /*2004.9.4*/
{
  Queue * temp;

  if(front==NULL){	/*从空队列中取数据返回-1*/
	return -1;
  }
  else{
	temp=front;			/*选中队头节点*/
	*tnode=temp->data;	/*直接将数据从队头节点中取出*/
	front=temp->next;	/*队列节点出队列*/
	free(temp);			/*清除已出队列并已被取走数据的节点*/

	if(front==NULL)		/*节点清除完毕后检查队列是否已空,若空 rear=nill*/
	{
	   rear=NULL;		/**/
	}
	return 0;
  }
}