在C语言的环境下,用递归的方法实现以下算法,以二叉链表表示二叉树,建立一棵二叉树,输出二叉树的先序、中序和后序遍历结果,计算二叉树的深度,统计二叉树的结点个数,统计二叉树的叶结点个数,统计二叉树的度为1的结点个数,输出二叉树中从每个叶子结点到根结点的路径。
时间: 2023-12-01 07:02:34 浏览: 83
你的问题是:在 C 语言中使用递归实现二叉树的各种操作以及路径输出。
好的,让我来回答你的问题。下面是递归实现的一些函数,可以用于建立二叉树、遍历二叉树、计算二叉树深度、统计节点数、统计叶节点数、统计度为1的节点数,并输出根节点到叶节点的路径。
首先,定义二叉树节点的结构体:
```
typedef struct binary_tree_node {
int value;
struct binary_tree_node* left;
struct binary_tree_node* right;
} BinaryTreeNode;
```
接下来,是递归实现的函数:
1. 建立二叉树
```
BinaryTreeNode* create_binary_tree() {
int value;
printf("请输入节点值(-1表示空节点):");
scanf("%d", &value);
if (value == -1) {
return NULL;
}
BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
node->value = value;
printf("请输入 %d 的左子树:\n", value);
node->left = create_binary_tree();
printf("请输入 %d 的右子树:\n", value);
node->right = create_binary_tree();
return node;
}
```
2. 先序遍历
```
void preorder_traversal(BinaryTreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->value);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
```
3. 中序遍历
```
void inorder_traversal(BinaryTreeNode* root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->value);
inorder_traversal(root->right);
}
```
4. 后序遍历
```
void postorder_traversal(BinaryTreeNode* root) {
if (root == NULL) {
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->value);
}
```
5. 计算二叉树深度
```
int binary_tree_depth(BinaryTreeNode* root) {
if (root == NULL) {
return 0;
}
int left_depth = binary_tree_depth(root->left);
int right_depth = binary_tree_depth(root->right);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
```
6. 统计节点数
```
int count_nodes(BinaryTreeNode* root) {
if (root == NULL) {
return 0;
}
return count_nodes(root->left) + count_nodes(root->right) + 1;
}
```
7. 统计叶节点数
```
int count_leaf_nodes(BinaryTreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return count_leaf_nodes(root->left) + count_leaf_nodes(root->right);
}
```
8. 统计度为1的节点数
```
int count_degree_1_nodes(BinaryTreeNode* root) {
if (root == NULL) {
return 0;
}
int degree = 0;
if (root->left != NULL) {
degree++;
}
if (root->right != NULL) {
degree++;
}
return degree == 1 ? 1 + count_degree_1_nodes(root->left) + count_degree_1_nodes(root->right) :
count_degree_1_nodes(root->left) + count_degree_1_nodes(root->right);
}
```
9. 输出根节点到叶节点的路径
```
void print_path(BinaryTreeNode* root, int* path, int top) {
if (root == NULL) {
return;
}
path[top++] = root->value;
if (root->left == NULL && root->right == NULL) {
printf("路径:");
for (int i = 0; i < top; i++) {
printf("%d ", path[i]);
}
printf("\n");
} else {
print_path(root->left, path, top);
print_path(root->right, path, top);
}
}
```
至此,递归实现的二叉树函数已经完成。
阅读全文