已知二叉树采用二叉链存储结构存储,请用C语言设计一个算法,求该二叉树中距离根结点最近的叶子结点。
时间: 2024-11-09 11:30:06 浏览: 81
在C语言中,我们可以设计一个递归算法来解决这个问题。首先,我们需要定义二叉链表节点的数据结构,并提供一个辅助函数来检查当前节点是否是叶子节点。然后,主函数可以遍历二叉树,找到最接近根节点的叶子节点。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉链表节点
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 辅助函数判断是否为叶子节点
int isLeaf(TreeNode* node) {
return (node->left == NULL && node->right == NULL);
}
// 主函数寻找最近的叶子节点
TreeNode* findNearestLeaf(TreeNode* root) {
if (root == NULL) {
return NULL; // 如果为空,直接返回
}
if (isLeaf(root)) { // 如果当前节点是叶子节点,直接返回
return root;
} else {
// 否则,分别在左子树和右子树寻找
TreeNode* nearestLeft = findNearestLeaf(root->left);
TreeNode* nearestRight = findNearestLeaf(root->right);
// 如果左子树有结果,更新最近叶子的距离
if (nearestLeft != NULL && (nearestRight == NULL || distanceToRoot(nearestLeft) < distanceToRoot(nearestRight))) {
return nearestLeft;
} else if (nearestRight != NULL) {
// 右子树有结果,返回它
return nearestRight;
}
}
}
// 假设distanceToRoot是一个计算节点到根节点距离的函数,可以根据实际需求实现
int distanceToRoot(TreeNode* node) {
// 这里只是一个假设,需要根据实际情况实现,例如递归计数或者利用已有的高度信息
return 0;
}
int main() {
// 初始化你的二叉树实例...
TreeNode* tree = ...;
TreeNode* nearestLeaf = findNearestLeaf(tree);
if (nearestLeaf) {
printf("最近的叶子节点值为:%d\n", nearestLeaf->val);
} else {
printf("找不到最近的叶子节点。\n");
}
return 0;
}
阅读全文