假设二叉排序树中所有结点关键字不同。设计一个程序,求出指定关键字的结点所在的层次
时间: 2023-06-27 09:00:53 浏览: 52
可以使用递归的方法来实现这个程序,具体步骤如下:
1. 如果二叉排序树为空,则指定的关键字不存在,返回0。
2. 如果指定的关键字等于当前结点的关键字,则返回1。
3. 如果指定的关键字小于当前结点的关键字,则递归查找左子树,并将返回值加1。
4. 如果指定的关键字大于当前结点的关键字,则递归查找右子树,并将返回值加1。
下面是具体的实现代码:
```python
def find_node_level(root, key, level=1):
if not root:
return 0
if root.key == key:
return level
elif root.key > key:
return find_node_level(root.left, key, level+1)
else:
return find_node_level(root.right, key, level+1)
```
其中,root 表示二叉排序树的根节点,key 表示指定的关键字,level 表示当前结点所在的层次。在调用函数时,初始的层次应该为1。如果指定的关键字不存在于树中,则返回0。
相关问题
在非空二叉排序树中求出指定关键字的结点的层次写代码
以下是求出指定关键字的结点的层次的 Python 代码:
```python
def find_node_level(root, key):
"""
在非空二叉排序树中查找指定关键字的结点,并返回其层次
"""
level = 1
node = root
while node is not None:
if node.key == key:
return level
elif node.key < key:
node = node.right
else:
node = node.left
level += 1
# 没有找到指定结点,返回 None
return None
```
其中,`root` 表示二叉排序树的根节点,`key` 表示要查找的关键字。算法采用迭代方式,不断遍历二叉排序树,直到找到指定的结点或者遍历到空节点。如果找到指定结点,则返回其层次;否则,返回 None。
在非空二叉排序树中求出指定关键字的结点的层次C语言完整代码
以下是求出指定关键字的结点的层次的 C 语言完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int key;
struct TreeNode *left;
struct TreeNode *right;
};
int find_node_level(struct TreeNode *root, int key) {
/*
* 在非空二叉排序树中查找指定关键字的结点,并返回其层次
*/
int level = 1;
struct TreeNode *node = root;
while (node != NULL) {
if (node->key == key) {
return level;
}
else if (node->key < key) {
node = node->right;
}
else {
node = node->left;
}
level++;
}
// 没有找到指定结点,返回 -1
return -1;
}
int main() {
// 创建二叉排序树
struct TreeNode *root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->key = 5;
root->left = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->left->key = 3;
root->left->left = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->left->left->key = 1;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->left->right->key = 4;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->right->key = 7;
root->right->left = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->right->left->key = 6;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->right->right->key = 8;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 查找指定结点的层次
int level = find_node_level(root, 4);
printf("The level of the node is: %d\n", level);
return 0;
}
```
在此示例代码中,我们创建了一个二叉排序树,并查找了关键字为 4 的结点的层次。注意,如果没有找到指定结点,则返回 -1。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)