写一个至少十个数的数组,将其中数依次插入树里,实现BST的增删查改以及successor,注意是五个方法
时间: 2024-05-06 16:15:01 浏览: 13
好的,下面是代码实现:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self, root=None):
self.root = root
def insert(self, val):
if not self.root:
self.root = Node(val)
else:
curr = self.root
while curr:
if val < curr.val:
if not curr.left:
curr.left = Node(val)
break
curr = curr.left
else:
if not curr.right:
curr.right = Node(val)
break
curr = curr.right
def delete(self, val):
def get_successor(node):
curr = node.right
while curr.left:
curr = curr.left
return curr
def remove(node, val):
if not node:
return None
if val == node.val:
if not node.left and not node.right:
return None
if not node.left:
return node.right
if not node.right:
return node.left
successor = get_successor(node)
node.val = successor.val
node.right = remove(node.right, successor.val)
elif val < node.val:
node.left = remove(node.left, val)
else:
node.right = remove(node.right, val)
return node
self.root = remove(self.root, val)
def search(self, val):
curr = self.root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None
def update(self, old_val, new_val):
node = self.search(old_val)
if node:
self.delete(old_val)
self.insert(new_val)
def successor(self, val):
node = self.search(val)
if not node:
return None
if node.right:
curr = node.right
while curr.left:
curr = curr.left
return curr.val
else:
parent = None
curr = self.root
while curr != node:
if val < curr.val:
parent = curr
curr = curr.left
else:
curr = curr.right
return parent.val if parent else None
```
我们可以测试一下:
```python
# 创建BST
bst = BST()
# 插入元素
arr = [10, 5, 15, 3, 7, 12, 17, 1, 4, 8]
for val in arr:
bst.insert(val)
# 搜索元素
print(bst.search(7).val) # 7
print(bst.search(9)) # None
# 找后继
print(bst.successor(7)) # 8
print(bst.successor(12)) # 15
print(bst.successor(17)) # None
# 更新元素
bst.update(7, 9)
print(bst.search(7)) # None
print(bst.search(9).val) # 9
# 删除元素
bst.delete(10)
print(bst.search(10)) # None
```