写出二叉排序树的插入算法的代码。要求如下:设待插入结点的关键码为key,为将其插入,先要在二叉排序树中进行查找,若查找成功,按二叉排序树定义,待插入结点已存在,不用插入;查找不成功时,则插入之。因此,新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。
时间: 2024-02-17 11:01:49 浏览: 81
代码实现了二叉树的生成和搜索 希望对正在学习算法的同学们提供便利
好的,下面是二叉排序树的插入算法的代码实现,符合你的要求:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert_bst(root, key):
if not root: # 若查找树为空,插入新结点
return TreeNode(key)
if key == root.val: # 若相等,不用插入
return root
elif key < root.val: # 当给key小于根结点关键码,插入将在以左子女为根的子树上继续进行
root.left = insert_bst(root.left, key)
else: # 当给key大于根结点关键码,插入将在以右子女为根的子树上继续进行
root.right = insert_bst(root.right, key)
return root
```
其中,`root`表示二叉排序树的根节点,`key`表示要插入的关键字。如果插入成功,则返回二叉排序树的根节点;如果插入失败,则返回`None`。如果要插入的关键字已经存在于二叉排序树中,则不进行插入操作。如果要插入的关键字不存在于二叉排序树中,则将其作为叶子节点插入到合适的位置上。
阅读全文