用c语言写一个在一棵二叉树中,求以值为X的结点为根结点的子树的深度的程序,并给出输入输出的数据例子
时间: 2024-03-14 08:43:21 浏览: 63
好的,以下是用 C 语言实现的程序:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int subtreeDepth(struct TreeNode* root, int x) {
if (root == NULL) {
return 0;
}
if (root->val == x) {
return maxDepth(root);
}
int leftDepth = subtreeDepth(root->left, x);
int rightDepth = subtreeDepth(root->right, x);
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->val = 3;
root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->left->val = 4;
root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->right->val = 5;
int x = 2;
printf("Subtree depth of %d: %d\n", x, subtreeDepth(root, x));
return 0;
}
```
程序的输入是一个二叉树的根节点和一个值 X,输出是以值为 X 的节点为根节点的子树的深度。
例如,对于上面程序中的二叉树和 X = 2,输出为:
```
Subtree depth of 2: 2
```
这是因为以 2 为根节点的子树深度为 2。
阅读全文