编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列 使用c++语言
时间: 2023-10-27 10:05:38 浏览: 147
好的,以下是使用C语言编写的程序,实现读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树,并输出该二叉树的层次遍历序列。
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct Queue {
int front;
int rear;
TreeNode* data[MAX_SIZE];
} Queue;
void initQueue(Queue* q) {
q->front = q->rear = 0;
}
int isEmpty(Queue* q) {
return q->front == q->rear;
}
int isFull(Queue* q) {
return (q->rear+1) % MAX_SIZE == q->front;
}
void enQueue(Queue* q, TreeNode* node) {
if (!isFull(q)) {
q->data[q->rear] = node;
q->rear = (q->rear+1) % MAX_SIZE;
}
}
TreeNode* deQueue(Queue* q) {
TreeNode* res = NULL;
if (!isEmpty(q)) {
res = q->data[q->front];
q->front = (q->front+1) % MAX_SIZE;
}
return res;
}
TreeNode* constructTree(char preOrder[], int* index) {
TreeNode* root = NULL;
if (preOrder[*index] != '\0') {
if (preOrder[*index] != '#') {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preOrder[*index] - '0';
(*index)++;
root->left = constructTree(preOrder, index);
(*index)++;
root->right = constructTree(preOrder, index);
} else {
(*index)++;
}
}
return root;
}
void levelOrder(TreeNode* root) {
Queue q;
initQueue(&q);
if (root == NULL) {
return;
}
enQueue(&q, root);
while (!isEmpty(&q)) {
TreeNode* node = deQueue(&q);
printf("%d ", node->val);
if (node->left) {
enQueue(&q, node->left);
}
if (node->right) {
enQueue(&q, node->right);
}
}
}
int main() {
char preOrder[MAX_SIZE];
printf("请输入一串以先序遍历表示的二叉树,其中#表示空节点:\n");
scanf("%s", preOrder);
int index = 0;
TreeNode* root = constructTree(preOrder, &index);
printf("该二叉树的层次遍历序列为:\n");
levelOrder(root);
return 0;
}
```
输入格式:
先序遍历串,其中 '#' 表示空节点,如‘AB#CD###EF#G##’表示的二叉树为:
A
/ \
B C
/ \
D E
/
F
\
G
输出格式:
该二叉树的层次遍历序列。
例如,对于上面的输入,输出应该为:
A B C D E F G
阅读全文