利用 Python 语言,实现二叉搜索树
时间: 2024-02-16 14:13:26 浏览: 24
好的,下面是 Python 实现的二叉搜索树代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val:
if not node.left:
node.left = TreeNode(val)
else:
self._insert(node.left, val)
else:
if not node.right:
node.right = TreeNode(val)
else:
self._insert(node.right, val)
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node:
return False
elif node.val == val:
return True
elif val < node.val:
return self._search(node.left, val)
else:
return self._search(node.right, val)
```
在这个实现中,我们定义了一个 `TreeNode` 类来表示二叉搜索树中的每个节点,节点包含一个值以及左右子节点的指针。然后,我们定义了一个 `BST` 类来表示整个二叉搜索树,其中包含一个根节点指针。`BST` 类中定义了插入和搜索节点的方法,每个方法都包含了一个递归的实现。在插入节点时,我们从根节点开始往下查找,找到一个合适的位置插入新节点。在搜索节点时,我们也从根节点开始往下查找,如果找到了则返回 True,否则返回 False。