[数据结构与算法]层次顺序遍历二叉树 （二叉树层序遍历）

【问题描述】

编写按层次顺序遍历二叉树的算法

实验要求：以二叉链表作为存储结构
【输入形式】

以扩展二叉树前序遍历序列作为输入，创建二叉树。

【输出形式】

输出层次遍历节点的编号，每层按从左到右顺序输出。

【样例输入】

AB#D##C##

【样例输出】

ABCD

//层次顺序遍历二叉树 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MaxSize 128

// 定义二叉树 
typedef struct Node
{                             
    char         data;       // 数据元素
    struct Node* lchild;     // 指向左孩子节点
    struct Node* rchild;     // 指向右孩子节点
}BiNode;                     // struct Node 的别名
typedef BiNode* BiTree;

// 定义顺序队
typedef struct Queue
{         
    int front;               // 队头指针（实际上不是指针，是一个标签） 
    int rear;                // 队尾指针（实际上不是指针，是一个标签）
    BiNode* data[MaxSize];   // 存放队中元素（保存指针的数组） 
}SqQueue;                    // struct Queue 的别名

//创建二叉树 
BiTree CreateTree()
{ 
	BiTree T;
    char x=getchar();
    if(x=='#')  return T=NULL;
	if(x=='\n') return T;
	else
	{ 
		T=(BiTree)malloc(sizeof(BiNode));
		T->data=x;
		T->lchild=CreateTree();
		T->rchild=CreateTree();
		return T;
	}	
}

//层序遍历  
void LeverOrder(BiTree T)
{
	BiNode *q= NULL;                      //创建临时指针q，移动它，来访问输出节点
    SqQueue* Q;                           //定义队列 Q
    Q=(SqQueue*)malloc(sizeof(SqQueue));  //给Q获取（创建）地址
    Q->front=Q->rear=-1;
    if(T==NULL) return; 
	Q->data[++Q->rear]=T;                                
    while(Q->front!=Q->rear)
	{
		q=Q->data[++Q->front];
		printf("%c",q->data);                                    
        if (q->lchild != NULL)  Q->data[++Q->rear]=q->lchild;
        if (q->rchild != NULL)  Q->data[++Q->rear]=q->rchild;
	}  
} 


int main()
{
	BiTree T;
	T=CreateTree();
    LeverOrder(T);
    return 0;   
}


//薛定谔的月球