用c语言写一段代码完成以下要求,由客户输入二叉树的先序序列和中序序列,用层序遍历输出二叉树数据,并输出二叉树的节点个数及其每个节点的子点个数
时间: 2024-03-17 07:44:02 浏览: 52
关于一个数据结构的一个i算法的描述,是二叉树的遍历问题,只有源代码,但是是可以直接运行的,是用C写的二叉树遍历问题.zip
好的,下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据先序和中序序列构建二叉树
TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if (preorderSize == 0 || inorderSize == 0) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
int i;
for (i = 0; i < inorderSize; i++) {
if (inorder[i] == preorder[0]) {
break;
}
}
root->left = buildTree(preorder + 1, i, inorder, i);
root->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);
return root;
}
// 获取二叉树节点数
int getNodeCount(TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + getNodeCount(root->left) + getNodeCount(root->right);
}
// 获取每个节点的子节点个数
void getNodeChildCount(TreeNode* root, int* childCount) {
if (root == NULL) {
return;
}
if (root->left != NULL) {
childCount[root->val]++;
getNodeChildCount(root->left, childCount);
}
if (root->right != NULL) {
childCount[root->val]++;
getNodeChildCount(root->right, childCount);
}
}
// 层序遍历二叉树
void levelOrder(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("%d ", node->val);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}
int main() {
int n;
printf("请输入二叉树节点个数:");
scanf("%d", &n);
int preorder[n], inorder[n];
printf("请输入二叉树先序序列:");
for (int i = 0; i < n; i++) {
scanf("%d", &preorder[i]);
}
printf("请输入二叉树中序序列:");
for (int i = 0; i < n; i++) {
scanf("%d", &inorder[i]);
}
TreeNode* root = buildTree(preorder, n, inorder, n);
printf("二叉树层序遍历结果为:");
levelOrder(root);
printf("\n");
int nodeCount = getNodeCount(root);
printf("二叉树节点个数为:%d\n", nodeCount);
int childCount[nodeCount];
for (int i = 0; i < nodeCount; i++) {
childCount[i] = 0;
}
getNodeChildCount(root, childCount);
printf("每个节点的子节点个数依次为:");
for (int i = 0; i < nodeCount; i++) {
printf("%d ", childCount[i]);
}
printf("\n");
return 0;
}
```
这段代码中,我们首先定义了一个二叉树的节点结构体,包含节点值、左子节点和右子节点。然后,我们通过先序和中序序列构建二叉树,使用递归的方法,每次找到根节点,然后递归构建左子树和右子树。接着,我们通过递归的方式获取二叉树的节点数,以及每个节点的子节点个数。最后,我们使用队列实现二叉树的层序遍历,并输出结果。
注意,这段代码中假设输入的先序序列和中序序列都是合法的,并且没有重复的节点值。如果输入的序列中存在重复节点值,可能会导致构建的二叉树不唯一。如果输入的序列不合法,可能会导致程序出错。
阅读全文