创建二叉排序树
时间: 2023-08-21 11:09:13 浏览: 45
二叉排序树,也称为二叉查找树,是一种特殊的二叉树,它满足以下性质:
1. 左子树上所有节点的值均小于它的根节点的值。
2. 右子树上所有节点的值均大于它的根节点的值。
3. 左右子树都是二叉排序树。
下面是一个示例代码,用于创建一个二叉排序树:
```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)
return
curr = self.root
while True:
if val < curr.val:
if not curr.left:
curr.left = TreeNode(val)
break
else:
curr = curr.left
else:
if not curr.right:
curr.right = TreeNode(val)
break
else:
curr = curr.right
def inorder_traversal(self, node):
if not node:
return
self.inorder_traversal(node.left)
print(node.val)
self.inorder_traversal(node.right)
# 示例用法
bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
bst.inorder_traversal(bst.root) # 输出 1 3 5 7 9
```
在上面的代码中,我们定义了一个 `TreeNode` 类来表示树节点,包含节点值、左右子节点。`BST` 类维护了树的根节点,并提供了 `insert()` 方法来插入新节点。在插入新节点时,我们从根节点开始遍历树,根据节点值的大小关系向左或向右走,直到找到一个空的位置插入新节点。最后,我们还提供了 `inorder_traversal()` 方法来进行中序遍历,输出二叉排序树中的所有节点值。