用c语言请编写以下子函数,并在主函数中分别调用。 子函数1:建立二叉树 子函数2:先序遍历二叉树并输出每个节点的值 子函数3:中序遍历二叉树并输出每个节点的值 子函数4:后序遍历二叉树并输出每个节点的值 子函数5:输出二叉树度为1、度为2、度为0(叶子节点)的个数
时间: 2024-11-06 11:23:29 浏览: 5
在C语言中,我们可以创建一系列功能独立的子函数来处理二叉树的操作。这里是一个简单的例子,我们将使用结构体表示二叉树节点,并提供所需的五个子函数:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 子函数1:建立二叉树
TreeNode* createTree(int arr[], int n) {
if (n <= 0)
return NULL;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = arr[0];
int i = 1;
while (i < n) {
if (arr[i] < root->val) {
root->left = createTree(arr + i, n - i);
} else {
root->right = createTree(arr + i, n - i);
break;
}
i++;
}
return root;
}
// 子函数2:先序遍历
void preOrderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->val);
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
}
// 子函数3:中序遍历
void inOrderTraversal(TreeNode* node) {
if (node != NULL) {
inOrderTraversal(node->left);
printf("%d ", node->val);
inOrderTraversal(node->right);
}
}
// 子函数4:后序遍历
void postOrderTraversal(TreeNode* node) {
if (node != NULL) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->val);
}
}
// 子函数5:计算度为1、2、0的节点数
void countDegree(TreeNode* node, int degree[]) {
if (node == NULL)
return;
degree[0]++;
if (node->left != NULL)
countDegree(node->left, degree);
if (node->right != NULL)
countDegree(node->right, degree);
}
int main() {
// 示例数组用于构建二叉搜索树
int arr[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
int n = sizeof(arr) / sizeof(arr[0]);
// 创建树
TreeNode* root = createTree(arr, n);
// 遍历并打印结果
printf("Preorder traversal: ");
preOrderTraversal(root);
printf("\nInorder traversal: ");
inOrderTraversal(root);
printf("\nPostorder traversal: ");
postOrderTraversal(root);
// 计算节点度并输出
int degrees[3] = {0, 0, 0}; // 度为1、2、0
countDegree(root, degrees);
printf("\nNumber of nodes with degree 1: %d\n", degrees[0]);
printf("Number of nodes with degree 2: %d\n", degrees[1]);
printf("Number of leaf nodes (degree 0): %d\n", degrees[2]);
// 清理内存
free(root);
return 0;
}
```
在这个示例中,我们首先定义了二叉树节点,然后实现了各个遍历和节点度计数的子函数。在`main`函数中,我们创建了一个二叉搜索树并进行了相应的操作。注意,这个程序并没有包含输入和错误处理,实际使用时需要完善这部分内容。
阅读全文