/***********************************************************************************************************************
                                        
  Copyright (C), 2006-2007, MegaByte Tech. Co., Ltd.

  文件名:      LevelOrderTraverse.c
  作者:        孫璇
  功能描述:    輸入二叉樹的數(shù)值，調(diào)用函數(shù)LevelOrderTraverse
               使其按照層次輸出。
  
  函數(shù)列表:    1. main(void)
	           2. CreateBiTree(PBTree *T)
			   3. LevelOrderTraverse(PBTree T)
			   4. InitQue(Pque Q)
			   5. QueEmpty(Pque Q)
			   6. EnQue(Pque Q,PBTree node)
			   7. DeQue(Pque Q,PBTree *node)
			   8. Visit(PBTree pNode)

  未完成:      動(dòng)態(tài)分配的內(nèi)存還沒有釋放!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
          

***********************************************************************************************************************/

#define ERROR 0
#define OK    1
#define NULL  0
#define NODE  struct TNode

#define QUEUE struct Queue
#define QNODE struct QNode

#include <stdio.h>
#include <stdlib.h>

/***********************************************************************************************************************/

typedef NODE                     /*節(jié)點(diǎn)結(jié)構(gòu)體類型*/
{
    char data; 
	NODE *LChild; 
	NODE *RChild; 
} *PBTree;                       /*指向節(jié)點(diǎn)的指針類型*/


typedef QNODE                    /*隊(duì)列節(jié)點(diǎn)結(jié)構(gòu)體類型*/
{
	PBTree  data;
	QNODE  *next;
} *Qnode;                        /*指向隊(duì)列節(jié)點(diǎn)的指針類型*/

typedef QUEUE                    /*隊(duì)列結(jié)構(gòu)體類型*/
{
	Qnode  front;
	Qnode  rear;
} *Pque;                         /*指向隊(duì)列的指針類型*/ 

/*******************************************************************************************************************

  函數(shù)名稱:       main
  調(diào)用函數(shù):       CreateBiTree()
                  LevelOrderTraverse()
				  printf()
  被調(diào)用:         None   

  輸入?yún)?shù):       二叉樹每個(gè)節(jié)點(diǎn)的數(shù)值                  
  輸出參數(shù):       二叉樹元素按照中序排列后的數(shù)值  
  返回值:         None

  功能描述:       輸入二叉樹的數(shù)值，調(diào)用函數(shù)LevelOrderTraverse
                  使其按照層次輸出。

*******************************************************************************************************************/

void main(void)
{
	/*指向指針的指針T*/
	PBTree  *pRoot;

	/*指向根節(jié)點(diǎn)的指針*/
	PBTree  root;

	/*聲明調(diào)用的函數(shù)*/
	int CreateBiTree(PBTree *pRoot);
	int LevelOrderTraverse(PBTree pRoot);

	/*給根節(jié)點(diǎn)申請(qǐng)內(nèi)存空間*/
	if (!(root = (PBTree) malloc (sizeof(PBTree)) ) )
	{
		exit (ERROR);
	}

	/*T指向根節(jié)點(diǎn)的指針*/
	pRoot = &root;

	printf("\nPlease input a tree: ");

	/*創(chuàng)建一棵二叉樹*/
    CreateBiTree(pRoot);

	printf("\nIn level-order is: ");

	/*對(duì)二叉樹按層次遍歷*/
	LevelOrderTraverse(*pRoot);
	printf("\n\n");
		
}	

/*******************************************************************************************************************

  函數(shù)名稱:       InitQue

  調(diào)用函數(shù):       None
  被調(diào)用:         LevelOrderTraverse()   

  輸入?yún)?shù):       Q，指向隊(duì)列結(jié)構(gòu)體的指針。                 
  輸出參數(shù):       None  
 
  返回值:         ERROR，動(dòng)態(tài)分配內(nèi)存失敗。
                  OK   ，成功初始化隊(duì)列。

  功能描述:       參數(shù)Q為指向隊(duì)列結(jié)構(gòu)體的指針，
                  為該結(jié)構(gòu)體變量申請(qǐng)空間并初始化。
                  

*******************************************************************************************************************/

int InitQue(Pque Q)
{
	/*為隊(duì)列申請(qǐng)空間*/
    (*Q).rear = (Qnode)malloc(sizeof(QNODE));

	if (!(*Q).rear)
	{
		/*分配空間失敗*/
		exit (ERROR);
	}
	else
	{
		/*初始化隊(duì)列,頭等于尾*/
		(*Q).front = (*Q).rear;
		(*Q).front->next = NULL;

		return OK;
	}
}


/*******************************************************************************************************************

  函數(shù)名稱:       QueEmpty

  調(diào)用函數(shù):       None
  被調(diào)用:         LevelOrderTraverse()   

  輸入?yún)?shù):       q，指向隊(duì)列結(jié)構(gòu)體的指針。                 
  輸出參數(shù):       None  
 
  返回值:         ERROR，隊(duì)列不是空的。
                  OK   ，隊(duì)列是空的。

  功能描述:       參數(shù)Q為指向隊(duì)列結(jié)構(gòu)體的指針，
                  判斷該變量是不是空隊(duì)列。
                  

*******************************************************************************************************************/

int QueEmpty(Pque Q)
{

	/*頭指針等于尾指針則為空隊(duì)列*/
	if((*Q).rear==(*Q).front)
	{
		return OK;
	}
	else
	{
		/*不等于則不是*/
		return ERROR;
	}
}


/*******************************************************************************************************************

  函數(shù)名稱:       EnQue()

  調(diào)用函數(shù):       None
  被調(diào)用:         LevelOrderTraverse()   

  輸入?yún)?shù):       Q，指向隊(duì)列結(jié)構(gòu)體的指針。
                  node，指向二叉樹節(jié)點(diǎn)類型的指針。
  輸出參數(shù):       None  
 
  返回值:         ERROR，動(dòng)態(tài)分配內(nèi)存失敗。
                  OK   ，將節(jié)點(diǎn)壓入隊(duì)列成功。

  功能描述:       把node指向的節(jié)點(diǎn)壓入Q指向的
                  隊(duì)列結(jié)構(gòu)體變量。
                  
*******************************************************************************************************************/

int EnQue(Pque Q,PBTree node)
{
	/*給一個(gè)節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存*/
    Qnode pnew = (Qnode)malloc(sizeof(QNODE));
	if(!pnew)
	{
		/*分配失敗*/
		exit(ERROR);
	}

	/*把參數(shù)值賦給新節(jié)點(diǎn)*/
	pnew->data = node;
	pnew->next = NULL;

	/*尾指針指向新節(jié)點(diǎn)*/
	Q->rear->next = pnew;
	Q->rear = pnew;

	return OK;
}

/*******************************************************************************************************************

  函數(shù)名稱:       DeQue

  調(diào)用函數(shù):       None
  被調(diào)用:         LevelOrderTraverse()   

  輸入?yún)?shù):       Q，指向隊(duì)列結(jié)構(gòu)體的指針。                
  輸出參數(shù):       node，指向二叉樹節(jié)點(diǎn)類型指針的指針。  
 
  返回值:         ERROR，棧已空。
                  OK   ，將節(jié)點(diǎn)彈出棧成功。

  功能描述:       把Q指向的結(jié)構(gòu)體變量的頭節(jié)點(diǎn)彈出，
                  并用node指向其指針。  
                                    
*******************************************************************************************************************/

int DeQue(Pque Q,PBTree *node)
{
	/*q指向頭指針的下一個(gè)節(jié)點(diǎn)*/
    Qnode q = Q->front->next;

	/*如果是空隊(duì)列*/
	if (Q->front==Q->rear)
	{
		return ERROR;
	}

	/*不是空隊(duì)列*/
	else
	{
		/*q對(duì)應(yīng)的data賦給參數(shù)指向的節(jié)點(diǎn)*/
		*node = q->data;

		/*調(diào)整頭尾節(jié)點(diǎn)的指向*/
		Q->front->next = q->next;
		if (Q->rear == q)
		{
			Q->rear = Q->front;
		}
		return OK;
	}
}

/*******************************************************************************************************************

  函數(shù)名稱:       Visit

  調(diào)用函數(shù):       None
  被調(diào)用:         LevelOrderTraverse()   

  輸入?yún)?shù):       pNode，指向二叉樹節(jié)點(diǎn)類型的指針。                
  輸出參數(shù):       None
 
  返回值:         ERROR，該節(jié)點(diǎn)為NULL。
                  OK   ，將節(jié)點(diǎn)數(shù)據(jù)打印成功。

  功能描述:       把pNode指向的二叉樹節(jié)點(diǎn)的數(shù)據(jù)打印出來。  
                                    
*******************************************************************************************************************/


int Visit(PBTree pNode)
{
	/*pNode不為空*/
	if (pNode)
	{
		/*打印該節(jié)點(diǎn)數(shù)據(jù)部分*/
        printf("%d. ",(*pNode).data);
	    return OK;
	}
	else
	{
		return ERROR;
	}
}

/*******************************************************************************************************************

  函數(shù)名稱:       CreateBiTree

  調(diào)用函數(shù):       scanf()
                  free()
				  CreateBiTree()
				 
  被調(diào)用:         main()
                  CreateBiTree()

  輸入?yún)?shù):       pRoot，指向二叉樹節(jié)點(diǎn)類型指針的指針。                
  輸出參數(shù):       None
 
  返回值:         ERROR，動(dòng)態(tài)分配內(nèi)存失敗。
                  OK   ，創(chuàng)建二叉樹成功。

  功能描述:       用scanf()函數(shù)輸入數(shù)據(jù)，并依次以之為節(jié)點(diǎn)，
                  通過遞歸調(diào)用的方法建立二叉樹。
                                    
*******************************************************************************************************************/

	
int CreateBiTree(PBTree *pRoot)
{
    /*輸入一個(gè)整數(shù)*/
	int  node;
	scanf("%d",&node);

	/*若為0則樹為空樹*/
	if (node==0)
	{
		/*釋放該節(jié)點(diǎn)*/
		free(*pRoot);
	    *pRoot = NULL;
	}/*if*/

	/*若不為0*/
	else
	{
		/*將其值賦給節(jié)點(diǎn)的數(shù)據(jù)部分*/
		(**pRoot).data = node;

		/*為該節(jié)點(diǎn)的左孩子申請(qǐng)空間*/
		if (!((**pRoot).LChild = (PBTree) malloc (sizeof(PBTree)) ) )
		{
		    return ERROR;
		}

		/*建立以其左孩子為根節(jié)點(diǎn)的子樹*/
		CreateBiTree(&(**pRoot).LChild);

		/*為該節(jié)點(diǎn)的右孩子申請(qǐng)空間*/
		if (!((**pRoot).RChild = (PBTree) malloc (sizeof(PBTree)) ) )
		{
		    return ERROR;
		}

		/*建立以其右孩子為根節(jié)點(diǎn)的子樹*/
		CreateBiTree(&(**pRoot).RChild);

	}/*else*/

	return OK;

}/*end*/

/*******************************************************************************************************************

  函數(shù)名稱:       LevelOrderTraverse

  調(diào)用函數(shù):       InitStack()
                  QueEmpty()
				  EnQue()
				  DeQue()
				  Visit()
  被調(diào)用:         main()
                  
  輸入?yún)?shù):       pRoot，指向二叉樹節(jié)點(diǎn)類型指針的指針。                
  輸出參數(shù):       None
 
  返回值:         ERROR，打印節(jié)點(diǎn)不成功。
                  OK   ，成功遍歷二叉樹。

  功能描述:       用InitStack()函數(shù)初始化棧，QueEmpty()判斷棧是否空，
                  EnQue(),DeQue()控制節(jié)點(diǎn)的出入隊(duì)列。Visit()將節(jié)點(diǎn)內(nèi)容打印
				  出來。
                                    
*******************************************************************************************************************/

int LevelOrderTraverse(PBTree pRoot)
{
	/*pNode指向根節(jié)點(diǎn)*/
	PBTree pNode = pRoot;

	/*Q為指向隊(duì)列的指針*/
	Pque   Q;
	Q = (Pque)malloc(sizeof(Pque));
	if(!Q)
	{
		exit (ERROR);
	}

	/*初始化隊(duì)列并壓入根節(jié)點(diǎn)*/
	InitQue(Q);
	EnQue(Q,pNode);

	/*隊(duì)列非空*/
	while(!QueEmpty(Q))
	{
		/*彈出頭節(jié)點(diǎn)*/
		DeQue(Q,&pNode);

		/*用Visit函數(shù)訪問節(jié)點(diǎn)*/
		if (!Visit(pNode))
		{
			/*訪問失敗*/
			return ERROR;

		}/*if*/

		/*打印成功*/
		else
		{
			/*左節(jié)點(diǎn)入隊(duì)列*/
			if((*pNode).LChild)
			{
			    EnQue(Q,(*pNode).LChild);
			}

			/*右節(jié)點(diǎn)入隊(duì)列*/
			if((*pNode).RChild)
			{
			    EnQue(Q,(*pNode).RChild);
			} 
			
		}/*else*/

	}/*while*/

	return OK;

}/*end*/
/*******************************************************************************************************************/