任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作。 实验说明: 二叉排序树存储结构如下: 二叉排序树插入算法伪代码如下:
时间: 2024-05-13 13:19:51 浏览: 105
二叉排序树是一棵二叉树,其中每个节点的左子树节点的值都小于该节点的值,右子树节点的值都大于该节点的值。
插入操作的伪代码如下:
```
// 插入一个值为value的节点
insert(value):
if root is NULL:
// 如果树为空,则插入为根节点
root = new Node(value)
else:
// 从根节点开始遍历,找到合适的位置插入
current = root
while current is not NULL:
if value < current.value:
// 插入节点的值小于当前节点,向左子树遍历
if current.left is NULL:
// 如果左子树为空,则插入为左子节点
current.left = new Node(value)
return
else:
current = current.left
else:
// 插入节点的值大于等于当前节点,向右子树遍历
if current.right is NULL:
// 如果右子树为空,则插入为右子节点
current.right = new Node(value)
return
else:
current = current.right
```
查找操作也很简单,从根节点开始遍历,如果找到了相应的节点就返回,否则返回空值。删除操作稍微复杂一些,需要分情况讨论。
如果要删除的节点没有子节点,直接删除即可;如果要删除的节点只有一个子节点,则用其子节点替代该节点;如果要删除的节点有两个子节点,则需要找到该节点的前驱或后继节点来代替该节点。具体实现可以参考下面的伪代码:
```
// 删除值为value的节点
delete(value):
// 查找要删除的节点
current = root
parent = NULL
while current is not NULL and current.value != value:
parent = current
if value < current.value:
current = current.left
else:
current = current.right
if current is NULL:
// 没有找到要删除的节点
return
if current.left is NULL and current.right is NULL:
// 要删除的节点没有子节点
if current == root:
// 如果要删除的节点是根节点
root = NULL
else:
if parent.left == current:
parent.left = NULL
else:
parent.right = NULL
else if current.left is NULL or current.right is NULL:
// 要删除的节点只有一个子节点
if current.left is not NULL:
child = current.left
else:
child = current.right
if current == root:
// 如果要删除的节点是根节点
root = child
else:
if parent.left == current:
parent.left = child
else:
parent.right = child
else:
// 要删除的节点有两个子节点
// 找到前驱节点
predecessor = current.left
while predecessor.right is not NULL:
predecessor_parent = predecessor
predecessor = predecessor.right
// 用前驱节点替代要删除的节点
current.value = predecessor.value
// 删除前驱节点
if predecessor_parent.left == predecessor:
predecessor_parent.left = predecessor.left
else:
predecessor_parent.right = predecessor.left
```
这些操作都可以在 $O(h)$ 的时间内完成,其中 $h$ 是树的高度。如果树平衡,则 $h$ 为 $log_2(n)$,其中 $n$ 是树中节点的数量。
阅读全文