用c语言写出一段代码完成以下要求,客户输入二叉树的字符型数据,输入0创建空树,输出二叉树的先序遍历,中序遍历,后序遍历和层序遍历
时间: 2024-03-14 22:42:57 浏览: 59
以下是使用C语言实现二叉树遍历的代码,包括先序遍历、中序遍历、后序遍历和层序遍历。客户输入的二叉树数据要求是按照先序遍历的顺序输入,如果某个节点没有子节点,需要输入一个特殊字符(例如#),以便在构造二叉树时正确判断左右子树是否为空。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
char c;
scanf("%c", &c);
if (c == '0') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = c;
root->left = createTree();
root->right = createTree();
return root;
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
// 层序遍历
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
TreeNode* node = queue[front++];
printf("%c ", node->val);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}
int main() {
printf("请输入二叉树的先序遍历,如果某个节点没有子节点,请输入#:\n");
TreeNode* root = createTree();
printf("先序遍历:");
preorderTraversal(root);
printf("\n");
printf("中序遍历:");
inorderTraversal(root);
printf("\n");
printf("后序遍历:");
postorderTraversal(root);
printf("\n");
printf("层序遍历:");
levelOrderTraversal(root);
printf("\n");
return 0;
}
```
注意:为了方便输入,我们假设输入的二叉树数据中不会包含空格。如果需要输入带空格的字符串,可以使用 `fgets()` 函数代替 `scanf()` 函数。
阅读全文