(1)输入一数列,建立二叉排序树; (2)对所建立的二叉排序树进行查找操作,找到了就显示,找不到就插入; (3)对所建立的二叉排序树进行删除操作。
时间: 2023-12-19 18:06:37 浏览: 30
好的,您的问题是关于二叉排序树的操作。我可以为您提供一些代码示例和解释来回答您的问题。以下是基于Python的实现:
(1)建立二叉排序树:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
return
curr = self.root
while True:
if val < curr.val:
if curr.left:
curr = curr.left
else:
curr.left = TreeNode(val)
return
else:
if curr.right:
curr = curr.right
else:
curr.right = TreeNode(val)
return
```
(2)对所建立的二叉排序树进行查找操作,找到了就显示,找不到就插入:
```python
class BST:
...
def search(self, val):
curr = self.root
while curr:
if curr.val == val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None
def insert_or_search(self, val):
if self.root is None:
self.root = TreeNode(val)
return self.root
curr = self.root
while True:
if val == curr.val:
return curr
elif val < curr.val:
if curr.left:
curr = curr.left
else:
curr.left = TreeNode(val)
return curr.left
else:
if curr.right:
curr = curr.right
else:
curr.right = TreeNode(val)
return curr.right
```
(3)对所建立的二叉排序树进行删除操作:
```python
class BST:
...
def delete(self, val):
def findMin(node):
curr = node
while curr.left:
curr = curr.left
return curr
def deleteNode(node, val):
if node is None:
return None
if val == node.val:
if not node.left and not node.right:
return None
elif not node.left:
return node.right
elif not node.right:
return node.left
else:
minRight = findMin(node.right)
node.val = minRight.val
node.right = deleteNode(node.right, minRight.val)
elif val < node.val:
node.left = deleteNode(node.left, val)
else:
node.right = deleteNode(node.right, val)
return node
self.root = deleteNode(self.root, val)
```
以上是关于二叉排序树的基本操作,希望对您有所帮助。如果您有其他问题,可以继续提出。