实现二叉排序树查找,步骤是1、定义二叉排序树的查找算法函数。 2、二叉排序树的插入算法函数。 3、建立二叉排序树的插入算法。 4、二叉排序树删除一个结点的操作实现。 5、 打印二叉排序树。
时间: 2023-10-30 14:15:58 浏览: 132
erchashu.rar_中序遍历二叉排序树
好的,我来为您解答如何实现二叉排序树的查找。
1. 定义二叉排序树的查找算法函数
二叉排序树的查找算法函数可以使用递归或迭代方式实现,以下是一个递归实现的示例代码:
```python
def search_bst(root, val):
if not root or root.val == val:
return root
elif root.val > val:
return search_bst(root.left, val)
else:
return search_bst(root.right, val)
```
2. 二叉排序树的插入算法函数
二叉排序树的插入算法函数也可以使用递归或迭代方式实现,以下是一个递归实现的示例代码:
```python
def insert_bst(root, val):
if not root:
return TreeNode(val)
elif root.val > val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
```
3. 建立二叉排序树的插入算法
建立二叉排序树的插入算法可以使用一个循环来不断插入新的节点,以下是一个示例代码:
```python
def build_bst(nums):
if not nums:
return None
root = TreeNode(nums[0])
for i in range(1, len(nums)):
insert_bst(root, nums[i])
return root
```
4. 二叉排序树删除一个结点的操作实现
二叉排序树删除一个结点的操作需要考虑多种情况,包括删除的节点有无子节点、删除的节点只有一个子节点、删除的节点有两个子节点等,以下是一个示例代码:
```python
def delete_bst(root, val):
if not root:
return None
if root.val == val:
if not root.left:
return root.right
if not root.right:
return root.left
if root.left and root.right:
temp = root.right
while temp.left:
temp = temp.left
root.val = temp.val
root.right = delete_bst(root.right, temp.val)
elif root.val > val:
root.left = delete_bst(root.left, val)
else:
root.right = delete_bst(root.right, val)
return root
```
5. 打印二叉排序树
二叉排序树的打印可以使用中序遍历来实现,以下是一个示例代码:
```python
def inorder_traversal(root):
if not root:
return []
res = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
```
可以使用以上函数来打印二叉排序树的所有节点值。
阅读全文