层序遍历二叉树非递归.c

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include<stdlib.h>
#include<stdio.h>
#define MAX 100                             //定义节点最大个数
int i;
typedef struct BinNode                     //定义节点类型
{ 
	char data;
    struct BinNode *lch,*rch;
} BinNode,*Bintree;

struct chtp                                //为输入数据使用 
{
	int len;      
	char ch[MAX];    
};

typedef struct QNode                      //队节点
{                     
	BinNode data;
	struct QNode *next;
}QNode;

typedef struct                             //定义对列结构
{                         
    QNode *head,*last;
}Queue;

struct BinNode *bt;
struct chtp s;

void  crt_pre(Bintree *t)                 //递归建立二叉树
{
	
	char c; 
	c=s.ch[i];     
	i=i+1;
    if (c=='.')  
		*t=NULL;
	else 
	{ 
		*t=(BinNode *)malloc(sizeof (BinNode));     
		(*t)->data=c;
		crt_pre(&(*t)->lch);	  
		crt_pre(&(*t)->rch);
	};
}


void InitQueue(Queue *Q)                     //建立队列
{
	Q->head=NULL;
	Q->last=NULL;
	return;
}

int EnQueue(Queue *Q,BinNode *a)                  //在队列尾部插入a
{
	QNode *temp=(QNode *)malloc(sizeof(QNode));
	if(!temp) 
		return 0;
	temp->data=*a;
	temp->next=NULL;
	if(!Q->head)
		Q->head=temp;
	else Q->last->next=temp;
	Q->last=temp;
	return 1;
}

int DeQueue(Queue *Q,BinNode *a)                 //删除队列第一个元素，并用a返回
{
	QNode *temp;
	if(Q->head!=NULL)                              //若队列不为空
	{
		temp=Q->head;
	    Q->head=temp->next;
	    *a=temp->data;
		free(temp);
		return 1;
	}
	else                                          //若队列为空
		return 0;
}


void Ceng_Bianli(BinNode *t)                       //层序遍历子函数
{
	Queue q;
	InitQueue(&q);                                 //建立队列
	printf("%c",t->data);                          //打印根节点 
	while(t!=NULL)                                 //判断条件：若节点不为空
    {
		if(t->lch!=NULL)                           //若其左孩子节点不为空
		{
			EnQueue(&q,t->lch);
		}
		if(t->rch!=NULL)                           //若其有孩子节点不为空
		{
			EnQueue(&q,t->rch);
		}
		if(DeQueue(&q,t))                          //若队列不为空
		{
			printf("%c",t->data);
		}
		else                                       //否则跳出循环
			break;
	}
}


void main()
{
	char /*c[]={'a','b','d','.','.','.','c','e','.','.','f','.','.','!'};*/
      c[]={'a','b','c','.','.','d','e','.','g','.','.','f','.','.','.','!'};
	//char c[]={'h','d','a','.','.','c','.','b','.','.','g','f','.','e','.','.','.','!'};    
	int i=0;
    for(i=0,s.len=0;c[i]!='!';i++,s.len++) 
		s.ch[i]=c[i];
	crt_pre(&bt);   
	Ceng_Bianli(bt);
	printf("\n");
}