编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列。层次遍历是指逐层访问,每一层又按从左到右的次序访问结点。
输入包括1行字符串,长度不超过100。
输出二叉树的层次遍历序列。每个结点先输出一个空格,然后再跟着输出结点的数据。
12##3##
1 2 3
- #include
- #include
-
- typedef int Status;
- typedef char ElemType;
-
- #define MaxSize 101
- #define OK 1
- #define ERROR -1
- #define OVERFLOW 0
-
- typedef struct BiTNode {
- ElemType data;
- struct BiTNode* lchild;
- struct BiTNode* rchild;
- } BTNode, * BiTree;
-
- typedef struct {
- BTNode data[MaxSize];
- int front, rear;
- } SqQueue;
-
- void InitQueue(SqQueue* qu) {
- qu->front = qu->rear = 0;
- }
-
- int QueueEmpty(SqQueue* qu) {
- return qu->front == qu->rear;
- }
-
- void enQueue(SqQueue* qu, BTNode* node) {
- if ((qu->rear + 1) % MaxSize == qu->front)
- return;
- qu->data[qu->rear] = *node;
- qu->rear = (qu->rear + 1) % MaxSize;
- }
-
- void deQueue(SqQueue* qu, BiTree* node) {
- if (qu->front == qu->rear)
- return;
- *node = &(qu->data[qu->front]);
- qu->front = (qu->front + 1) % MaxSize;
- }
-
- void LevelOrder(BiTree b) {
- if (!b)
- return;
- SqQueue qu;
- InitQueue(&qu);
- enQueue(&qu, b);
- while (!QueueEmpty(&qu)) {
- BiTree p;
- deQueue(&qu, &p);
- printf(" %c", p->data);
- if (p->lchild != NULL)
- enQueue(&qu, p->lchild);
- if (p->rchild != NULL)
- enQueue(&qu, p->rchild);
- }
- }
-
- void CreateBiTree(BiTree* T) {
- ElemType ch;
- scanf(" %c", &ch); // Add a space before %c to consume any whitespace characters including newline
- if (ch == '#')
- *T = NULL;
- else {
- if (!(*T = (BTNode*)malloc(sizeof(BTNode))))
- exit(OVERFLOW);
- (*T)->data = ch;
- CreateBiTree(&((*T)->lchild));
- CreateBiTree(&((*T)->rchild));
- }
- }
-
- void FreeBiTree(BiTree T) {
- if (T == NULL)
- return;
- FreeBiTree(T->lchild);
- FreeBiTree(T->rchild);
- free(T);
- }
-
- int main() {
- BiTree T = NULL;
- printf("Enter a preorder traversal string (length <= 100):\n");
- CreateBiTree(&T);
- printf("Level order traversal:\n");
- LevelOrder(T);
- printf("\n");
- FreeBiTree(T); // Free dynamically allocated memory
- return 0;
- }
```c
#include
#include
```
这两行包含了标准输入输出和内存分配函数的头文件。
```c
typedef int Status;
typedef char ElemType;
```
这里定义了两个类型别名,`Status` 和 `ElemType`,分别用于表示函数的状态和二叉树节点的数据类型。
```c
#define MaxSize 101
#define OK 1
#define ERROR -1
#define OVERFLOW 0
```
这里定义了一些宏,用于指定队列的最大大小以及一些状态码,比如 `OK` 表示成功,`ERROR` 表示错误,`OVERFLOW` 表示内存溢出。
```c
typedef struct BiTNode {
ElemType data;
struct BiTNode* lchild;
struct BiTNode* rchild;
} BTNode, * BiTree;
```
这个结构体定义了二叉树的节点结构,包含了节点的数据以及左右子节点的指针。`BTNode` 是节点类型的别名,`BiTree` 是节点指针类型的别名。
```c
typedef struct {
BTNode data[MaxSize];
int front, rear;
} SqQueue;
```
这个结构体定义了一个顺序队列,用于层序遍历时存储节点。它包含了一个数组用于存储节点,以及队列的前后指针。
```c
void InitQueue(SqQueue* qu) {
qu->front = qu->rear = 0;
}
```
这个函数用于初始化队列,将队列的前后指针都设置为0,表示队列为空。
```c
int QueueEmpty(SqQueue* qu) {
return qu->front == qu->rear;
}
```
这个函数用于判断队列是否为空,即前后指针是否相等。
```c
void enQueue(SqQueue* qu, BTNode* node) {
if ((qu->rear + 1) % MaxSize == qu->front)
return;
qu->data[qu->rear] = *node;
qu->rear = (qu->rear + 1) % MaxSize;
}
```
这个函数用于入队操作,将节点加入队列。如果队列已满,则不进行操作。
```c
void deQueue(SqQueue* qu, BiTree* node) {
if (qu->front == qu->rear)
return;
*node = &(qu->data[qu->front]);
qu->front = (qu->front + 1) % MaxSize;
}
```
这个函数用于出队操作,将队首节点出队,并将节点指针传出。如果队列为空,则不进行操作。
```c
void LevelOrder(BiTree b) {
if (!b)
return;
SqQueue qu;
InitQueue(&qu);
enQueue(&qu, b);
while (!QueueEmpty(&qu)) {
BiTree p;
deQueue(&qu, &p);
printf(" %c", p->data);
if (p->lchild != NULL)
enQueue(&qu, p->lchild);
if (p->rchild != NULL)
enQueue(&qu, p->rchild);
}
}
```
这个函数实现了二叉树的层序遍历。它使用了顺序队列来辅助遍历,先将根节点入队,然后循环执行出队和入队操作,直到队列为空。在遍历过程中,打印每个节点的数据,并将其左右子节点入队。
```c
void CreateBiTree(BiTree* T) {
ElemType ch;
scanf(" %c", &ch); // Add a space before %c to consume any whitespace characters including newline
if (ch == '#')
*T = NULL;
else {
if (!(*T = (BTNode*)malloc(sizeof(BTNode))))
exit(OVERFLOW);
(*T)->data = ch;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
}
```
这个函数用于根据用户输入的先序遍历字符串构建二叉树。用户输入时,'#' 表示空节点。函数递归地构建左右子树,并动态分配内存。
```c
void FreeBiTree(BiTree T) {
if (T == NULL)
return;
FreeBiTree(T->lchild);
FreeBiTree(T->rchild);
free(T);
}
```
这个函数用于释放动态分配的二叉树内存,通过递归遍历二叉树的所有节点,并释放每个节点的内存。
```c
int main() {
BiTree T = NULL;
printf("Enter a preorder traversal string (length <= 100):\n");
CreateBiTree(&T);
printf("Level order traversal:\n");
LevelOrder(T);
printf("\n");
FreeBiTree(T); // Free dynamically allocated memory
return 0;
}
```
这个函数是程序的入口,主要完成以下几个任务:
- 提示用户输入先序遍历字符串。
- 调用 `CreateBiTree` 函数构建二叉树。
- 调用 `LevelOrder` 函数进行层序遍历并打印结果。
- 调用 `FreeBiTree` 函数释放动态分配的内存。
- 返回0表示程序成功运行结束。
```