设计一个算法,在一颗非空二叉排序树bt中求出指定关键字为看的结点的层次C语言完整代码
时间: 2024-02-25 07:58:46 浏览: 134
二叉排序树最近公共祖先
4星 · 用户满意度95%
以下是一个基于递归的算法,可以在一颗非空二叉排序树中求出指定关键字为k的结点的层次的C语言完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义二叉树结点的创建函数
TreeNode* create_node(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 定义二叉排序树的插入函数
void insert_node(TreeNode** root, int val) {
if (*root == NULL) {
*root = create_node(val);
return;
}
if ((*root)->val > val) {
insert_node(&((*root)->left), val);
} else {
insert_node(&((*root)->right), val);
}
}
// 定义查找结点层次的函数
int find_node_level(TreeNode* root, int k, int level) {
if (root == NULL) {
return 0;
}
if (root->val == k) {
return level;
}
if (root->val > k) {
return find_node_level(root->left, k, level+1);
} else {
return find_node_level(root->right, k, level+1);
}
}
int main() {
// 创建一棵二叉排序树
TreeNode* root = NULL;
insert_node(&root, 6);
insert_node(&root, 4);
insert_node(&root, 2);
insert_node(&root, 5);
insert_node(&root, 8);
insert_node(&root, 7);
insert_node(&root, 9);
// 查找结点5的层次
int level = find_node_level(root, 5, 1);
printf("The level of node with value 5 is %d\n", level);
return 0;
}
```
在这个示例中,我们创建了一棵二叉排序树,并在其中插入了一些结点。然后,我们调用find_node_level函数,查找结点5的层次,并将结果输出到控制台。这个示例代码可以在C语言编译器中进行编译,并在控制台中查看结果。
阅读全文