二叉树的层序遍历(广度优先遍历)

二叉树的层序遍历

/*
	Name: 二叉树的层序遍历 
	Copyright: 
	Author: lkm 
	Date: 01/04/22 21:47
*/
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 1000  
typedef struct node 
{ 
    char data; 
    struct node *lchild; 
    struct node *rchild; 
}BiTreeNode,*BiTree; 
//创建二叉树 
//输入abc###def###h##
void CreateBiTree(BiTree &T){
	char c;
	scanf("%c",&c);
	if(c=='#')
	{
		T=NULL;
	}
	else{
		//根据先序存储，叶子节点的左右孩子为空。 
		T=(BiTree)malloc(sizeof(BiTreeNode));
		T->data=c;
		CreateBiTree(T->lchild);		
		CreateBiTree(T->rchild);
	}
} 
//层序遍历算法 
void LevelOrder(BiTree T) 
{ 
    BiTreeNode *p; 
    BiTreeNode *num[MaxSize]; 
    int front,rear; 
    front=rear=-1; 
    rear++; 
    num[rear]=T; 
    while(front != rear) 
    { 
        front=(front+1)%MaxSize; 
        p=num[front]; 
        printf("%c ",p->data); 
  
        if(p->lchild!=NULL) 
        { 
            rear=(rear+1)%MaxSize; 
            num[rear]=p->lchild; 
        } 
  
        if(p->rchild!=NULL) 
        { 
            rear=(rear+1)%MaxSize; 
            num[rear]=p->rchild; 
        } 
    } 
} 
  
//主函数 
int main() 
{ 
	BiTree T;
    CreateBiTree(T);
    printf("层序遍历算法的访问次序为："); 
    LevelOrder(T); 
    return 0; 
}