用c语言在一棵二叉树中,求以值为X的结点为根结点的子树的深度
时间: 2024-03-13 15:48:20 浏览: 67
同样地,在C语言中也可以通过递归遍历二叉树来求解以值为X的结点为根结点的子树的深度。以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 求二叉树深度的函数
int depth(TreeNode *root) {
if (!root) {
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
return left > right ? left + 1 : right + 1;
}
// 求以值为x的结点为根结点的子树的深度
int subtreeDepth(TreeNode *root, int x) {
if (!root) {
return 0;
}
if (root->val == x) {
int left = depth(root->left);
int right = depth(root->right);
return left > right ? left + 1 : right + 1;
}
int left = subtreeDepth(root->left, x);
int right = subtreeDepth(root->right, x);
return left > right ? left : right;
}
int main() {
// 构造一棵二叉树
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 4;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 求以值为3的结点为根结点的子树的深度
int x = 3;
int subDepth = subtreeDepth(root, x);
printf("以值为%d的结点为根结点的子树的深度为%d\n", x, subDepth);
// 释放内存
free(root->right->right);
free(root->right);
free(root->left);
free(root);
return 0;
}
```
注意,在C语言中需要手动释放动态分配的内存,避免内存泄漏。
阅读全文