转载请注明出处：http://blog.csdn.net/ns_code/article/details/26089165
剑指offer上的第23题，实际上就是考察二叉树的层序遍历，详细思想能够參考这里。
- 题目描写叙述：
从上往下打印出二叉树的每一个节点，同层节点从左至右打印。
- 输入：
输入可能包括多个測试例子，输入以EOF结束。
对于每一个測试案例。输入的第一行一个整数n(1<=n<=1000, ：n代表将要输入的二叉树元素的个数（节点从1開始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行。每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子。紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子。紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。
- 输出：
相应每一个測试案例，
依照从上之下。从左至右打印出二叉树节点的值。
- 例子输入：
7 8 6 5 7 10 9 11 d 2 5 d 3 4 z z d 6 7 z z
- 例子输出：
8 6 10 5 7 9 11
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/*
二叉树的存储结构
*/
typedef struct BTNode
{
int data;
int rchild;
int lchild;
}BTNode;
/*
队列的存储结构
*/
typedef struct Node
{
BTNode data;
struct Node *pNext;
}NODE,*PNODE;
typedef struct Queue
{
PNODE front; //队头指针
PNODE rear; //队尾指针
}QUEUE,*PQUEUE;
/*
创建一个空队列，队头指针和队尾指针都指向头结点，
头结点中不存放数据，仅仅存放指针
*/
PQUEUE create_queue()
{
PQUEUE pS = (PQUEUE)malloc(sizeof(QUEUE));
pS->front = (PNODE)malloc(sizeof(NODE));
if(!pS || !pS->front)
{
printf("pS or front malloc failed!!");
exit(-1);
}
else
{
pS->rear = pS->front;
pS->front->pNext = NULL;
}
return pS;
}
/*
推断队列是否为空
*/
bool is_empty(PQUEUE pS)
{
if(pS->front == pS->rear)
return true;
else
return false;
}
/*
进队函数，从队尾进队，队头指针保持不变
*/
void en_queue(PQUEUE pS, BTNode e)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(!pNew)
{
printf("pNew malloc failed");
exit(-1);
}
else
{
pNew->data = e;
pNew->pNext = NULL;
pS->rear->pNext = pNew;
pS->rear = pNew;
}
return;
}
/*
出队函数，从队头出队，队尾指针保持不变，但当最后一个元素出队时。
须要对队尾指针又一次赋值。使其指向头结点
*/
bool de_queue(PQUEUE pS,BTNode *pData)
{
if(is_empty(pS))
return false;
else
{
PNODE p = pS->front->pNext;
*pData = p->data;
pS->front->pNext = p->pNext;
//这里是队列头元素出队的特殊情况，普通情况下。删除队头元素时
//仅需改动头结点中的指针，但当队列中最后一个元素被删除时，
//队列尾指针也丢失了。因此需对队尾指针又一次赋值（指向头结点）。
if(pS->rear == p)
pS->rear = pS->front;
free(p);
}
return true;
}
/*
销毁队列,头结点也被销毁,最后也将pS节点销毁，并将其指向为空，避免垂直指针的产生
*/
void destroy_queue(PQUEUE pS)
{
if(is_empty(pS))
return;
else
{
while(pS->front)
{
pS->rear = pS->front->pNext;
free(pS->front);
pS->front = pS->rear;
}
}
free(pS);
pS = 0;
return;
}
/*
层序遍历二叉树
*/
void LevelTraverse(BTNode *pTree,int index,int *LevTraverse,int n)
{
if(pTree == NULL)
return;
if(index == -1)
return;
BTNode pBTNode;
PQUEUE pS = create_queue();
en_queue(pS, pTree[0]);
int i = 0;
while(!is_empty(pS) && i<n)
{
de_queue(pS,&pBTNode);
//相同，先把元素按层序遍历的顺序保存起来
LevTraverse[i++] = pBTNode.data;
if(pBTNode.lchild != -1)
en_queue(pS, pTree[pBTNode.lchild]);
if(pBTNode.rchild != -1)
en_queue(pS, pTree[pBTNode.rchild]);
}
destroy_queue(pS);
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
//输入树pTree各节点的值
BTNode *pTree = NULL;
if(n>0)
{
pTree = (BTNode *)malloc(n*sizeof(BTNode));
if(pTree == NULL)
exit(EXIT_FAILURE);
int i,data;
//输入n个节点的data
for(i=0;i<n;i++)
{
scanf("%d",&data);
pTree[i].data = data;
pTree[i].rchild = -1;
pTree[i].lchild = -1;
}
//输入n行节点连接关系
for(i=0;i<n;i++)
{
char ci;
//这两行的作用是为了跳过缓冲区中的换行符
//这里不能用fflush(stdin)，gcc不支持。这仅仅是一些编译器自加的。
//假设用了，測试系统会报RE。
while(getchar() != '
')
continue;
scanf("%c",&ci);
if(ci == 'z')
continue;
else if(ci == 'l')
{
int lindex;
scanf("%d",&lindex);
pTree[i].lchild = lindex-1;
}
else if(ci == 'r')
{
int rindex;
scanf("%d",&rindex);
pTree[i].rchild = rindex-1;
}
else if(ci == 'd')
{
int lindex,rindex;
scanf("%d",&lindex);
scanf("%d",&rindex);
pTree[i].lchild = lindex-1;
pTree[i].rchild = rindex-1;
}
}
}
//先将遍历的元素依次保存到preTraverse数组中
int *LevTraverse = (int *)malloc(n*sizeof(int));
if(LevTraverse == NULL)
exit(EXIT_FAILURE);
LevelTraverse(pTree,0,LevTraverse,n);
int i;
for(i=0;i<n;i++)
{
//使输出符合測试系统要求的格式
if(i == n-1)
printf("%d
",LevTraverse[i]);
else
printf("%d ",LevTraverse[i]);
}
free(LevTraverse);
LevTraverse = NULL;
free(pTree);
pTree = NULL;
}
return 0;
}
/************************************************************** Problem: 1523 User: mmc_maodun Language: C Result: Accepted Time:0 ms Memory:916 kb****************************************************************/