假设二叉排序树中所有结点关键字不同。设计一个程序,求出指定关键字的结点所在的层次
时间: 2023-06-27 22:00:53 浏览: 80
数据结构课程设计建立二叉树并求指定结点路径程序源代码.doc
可以使用递归的方法来实现这个程序,具体步骤如下:
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。
阅读全文