帮我写一个二叉树查找
时间: 2023-02-16 12:42:47 浏览: 68
二叉查找树(Binary Search Tree, BST)是一种特殊的二叉树,每个节点都满足:
- 若它有左子树,则左子树上所有节点的值均小于它的根节点的值
- 若它有右子树,则右子树上所有节点的值均大于它的根节点的值
以下是一个 Python 实现的二叉查找树类:
```
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
new_node = Node(val)
if not self.root:
self.root = new_node
return
curr = self.root
while curr:
if val < curr.val:
if not curr.left:
curr.left = new_node
return
curr = curr.left
else:
if not curr.right:
curr.right = new_node
return
curr = curr.right
def search(self, val):
curr = self.root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None
```
上述程序实现了二叉查找树的基本操作:插入和查找。
- insert 方法用于向树中插入一个新的值。
- search 方法用于在树中查找一个值,如果找到返回该节点,否则返回 None。