用c语言写一段代码完成以下要求,由客户输入二叉树的长度(序列的存储位置)、先序序列和中序序列,用层序遍历输出二叉树(例如A在第一层,放第一行,B、C在第二层,放第二行),并输出二叉树的节点个数(节点个数要计算出来),然后客户输入某一个节点,程序输出该节点的子节点个数
时间: 2024-03-17 16:44:35 浏览: 27
好的,我可以帮您完成这个问题。
以下是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int findIdx(char *arr, int start, int end, char val) {
for (int i = start; i <= end; i++) {
if (arr[i] == val) {
return i;
}
}
return -1;
}
TreeNode *buildTree(char *preorder, char *inorder, int start, int end) {
static int preIdx = 0;
if (start > end) {
return NULL;
}
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = preorder[preIdx++];
if (start == end) {
node->left = NULL;
node->right = NULL;
return node;
}
int inIdx = findIdx(inorder, start, end, node->val);
node->left = buildTree(preorder, inorder, start, inIdx - 1);
node->right = buildTree(preorder, inorder, inIdx + 1, end);
return node;
}
int getNodeCount(TreeNode *root) {
if (root == NULL) {
return 0;
}
return getNodeCount(root->left) + getNodeCount(root->right) + 1;
}
void printLevelOrder(TreeNode *root) {
if (root == NULL) {
return;
}
TreeNode *queue[MAX_N];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
int levelSize = rear - front;
for (int i = 0; i < levelSize; i++) {
TreeNode *node = queue[front++];
printf("%c ", node->val);
if (node->left) {
queue[rear++] = node->left;
}
if (node->right) {
queue[rear++] = node->right;
}
}
printf("\n");
}
}
int getChildCount(TreeNode *node) {
if (!node || (!node->left && !node->right)) {
return 0;
}
int count = 0;
if (node->left) {
count++;
}
if (node->right) {
count++;
}
return count;
}
int main() {
char preorder[MAX_N], inorder[MAX_N], target;
int n, len;
printf("请输入二叉树长度、先序序列、中序序列:\n");
scanf("%d%s%s", &n, preorder, inorder);
len = strlen(preorder);
TreeNode *root = buildTree(preorder, inorder, 0, len - 1);
printf("层序遍历:\n");
printLevelOrder(root);
printf("节点个数为:%d\n", getNodeCount(root));
printf("请输入要查询子节点的节点:\n");
scanf(" %c", &target);
TreeNode *node = root;
while (node && node->val != target) {
if (node->val > target) {
node = node->left;
} else {
node = node->right;
}
}
if (!node) {
printf("未找到该节点!\n");
} else {
printf("子节点个数为:%d\n", getChildCount(node));
}
return 0;
}
```
这段代码实现了以下功能:
1. 读取客户输入的二叉树长度、先序序列和中序序列,构建二叉树。
2. 用层序遍历输出二叉树,并输出二叉树的节点个数。
3. 读取客户输入的某一个节点,输出该节点的子节点个数。
希望这段代码能够帮到您!
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)