使用数据结构知识用C语言编写完整的程序完成以下功能:1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数
时间: 2023-11-14 08:18:39 浏览: 108
下面是使用数据结构知识用C语言编写完整程序,实现二叉树的创建、遍历、深度和叶子节点个数的功能。请参考代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode *create_tree() {
int value;
scanf("%d", &value);
if (value == -1) { // 结束标志
return NULL;
}
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = value;
node->left = create_tree();
node->right = create_tree();
return node;
}
// 先序遍历二叉树
void preorder_traversal(TreeNode *node) {
if (node == NULL) {
return;
}
printf("%d ", node->data);
preorder_traversal(node->left);
preorder_traversal(node->right);
}
// 中序遍历二叉树
void inorder_traversal(TreeNode *node) {
if (node == NULL) {
return;
}
inorder_traversal(node->left);
printf("%d ", node->data);
inorder_traversal(node->right);
}
// 后序遍历二叉树
void postorder_traversal(TreeNode *node) {
if (node == NULL) {
return;
}
postorder_traversal(node->left);
postorder_traversal(node->right);
printf("%d ", node->data);
}
// 求二叉树深度
int tree_depth(TreeNode *node) {
if (node == NULL) {
return 0;
}
int left_depth = tree_depth(node->left);
int right_depth = tree_depth(node->right);
return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}
// 求二叉树叶子结点个数
int leaf_count(TreeNode *node) {
if (node == NULL) {
return 0;
}
if (node->left == NULL && node->right == NULL) {
return 1;
}
return leaf_count(node->left) + leaf_count(node->right);
}
int main() {
// 创建二叉树
printf("请输入二叉树每个节点的值,-1表示此节点为空:\n");
TreeNode *root = create_tree();
// 先序遍历二叉树
printf("先序遍历二叉树:\n");
preorder_traversal(root);
printf("\n");
// 中序遍历二叉树
printf("中序遍历二叉树:\n");
inorder_traversal(root);
printf("\n");
// 后序遍历二叉树
printf("后序遍历二叉树:\n");
postorder_traversal(root);
printf("\n");
// 求二叉树深度
printf("二叉树深度为:%d\n", tree_depth(root));
// 求二叉树叶子结点个数
printf("二叉树叶子结点个数为:%d\n", leaf_count(root));
return 0;
}
```
程序运行结果:
```
请输入二叉树每个节点的值,-1表示此节点为空:
1 2 -1 -1 3 4 -1 -1 5 -1 -1
先序遍历二叉树:
1 2 3 4 5
中序遍历二叉树:
2 1 4 3 5
后序遍历二叉树:
2 4 5 3 1
二叉树深度为:3
二叉树叶子结点个数为:3
```
阅读全文