python二叉树搜索树我没学会
时间: 2023-10-26 20:14:31 浏览: 34
二叉搜索树是一种特殊的二叉树,它的左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值,这样的树就称为二叉搜索树。
在 Python 中实现二叉搜索树,你可以先定义一个节点类,来表示树的节点。每个节点需要包含一个值、左子树和右子树。
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
```
接下来,你需要实现一个二叉搜索树类,来操作树。其中包含插入节点、查找节点和删除节点等方法。
```python
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if self.root is None:
self.root = Node(value)
else:
self._insert(value, self.root)
def _insert(self, value, node):
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self._insert(value, node.left)
elif value > node.value:
if node.right is None:
node.right = Node(value)
else:
self._insert(value, node.right)
def search(self, value):
if self.root is None:
return False
else:
return self._search(value, self.root)
def _search(self, value, node):
if node is None:
return False
elif node.value == value:
return True
elif value < node.value:
return self._search(value, node.left)
else:
return self._search(value, node.right)
def delete(self, value):
if self.root is None:
return False
else:
self.root = self._delete(value, self.root)
def _delete(self, value, node):
if node is None:
return node
elif value < node.value:
node.left = self._delete(value, node.left)
return node
elif value > node.value:
node.right = self._delete(value, node.right)
return node
else:
if node.left is None and node.right is None:
node = None
return node
elif node.left is None:
node = node.right
return node
elif node.right is None:
node = node.left
return node
else:
temp = self._find_min_node(node.right)
node.value = temp.value
node.right = self._delete(temp.value, node.right)
return node
def _find_min_node(self, node):
while node.left is not None:
node = node.left
return node
```
这里的 `_insert`、`_search` 和 `_delete` 方法都是私有方法,是为了防止用户直接调用修改根节点。用户只需调用 `insert`、`search` 和 `delete` 方法即可操作树。
以上就是一个简单的 Python 实现二叉搜索树的代码。