python创建二叉搜索树
时间: 2023-07-24 16:29:22 浏览: 46
可以使用 Python 实现一个简单的二叉搜索树。
首先,定义一个二叉树节点类,包含节点值、左子树和右子树三个属性:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
```
然后,定义一个二叉搜索树类,包含根节点和插入方法:
```python
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
node = self.root
while True:
if val < node.val:
if not node.left:
node.left = TreeNode(val)
break
else:
node = node.left
else:
if not node.right:
node.right = TreeNode(val)
break
else:
node = node.right
```
在插入方法中,如果根节点为空,则直接创建一个新节点作为根节点;否则,从根节点开始,如果插入的值小于当前节点的值,则判断当前节点的左子树是否为空,如果为空,则将新节点插入到左子树中,否则继续向左子树遍历;如果插入的值大于当前节点的值,则判断当前节点的右子树是否为空,如果为空,则将新节点插入到右子树中,否则继续向右子树遍历。
这样,就可以使用二叉搜索树类来创建一个二叉搜索树,并且插入节点:
```python
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
bst.insert(6)
bst.insert(8)
```
最终创建的二叉搜索树如下所示:
```
5
/ \
3 7
/ \ / \
2 4 6 8
```