编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树,C语言
时间: 2024-09-09 20:02:37 浏览: 44
C语言 字符串操作和二叉树遍历算法
4星 · 用户满意度95%
要在C语言中根据用户输入的先序遍历字符串建立一个二叉树,我们可以按照以下步骤进行:
1. 定义二叉树节点的数据结构。
2. 读入先序遍历的字符串。
3. 使用递归的方式构建二叉树。
首先,我们定义一个二叉树节点的结构体:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
然后,我们需要一个函数来创建新的树节点:
```c
// 创建新的树节点
TreeNode* createNode(char data) {
TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode == NULL) {
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
```
接下来,我们定义一个递归函数来根据先序遍历的字符串构建二叉树:
```c
// 递归构建二叉树
TreeNode* buildTree(char **str) {
if (**str == '\0') {
return NULL;
}
// 读取当前字符作为节点值
char ch = *(*str)++;
TreeNode *node = createNode(ch);
// 如果是'(',则左子树存在,继续构建左子树
if (ch == '(') {
node->left = buildTree(str);
// 跳过')'
if (**str != ')') {
--(*str); // 回退到最后一个字符
}
++(*str); // 跳过')'
}
// 如果是')',说明左子树构建完成,接下来是右子树
else if (ch == ')') {
return node;
}
// 构建右子树
node->right = buildTree(str);
return node;
}
```
最后,我们可以编写主函数来读取用户输入,并构建二叉树:
```c
int main() {
char str[100]; // 假设输入的字符串不超过100个字符
printf("请输入先序遍历的字符串,例如:ABD##E##CF###\n");
scanf("%s", str);
// 为了方便处理,我们首先将字符串放入一个字符数组中
char *ptr = str;
// 构建二叉树
TreeNode *root = buildTree(&ptr);
// ... 这里可以添加对二叉树进行操作的代码 ...
// 释放二叉树占用的内存(这里未展示)
return 0;
}
```
注意:在实际使用中,这个程序假设输入的字符串格式正确,并且每个节点的值都是单个字符。此外,这里没有添加释放二叉树占用内存的代码,实际应用中应当注意内存管理。
阅读全文