需要编写函数来实现以下三个功能: 建立有序表,利用二叉排序树的插入算法建立二叉排序树; 在以上二叉排序树中删除某一指定关键字元素; 采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)。
时间: 2024-02-17 22:01:32 浏览: 100
好的,我可以帮您解答这个问题。以下是代码实现:
建立有序表,利用二叉排序树的插入算法建立二叉排序树:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
self._insert(val, node.left)
elif val > node.val:
if node.right is None:
node.right = TreeNode(val)
else:
self._insert(val, node.right)
```
在以上二叉排序树中删除某一指定关键字元素:
```python
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
self._insert(val, node.left)
elif val > node.val:
if node.right is None:
node.right = TreeNode(val)
else:
self._insert(val, node.right)
def delete(self, val):
if self.root is None:
return False
else:
return self._delete(val, self.root)
def _delete(self, val, node):
if node is None:
return node
if val < node.val:
node.left = self._delete(val, node.left)
elif val > node.val:
node.right = self._delete(val, node.right)
else:
if node.left is None:
temp = node.right
del node
return temp
elif node.right is None:
temp = node.left
del node
return temp
temp = self._minValueNode(node.right)
node.val = temp.val
node.right = self._delete(temp.val, node.right)
return node
def _minValueNode(self, node):
current = node
while current.left is not None:
current = current.left
return current
```
采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构):
```python
def binary_search(arr, val):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == val:
return mid
elif arr[mid] < val:
low = mid + 1
else:
high = mid - 1
return -1
```
希望以上代码可以帮到您!
阅读全文