用c语言写一个在一棵二叉树中,求以值为X的结点为根结点的子树的深度的程序
时间: 2024-03-13 21:48:20 浏览: 92
用c语言实现二叉树的深度,宽度,相似度的编程
5星 · 资源好评率100%
以下是用C语言实现在二叉树中求以值为X的结点为根结点的子树深度的程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 创建二叉树
struct TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 求以值为x的结点为根结点的子树深度
int subtreeDepth(struct TreeNode* root, int x) {
if (root == NULL) {
return 0;
}
if (root->val == x) {
// 以x为根结点的子树深度等于以左右子树中深度更大的那个子树的深度加1
return 1 + (subtreeDepth(root->left, x) > subtreeDepth(root->right, x) ? subtreeDepth(root->left, x) : subtreeDepth(root->right, x));
}
// 如果当前结点不是x,就递归左右子树查找x
int leftDepth = subtreeDepth(root->left, x);
int rightDepth = subtreeDepth(root->right, x);
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
int main() {
struct TreeNode* root = createTree();
int x;
printf("请输入要查询深度的结点值:");
scanf("%d", &x);
int depth = subtreeDepth(root, x);
printf("以%d为根结点的子树深度为:%d\n", x, depth);
return 0;
}
```
以上程序中,我们首先定义了一个二叉树结构体 `TreeNode`,包含了结点的值 `val`、左子树指针 `left` 和右子树指针 `right`。然后我们用 `createTree` 函数创建了一棵二叉树,通过递归方式实现。最后,我们定义了一个 `subtreeDepth` 函数,用于求以值为 `x` 的结点为根结点的子树深度。如果当前结点是 `x`,那么以 `x` 为根结点的子树深度等于以左右子树中深度更大的那个子树的深度加1;如果当前结点不是 `x`,就递归左右子树查找 `x`。最后,在 `main` 函数中,我们输入要查询深度的结点值 `x`,然后调用 `subtreeDepth` 函数求解,并输出结果。
阅读全文