通过python实现修改二叉搜索树插入新节点的put()方法,使得如果待插入节点的键已在树中,就将节点的值更新为新值,而不是用同一个键插入一个新节点
时间: 2023-12-17 09:04:30 浏览: 80
可以通过递归实现这个修改,具体代码如下:
```python
class TreeNode:
def __init__(self, key, value):
self.key = key
self.val = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def put(self, key, value):
self.root = self._put(self.root, key, value)
def _put(self, node, key, value):
if not node:
return TreeNode(key, value)
if key < node.key:
node.left = self._put(node.left, key, value)
elif key > node.key:
node.right = self._put(node.right, key, value)
else:
node.val = value
return node
```
在这里,我们首先检查树是否为空,如果是,则返回一个新的节点。如果节点不为空,则将待插入节点的键与当前节点的键进行比较,如果小于当前节点的键,则递归调用_put方法,并将节点的左子树指针更新为递归调用的结果。如果大于当前节点的键,则递归调用_put方法,并将节点的右子树指针更新为递归调用的结果。如果待插入节点的键与当前节点的键相等,则更新当前节点的值。
这样,我们就实现了修改二叉搜索树插入新节点的put方法,使得如果待插入节点的键已在树中,就将节点的值更新为新值,而不是用同一个键插入一个新节点。
阅读全文