用C语言写以下程序,包含main函数,用递归的方法实现以下算法: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的叶结点个数; 7.输出二叉树中从每个叶子结点到根结点的路径。
时间: 2023-05-25 07:04:05 浏览: 132
递归算法实现二叉树的各种运算
5星 · 资源好评率100%
请注意,这是一道较为复杂的编程题目,需要一些基本的算法和数据结构知识。以下是参考代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 建立二叉树
TreeNode* buildTree() {
int value;
scanf("%d", &value); // 输入当前结点的值
if (value == -1) { // -1 表示空结点
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode)); // 分配空间
root->value = value;
root->left = buildTree(); // 递归建立左子树
root->right = buildTree(); // 递归建立右子树
return root;
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->value);
inorderTraversal(root->right);
}
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->value);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->value);
}
// 计算深度
int getDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
// 统计叶结点个数
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
// 从叶子结点到根结点的路径
void printPaths(TreeNode* root, int path[], int level) {
if (root == NULL) {
return;
}
path[level] = root->value;
if (root->left == NULL && root->right == NULL) { // 叶子结点
for (int i = level; i >= 0; i--) {
printf("%d ", path[i]);
}
printf("\n");
} else {
printPaths(root->left, path, level+1);
printPaths(root->right, path, level+1);
}
}
int main() {
printf("请输入一棵二叉树,-1表示空结点:\n");
TreeNode *root = buildTree();
printf("中序遍历:");
inorderTraversal(root);
printf("\n");
printf("前序遍历:");
preorderTraversal(root);
printf("\n");
printf("后序遍历:");
postorderTraversal(root);
printf("\n");
printf("深度为:%d\n", getDepth(root));
printf("叶结点个数为:%d\n", countLeaves(root));
printf("从叶子结点到根结点的路径为:\n");
int path[100];
printPaths(root, path, 0);
return 0;
}
```
阅读全文