python实现建立二叉树并查找父节点,输入有三行: 第一行是n值,表示有n个结点; 第二行有n个整数,分别代表n个结点的数据值; 第三行是x,表示要搜索值为x的结点的父结点。 输出格式: 输出值为x的结点的父结点的值。 若值为x的结点不存在,则输出:It does not exist.
时间: 2024-03-23 08:39:57 浏览: 20
好的,这里是一个 Python 实现建立二叉搜索树并查找父结点的例子。你可以根据需要进行修改:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, data):
if self.root is None:
self.root = Node(data)
else:
self._insert(data, self.root)
def _insert(self, data, cur_node):
if data < cur_node.data:
if cur_node.left is None:
cur_node.left = Node(data)
else:
self._insert(data, cur_node.left)
elif data > cur_node.data:
if cur_node.right is None:
cur_node.right = Node(data)
else:
self._insert(data, cur_node.right)
def find_parent(self, data):
return self._find_parent(data, self.root)
def _find_parent(self, data, cur_node):
if cur_node is None:
return "It does not exist."
elif cur_node.left is not None and cur_node.left.data == data:
return cur_node.data
elif cur_node.right is not None and cur_node.right.data == data:
return cur_node.data
elif data < cur_node.data:
return self._find_parent(data, cur_node.left)
elif data > cur_node.data:
return self._find_parent(data, cur_node.right)
if __name__ == '__main__':
n = int(input())
nums = list(map(int, input().split()))
x = int(input())
bst = BST()
for num in nums:
bst.insert(num)
ans = bst.find_parent(x)
print(ans)
```
这个例子中,我们首先定义了一个 `Node` 类来表示二叉搜索树中的结点,包含 `data` 值、`left` 左子结点和 `right` 右子结点。然后定义了一个 `BST` 类来表示二叉搜索树,包含 `root` 根结点和 `insert` 插入结点、`find_parent` 查找父结点的方法。在 `insert` 方法中,我们使用了递归的方式来插入结点;在 `find_parent` 方法中,我们使用了递归的方式来查找父结点并返回其值。最后,在主程序中,我们读入输入数据,建立二叉搜索树,并查找要搜索的结点的父结点并输出其值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)