找到先根序列中第K个结点,给出C语言
时间: 2024-10-07 18:08:45 浏览: 15
在C语言中,找到二叉搜索树(BST)的先序遍历序列中的第K个节点通常需要借助迭代或递归的方式来解决。这里提供一个基于递归的解决方案:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序遍历函数,返回第K个节点指针
TreeNode* findKthNode(TreeNode* root, int k) {
if (root == NULL || k <= 0) { // 检查根节点为空或k值无效的情况
return NULL;
}
// 递归查找左子树
TreeNode* left = findKthNode(root->left, k);
if (left != NULL) {
return left; // 如果k在左子树,直接返回
} else {
// 如果k在当前节点或右子树,则k -= 已访问的节点数(根节点)
k--;
// 如果k等于0,说明找到了第K个节点,返回当前节点
if (k == 0) {
return root;
} else {
// 继续在右子树查找
return findKthNode(root->right, k);
}
}
}
int main() {
// 示例用法
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
// 初始化你的二叉搜索树...
int k;
printf("请输入你要找的第K个节点的位置:");
scanf("%d", &k);
TreeNode* result = findKthNode(root, k);
if (result) {
printf("第 %d 个节点的值是:%d\n", k, result->val);
} else {
printf("找不到第 %d 个节点.\n", k);
}
return 0;
}
```
在这个程序中,`findKthNode`函数会按照先序遍历的方式递归地查找BST中的第K个节点。用户输入K值后,主函数会调用这个函数并打印结果。
阅读全文