任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作。写出源码
时间: 2024-03-05 16:53:57 浏览: 62
好的,下面是二叉排序树的基本操作的源码实现,包括创建、插入、查找和删除节点功能:
```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 not self.root:
self.root = TreeNode(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left:
self._insert(val, node.left)
else:
node.left = TreeNode(val)
else:
if node.right:
self._insert(val, node.right)
else:
node.right = TreeNode(val)
# 查找节点
def find(self, val):
if self.root:
res = self._find(val, self.root)
if res:
return True
else:
return False
else:
return False
def _find(self, val, node):
if not node:
return None
elif node.val == val:
return node
elif val < node.val:
return self._find(val, node.left)
else:
return self._find(val, node.right)
# 删除节点
def delete(self, val):
if not self.root:
return None
else:
self.root = self._delete(val, self.root)
def _delete(self, val, node):
if not node:
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:
# 情况1:该节点没有子节点
if not node.left and not node.right:
node = None
# 情况2:该节点只有一个子节点
elif not node.left:
node = node.right
elif not node.right:
node = node.left
# 情况3:该节点有两个子节点
else:
temp = self._find_min(node.right)
node.val = temp.val
node.right = self._delete(temp.val, node.right)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
```
以上就是二叉排序树的基本操作实现,包括创建、插入、查找和删除节点功能。
阅读全文