python 建立 搜索树
时间: 2023-08-15 14:14:56 浏览: 46
在Python中,可以使用二叉搜索树(Binary Search Tree)来实现搜索树。二叉搜索树是一种有序的二叉树,其中每个节点的左子树的值都小于该节点的值,右子树的值都大于该节点的值。以下是在Python中建立搜索树的一种方法:
```python
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)
def _insert_recursive(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert_recursive(node.left, key)
else:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert_recursive(node.right, key)
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search_recursive(node.left, key)
return self._search_recursive(node.right, key)
```
使用上述代码,可以通过调用`insert`方法向搜索树中插入节点,通过调用`search`方法来搜索特定的键。这个实现是基于递归的,它会根据键的大小递归地在左子树或右子树中进行搜索。
#### 引用[.reference_title]
- *1* [python-二叉搜索树(BST)](https://blog.csdn.net/weixin_42038527/article/details/119088736)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* *3* [Python 二叉搜索树](https://blog.csdn.net/dta0502/article/details/80800658)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]