请用python代码回答以下问题按输入顺序建立二叉搜索树,并搜索某一结点,输出其父结点。 输入格式: 输入有三行: 第一行是n值,表示有n个结点; 第二行有n个整数,分别代表n个结点的数据值; 第三行是x,表示要搜索值为x的结点的父结点。 输出格式: 输出值为x的结点的父结点的值。 若值为x的结点不存在,则输出:It does not exist. 若值为x的结点是根结点,则输出:It doesn't have parent.
时间: 2024-02-11 17:04:27 浏览: 27
好的,以下是Python代码实现:
```python
# 定义二叉搜索树节点结构体
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
# 按输入顺序建立二叉搜索树
def build_bst(arr):
root = None
for val in arr:
root = insert(root, val)
return root
# 插入节点到二叉搜索树中
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
root.left.parent = root
else:
root.right = insert(root.right, val)
root.right.parent = root
return root
# 搜索节点并输出其父节点的值
def search(root, x):
if not root:
return "It does not exist."
if root.val == x:
if not root.parent:
return "It doesn't have parent."
else:
return root.parent.val
elif root.val > x:
return search(root.left, x)
else:
return search(root.right, x)
# 读取输入
n = int(input())
arr = list(map(int, input().split()))
x = int(input())
# 建立二叉搜索树
root = build_bst(arr)
# 搜索节点并输出其父节点的值
print(search(root, x))
```
你可以将上述代码复制到Python环境中运行,输入样例数据以检验代码正确性。