C语言按层次遍历二叉树算法

C语言按层次遍历二叉树算法

#define MaxSize 1000
typedef char ElemType; 
typedef struct node 
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;
} BTNode;
//创建二叉树
void CreateBTNode(BTNode *&b,char *str)
{
	BTNode *St[MaxSize],*p=NULL;
	int top=-1,k,j=0;
	char ch;
	b=NULL;
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case '(':top++;St[top]=p;k=1;break;
		case ')':top--;break;
		case ',':k=2;break;
		default:p=(BTNode *)malloc(sizeof(BTNode));
			p->data=ch;p->lchild=p->rchild=NULL;
			if(b==NULL) b=p;
			else
			{
				switch(k)
				{
				case 1:St[top]->lchild=p;break;
				case 2:St[top]->rchild=p;break;
				}    
			}    
		}    
		j++;
		ch=str[j];
	}    
}
//层次遍历算法 
void LevelOrder(BTNode *b)
{
	BTNode *p;
	BTNode *qu[MaxSize];
	int front,rear;
	front=rear=-1;
	rear++;
	qu[rear]=b;
	while(front != rear)
	{
		front=(front+1)%MaxSize;
		p=qu[front];
		printf("%c ",p->data);
		if(p->lchild!=NULL)
		{
			rear=(rear+1)%MaxSize;
			qu[rear]=p->lchild;
		}
		if(p->rchild!=NULL)
		{
			rear=(rear+1)%MaxSize;
			qu[rear]=p->rchild;
		}
	}
}
//主函数
int main()
{
	BTNode *b,*h;
	char s[MaxSize] = "A(B(D(,G)),C(E,F))";
	CreateBTNode(b,s);
	printf("层次遍历算法的访问次序为：");
	LevelOrder(b);
	printf("\n请输入二叉树括号表示法字符串：\n");
	return 0;
}