1)以先序递归方式创建一棵二叉树; 2)输出二叉树的先序、中序和后序递归遍历下的结点访问次序; 3)计算二叉树的深度和结点个数
时间: 2024-02-29 11:51:06 浏览: 53
下面是C语言实现以上三个要求的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序递归创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 先序递归遍历二叉树
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preOrder(root->left);
preOrder(root->right);
}
// 中序递归遍历二叉树
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%d ", root->val);
inOrder(root->right);
}
// 后序递归遍历二叉树
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->val);
}
// 计算二叉树深度
int depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
// 计算二叉树结点数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
int main() {
printf("请输入二叉树的结点值(-1代表空结点):\n");
TreeNode *root = createTree();
printf("\n先序递归遍历结果为:");
preOrder(root);
printf("\n中序递归遍历结果为:");
inOrder(root);
printf("\n后序递归遍历结果为:");
postOrder(root);
printf("\n二叉树深度为:%d\n", depth(root));
printf("二叉树结点数为:%d\n", countNodes(root));
return 0;
}
```
在该代码中,我们通过递归的方式实现了先序创建二叉树和先序、中序、后序遍历二叉树的函数。同时,我们还实现了计算二叉树深度和结点数的函数。在主函数中,我们首先调用createTree函数创建二叉树,然后分别调用preOrder、inOrder和postOrder函数遍历二叉树,并输出遍历结果。最后,我们调用depth和countNodes函数计算二叉树的深度和结点数,并输出结果。
阅读全文