#2
azzbcc2015-11-30 10:03
|
程序代码:
#include <stdio.h>
#include <stdlib.h>
//二叉树的节点
typedef int Status;
typedef char TElementType;
typedef struct BiTrNode
{
TElementType data;
struct BiTrNode *lchild;
struct BiTrNode *rchild;
}BiTrNode, *BiTree;
//队列的节点
typedef BiTree QElementType;
typedef struct QueueNode
{
QElementType data;
struct QueueNode *next;
}QNode;
typedef struct LinkQueue
{
QNode *front;
QNode *rear;
}*Queue;
//建立队列的头节点
Queue CreateQueue(void) //这里总是显示用了未初始化的局部变量“q”,但是我声明了啊
{
Queue q;
q->front = (QNode *)malloc(sizeof(QNode));
q->rear = q->front;
q->front->next = NULL;
return q;
}
//入队操作
void Add(Queue Q, QElementType data)
{
QNode *p = (QNode *)malloc(sizeof(QNode));
p->data = data;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
//出队操作
QElementType Delete(Queue Q)
{
QElementType data;
QNode *temp = Q->front->next;
data = temp->data;
Q->front->next = temp->next;
free(temp);
return data;
}
//判断队列是否为空
Status IsEmpty(Queue Q)
{
return Q->front->next == NULL;
}
void CreateBiTree(BiTree *T) //先序遍历生成二叉树
{
char c;
scanf("%c", &c);
if (c == '#')
{
*T = NULL;
return;
}
*T = (BiTree)malloc(sizeof(BiTrNode));
(*T)->data = c;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
void LevelOrderTraversal(BiTree T)
{
Queue Q;
if (T == NULL)
{
return;
}
Q = CreateQueue();
Add(Q, T);
while (!IsEmpty(Q))
{
T = Delete(Q);
printf("%c", T->data);
if (T->lchild)
{
Add(Q, T->lchild);
}
if (T->rchild)
{
Add(Q, T->rchild);
}
}
}
int main(void)
{
BiTree T;
CreateBiTree(&T);
LevelOrderTraversal(T);
return 0;
}
#include <stdlib.h>
//二叉树的节点
typedef int Status;
typedef char TElementType;
typedef struct BiTrNode
{
TElementType data;
struct BiTrNode *lchild;
struct BiTrNode *rchild;
}BiTrNode, *BiTree;
//队列的节点
typedef BiTree QElementType;
typedef struct QueueNode
{
QElementType data;
struct QueueNode *next;
}QNode;
typedef struct LinkQueue
{
QNode *front;
QNode *rear;
}*Queue;
//建立队列的头节点
Queue CreateQueue(void) //这里总是显示用了未初始化的局部变量“q”,但是我声明了啊
{
Queue q;
q->front = (QNode *)malloc(sizeof(QNode));
q->rear = q->front;
q->front->next = NULL;
return q;
}
//入队操作
void Add(Queue Q, QElementType data)
{
QNode *p = (QNode *)malloc(sizeof(QNode));
p->data = data;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
//出队操作
QElementType Delete(Queue Q)
{
QElementType data;
QNode *temp = Q->front->next;
data = temp->data;
Q->front->next = temp->next;
free(temp);
return data;
}
//判断队列是否为空
Status IsEmpty(Queue Q)
{
return Q->front->next == NULL;
}
void CreateBiTree(BiTree *T) //先序遍历生成二叉树
{
char c;
scanf("%c", &c);
if (c == '#')
{
*T = NULL;
return;
}
*T = (BiTree)malloc(sizeof(BiTrNode));
(*T)->data = c;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
void LevelOrderTraversal(BiTree T)
{
Queue Q;
if (T == NULL)
{
return;
}
Q = CreateQueue();
Add(Q, T);
while (!IsEmpty(Q))
{
T = Delete(Q);
printf("%c", T->data);
if (T->lchild)
{
Add(Q, T->lchild);
}
if (T->rchild)
{
Add(Q, T->rchild);
}
}
}
int main(void)
{
BiTree T;
CreateBiTree(&T);
LevelOrderTraversal(T);
return 0;
}