用C语言实现二叉树,并完成: 1、从键盘输入数据,创建二叉树; 2、计算二叉树的度、高度、叶子结点的个数; 3、按前序、中序、后续遍历二叉树,并输出遍历序列
时间: 2023-12-25 13:05:18 浏览: 198
Hello! 我很高兴能够回答你的问题。让我们开始吧!
对于你的问题,我们可以使用C语言来实现二叉树。以下是代码实现和注释:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树的结构体
typedef struct node {
int value; // 结点的值
struct node *left; // 左子树指针
struct node *right; // 右子树指针
} Node;
// 创建一个新结点的函数
Node* create_node(int value) {
Node* node = (Node*) malloc(sizeof(Node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
// 从键盘输入数据,创建二叉树
Node* create_tree() {
int value;
printf("请输入结点的值(输入 -1 表示该结点为空):\n");
scanf("%d", &value);
if (value == -1) {
return NULL;
}
Node* node = create_node(value);
printf("请按顺序输入结点 %d 的左子树和右子树:\n", value);
node->left = create_tree();
node->right = create_tree();
return node;
}
// 计算二叉树的度
int get_degree(Node* root) {
if (root == NULL) {
return 0;
}
int degree = 0;
if (root->left != NULL) {
degree++;
}
if (root->right != NULL) {
degree++;
}
return degree;
}
// 计算二叉树的高度
int get_height(Node* root) {
if (root == NULL) {
return 0;
}
int left_height = get_height(root->left);
int right_height = get_height(root->right);
return 1 + (left_height > right_height ? left_height : right_height);
}
// 计算二叉树的叶子结点个数
int get_leaf_count(Node* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return get_leaf_count(root->left) + get_leaf_count(root->right);
}
// 按前序遍历二叉树
void preorder_traversal(Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->value);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
// 按中序遍历二叉树
void inorder_traversal(Node* root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->value);
inorder_traversal(root->right);
}
// 按后序遍历二叉树
void postorder_traversal(Node* root) {
if (root == NULL) {
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->value);
}
// 测试
int main() {
Node* root = create_tree();
printf("二叉树的度为:%d\n", get_degree(root));
printf("二叉树的高度为:%d\n", get_height(root));
printf("二叉树的叶子结点个数为:%d\n", get_leaf_count(root));
printf("前序遍历的结果为:");
preorder_traversal(root);
printf("\n");
printf("中序遍历的结果为:");
inorder_traversal(root);
printf("\n");
printf("后序遍历的结果为:");
postorder_traversal(root);
printf("\n");
return 0;
}
```
希望这能帮到你!如果你还有其他问题,请随时问我。
阅读全文