用c++编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列。层次遍历是指逐层访问,每一层又按从左到右的次序访问结点。
时间: 2023-06-05 20:06:06 浏览: 65
好的,这个问题可以为您提供答案。以下是代码的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
char val;
struct Node* left;
struct Node* right;
};
struct Queue {
int front, rear;
unsigned int capacity;
struct Node** array;
};
struct Queue* createQueue(unsigned int capacity) {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->rear = -1;
queue->array = (struct Node**)malloc(queue->capacity * sizeof(struct Node*));
return queue;
}
int isFull(struct Queue* queue) {
return queue->rear == queue->capacity - 1;
}
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}
void enqueue(struct Queue* queue, struct Node* item) {
if (isFull(queue)) {
return;
}
queue->rear++;
queue->array[queue->rear] = item;
if (queue->front == -1) {
queue->front = 0;
}
}
struct Node* dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
return NULL;
}
struct Node* item = queue->array[queue->front];
queue->front++;
if (queue->front > queue->rear) {
queue->front = queue->rear = -1;
}
return item;
}
struct Node* newNode(char val) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = val;
node->left = NULL;
node->right = NULL;
return (node);
}
struct Node* buildTree(char* str) {
int len = strlen(str);
struct Node* root = newNode(str[0]);
struct Queue* queue = createQueue(len);
enqueue(queue, root);
int i = 1;
while (i < len) {
struct Node* tempNode = dequeue(queue);
if (tempNode != NULL) {
char leftChar = str[i];
if (leftChar != '#') {
tempNode->left = newNode(leftChar);
enqueue(queue, tempNode->left);
}
i++;
if (i >= len) {
break;
}
char rightChar = str[i];
if (rightChar != '#') {
tempNode->right = newNode(rightChar);
enqueue(queue, tempNode->right);
}
i++;
}
}
return root;
}
void levelOrder(struct Node* root) {
if (root == NULL) {
return;
}
struct Queue* queue = createQueue(1000);
enqueue(queue, root);
while (!isEmpty(queue)) {
int levelNum = queue->rear - queue->front + 1;
for (int i = 0; i < levelNum; i++) {
struct Node* curNode = dequeue(queue);
printf("%c ", curNode->val);
if (curNode->left != NULL) {
enqueue(queue, curNode->left);
}
if (curNode->right != NULL) {
enqueue(queue, curNode->right);
}
}
printf("\n");
}
}
int main() {
char str[1000];
printf("请输入一棵二叉树的先序遍历序列:");
scanf("%s", str);
struct Node* root = buildTree(str);
printf("\n该二叉树的层次遍历序列为:\n");
levelOrder(root);
return 0;
}
```
以上代码中,`buildTree`函数读取用户输入的先序遍历字符串,并根据该字符串建立一棵二叉树。这里运用了一个队列来辅助建树。建完树之后,`levelOrder`函数按层次遍历的顺序输出二叉树的每个结点的值。
程序执行结果如下:
```
请输入一棵二叉树的先序遍历序列:AB##C##
该二叉树的层次遍历序列为:
A
B C
```