编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值,用c++编写
时间: 2023-03-19 16:21:45 浏览: 296
以下是使用C语言编写的递归算法,可以在二叉树中查找先序序列中第k个位置的节点,并返回该节点的值:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int findKthNode(struct TreeNode* root, int k) {
if (root == NULL || k <= 0) {
return 0; // 无效输入
}
static int count = 0; // 使用静态变量计数
if (count < k) {
int val = findKthNode(root->left, k);
if (count < k) {
count++;
if (count == k) {
return root->val; // 找到第k个节点
}
val = findKthNode(root->right, k);
}
return val;
}
return 0; // 超过了第k个节点
}
int main() {
struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode *left = malloc(sizeof(struct TreeNode));
left->val = 2;
left->left = NULL;
left->right = NULL;
struct TreeNode *right = malloc(sizeof(struct TreeNode));
right->val = 3;
right->left = NULL;
right->right = NULL;
root->left = left;
root->right = right;
int k = 2;
int val = findKthNode(root, k);
printf("第%d个节点的值是%d\n", k, val);
free(left);
free(right);
free(root);
return 0;
}
```
这个递归算法的核心是使用一个静态变量count来计数,每当访问一个节点时就将count加1。当count等于k时,就找到了第k个节点,返回其值。如果count大于k,则说明超过了第k个节点,返回0表示未找到。如果找到了第k个节点,就不再继续访问左右子树,从而实现了查找先序序列中第k个位置的节点的功能。
阅读全文