levelordertraverse.c

从键盘输入二叉树的节点数据建立二叉树

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

  文件名:      LevelOrderTraverse.c
  作者:        孙璇
  功能描述:    输入二叉树的数值，调用函数LevelOrderTraverse
               使其按照层次输出。
  
  函数列表:    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)

  未完成:      动态分配的内存还没有释放!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
          

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

#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                     /*节点结构体类型*/
{
    char data; 
	NODE *LChild; 
	NODE *RChild; 
} *PBTree;                       /*指向节点的指针类型*/


typedef QNODE                    /*队列节点结构体类型*/
{
	PBTree  data;
	QNODE  *next;
} *Qnode;                        /*指向队列节点的指针类型*/

typedef QUEUE                    /*队列结构体类型*/
{
	Qnode  front;
	Qnode  rear;
} *Pque;                         /*指向队列的指针类型*/ 

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

  函数名称:       main
  调用函数:       CreateBiTree()
                  LevelOrderTraverse()
				  printf()
  被调用:         None   

  输入参数:       二叉树每个节点的数值                  
  输出参数:       二叉树元素按照中序排列后的数值  
  返回值:         None

  功能描述:       输入二叉树的数值，调用函数LevelOrderTraverse
                  使其按照层次输出。

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

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

	/*指向根节点的指针*/
	PBTree  root;

	/*声明调用的函数*/
	int CreateBiTree(PBTree *pRoot);
	int LevelOrderTraverse(PBTree pRoot);

	/*给根节点申请内存空间*/
	if (!(root = (PBTree) malloc (sizeof(PBTree)) ) )
	{
		exit (ERROR);
	}

	/*T指向根节点的指针*/
	pRoot = &root;

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

	/*创建一棵二叉树*/
    CreateBiTree(pRoot);

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

	/*对二叉树按层次遍历*/
	LevelOrderTraverse(*pRoot);
	printf("\n\n");
		
}	

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

  函数名称:       InitQue

  调用函数:       None
  被调用:         LevelOrderTraverse()   

  输入参数:       Q，指向队列结构体的指针。                 
  输出参数:       None  
 
  返回值:         ERROR，动态分配内存失败。
                  OK   ，成功初始化队列。

  功能描述:       参数Q为指向队列结构体的指针，
                  为该结构体变量申请空间并初始化。
                  

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

int InitQue(Pque Q)
{
	/*为队列申请空间*/
    (*Q).rear = (Qnode)malloc(sizeof(QNODE));

	if (!(*Q).rear)
	{
		/*分配空间失败*/
		exit (ERROR);
	}
	else
	{
		/*初始化队列,头等于尾*/
		(*Q).front = (*Q).rear;
		(*Q).front->next = NULL;

		return OK;
	}
}


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

  函数名称:       QueEmpty

  调用函数:       None
  被调用:         LevelOrderTraverse()   

  输入参数:       q，指向队列结构体的指针。                 
  输出参数:       None  
 
  返回值:         ERROR，队列不是空的。
                  OK   ，队列是空的。

  功能描述:       参数Q为指向队列结构体的指针，
                  判断该变量是不是空队列。
                  

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

int QueEmpty(Pque Q)
{

	/*头指针等于尾指针则为空队列*/
	if((*Q).rear==(*Q).front)
	{
		return OK;
	}
	else
	{
		/*不等于则不是*/
		return ERROR;
	}
}


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

  函数名称:       EnQue()

  调用函数:       None
  被调用:         LevelOrderTraverse()   

  输入参数:       Q，指向队列结构体的指针。
                  node，指向二叉树节点类型的指针。
  输出参数:       None  
 
  返回值:         ERROR，动态分配内存失败。
                  OK   ，将节点压入队列成功。

  功能描述:       把node指向的节点压入Q指向的
                  队列结构体变量。
                  
*******************************************************************************************************************/

int EnQue(Pque Q,PBTree node)
{
	/*给一个节点动态分配内存*/
    Qnode pnew = (Qnode)malloc(sizeof(QNODE));
	if(!pnew)
	{
		/*分配失败*/
		exit(ERROR);
	}

	/*把参数值赋给新节点*/
	pnew->data = node;
	pnew->next = NULL;

	/*尾指针指向新节点*/
	Q->rear->next = pnew;
	Q->rear = pnew;

	return OK;
}

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

  函数名称:       DeQue

  调用函数:       None
  被调用:         LevelOrderTraverse()   

  输入参数:       Q，指向队列结构体的指针。                
  输出参数:       node，指向二叉树节点类型指针的指针。  
 
  返回值:         ERROR，栈已空。
                  OK   ，将节点弹出栈成功。

  功能描述:       把Q指向的结构体变量的头节点弹出，
                  并用node指向其指针。  
                                    
*******************************************************************************************************************/

int DeQue(Pque Q,PBTree *node)
{
	/*q指向头指针的下一个节点*/
    Qnode q = Q->front->next;

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

	/*不是空队列*/
	else
	{
		/*q对应的data赋给参数指向的节点*/
		*node = q->data;

		/*调整头尾节点的指向*/
		Q->front->next = q->next;
		if (Q->rear == q)
		{
			Q->rear = Q->front;
		}
		return OK;
	}
}

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

  函数名称:       Visit

  调用函数:       None
  被调用:         LevelOrderTraverse()   

  输入参数:       pNode，指向二叉树节点类型的指针。                
  输出参数:       None
 
  返回值:         ERROR，该节点为NULL。
                  OK   ，将节点数据打印成功。

  功能描述:       把pNode指向的二叉树节点的数据打印出来。  
                                    
*******************************************************************************************************************/


int Visit(PBTree pNode)
{
	/*pNode不为空*/
	if (pNode)
	{
		/*打印该节点数据部分*/
        printf("%d. ",(*pNode).data);
	    return OK;
	}
	else
	{
		return ERROR;
	}
}

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

  函数名称:       CreateBiTree

  调用函数:       scanf()
                  free()
				  CreateBiTree()
				 
  被调用:         main()
                  CreateBiTree()

  输入参数:       pRoot，指向二叉树节点类型指针的指针。                
  输出参数:       None
 
  返回值:         ERROR，动态分配内存失败。
                  OK   ，创建二叉树成功。

  功能描述:       用scanf()函数输入数据，并依次以之为节点，
                  通过递归调用的方法建立二叉树。
                                    
*******************************************************************************************************************/

	
int CreateBiTree(PBTree *pRoot)
{
    /*输入一个整数*/
	int  node;
	scanf("%d",&node);

	/*若为0则树为空树*/
	if (node==0)
	{
		/*释放该节点*/
		free(*pRoot);
	    *pRoot = NULL;
	}/*if*/

	/*若不为0*/
	else
	{
		/*将其值赋给节点的数据部分*/
		(**pRoot).data = node;

		/*为该节点的左孩子申请空间*/
		if (!((**pRoot).LChild = (PBTree) malloc (sizeof(PBTree)) ) )
		{
		    return ERROR;
		}

		/*建立以其左孩子为根节点的子树*/
		CreateBiTree(&(**pRoot).LChild);

		/*为该节点的右孩子申请空间*/
		if (!((**pRoot).RChild = (PBTree) malloc (sizeof(PBTree)) ) )
		{
		    return ERROR;
		}

		/*建立以其右孩子为根节点的子树*/
		CreateBiTree(&(**pRoot).RChild);

	}/*else*/

	return OK;

}/*end*/

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

  函数名称:       LevelOrderTraverse

  调用函数:       InitStack()
                  QueEmpty()
				  EnQue()
				  DeQue()
				  Visit()
  被调用:         main()
                  
  输入参数:       pRoot，指向二叉树节点类型指针的指针。                
  输出参数:       None
 
  返回值:         ERROR，打印节点不成功。
                  OK   ，成功遍历二叉树。

  功能描述:       用InitStack()函数初始化栈，QueEmpty()判断栈是否空，
                  EnQue(),DeQue()控制节点的出入队列。Visit()将节点内容打印
				  出来。
                                    
*******************************************************************************************************************/

int LevelOrderTraverse(PBTree pRoot)
{
	/*pNode指向根节点*/
	PBTree pNode = pRoot;

	/*Q为指向队列的指针*/
	Pque   Q;
	Q = (Pque)malloc(sizeof(Pque));
	if(!Q)
	{
		exit (ERROR);
	}

	/*初始化队列并压入根节点*/
	InitQue(Q);
	EnQue(Q,pNode);

	/*队列非空*/
	while(!QueEmpty(Q))
	{
		/*弹出头节点*/
		DeQue(Q,&pNode);

		/*用Visit函数访问节点*/
		if (!Visit(pNode))
		{
			/*访问失败*/
			return ERROR;

		}/*if*/

		/*打印成功*/
		else
		{
			/*左节点入队列*/
			if((*pNode).LChild)
			{
			    EnQue(Q,(*pNode).LChild);
			}

			/*右节点入队列*/
			if((*pNode).RChild)
			{
			    EnQue(Q,(*pNode).RChild);
			} 
			
		}/*else*/

	}/*while*/

	return OK;

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