设计算法,将n个数据组成二叉排序树结构,并可以删除其中的一个结点。 输入:数据个数n、n个数据、需要删除的数值value。 输出:原始数据、二叉排序树的中序输出及删除结点value后的结果。
时间: 2024-02-20 22:00:48 浏览: 14
以下是Python实现的算法:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if not root:
return Node(val)
if root.val > val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def inorder(root, res):
if not root:
return
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
def delete(root, val):
if not root:
return root
if root.val > val:
root.left = delete(root.left, val)
elif root.val < val:
root.right = delete(root.right, val)
else:
if not root.left:
return root.right
if not root.right:
return root.left
tmp = root.right
while tmp.left:
tmp = tmp.left
root.val = tmp.val
root.right = delete(root.right, tmp.val)
return root
def build_tree(arr):
root = None
for val in arr:
root = insert(root, val)
return root
n = int(input("请输入数据个数:"))
arr = list(map(int, input("请输入数据:").split()))
value = int(input("请输入需要删除的数值:"))
print("原始数据:", arr)
root = build_tree(arr)
res = []
print("二叉排序树的中序输出:", end="")
inorder(root, res)
print(res)
root = delete(root, value)
res = []
print("删除结点value后的结果:", end="")
inorder(root, res)
print(res)
```
实现思路:
首先定义一个节点类 Node,包含节点的值 val、左子节点 left 和右子节点 right。
接着定义插入节点的函数 insert,如果当前节点为空,则直接插入;如果插入的值小于当前节点的值,则插入到左子树,否则插入到右子树。
定义中序遍历函数 inorder,遍历左子树,访问当前节点,再遍历右子树,将遍历结果存入列表 res 中。
定义删除节点的函数 delete,如果当前节点为空,则直接返回;如果要删除的值小于当前节点的值,则在左子树中递归删除;如果要删除的值大于当前节点的值,则在右子树中递归删除;如果要删除的值等于当前节点的值,则判断是否有左子节点和右子节点,如果没有,则直接删除;如果只有一个子节点,则用子节点替换当前节点;如果有两个子节点,则找到右子树中的最小节点替换当前节点,并在右子树中删除该最小节点。
最后定义建立二叉排序树的函数 build_tree,遍历数组中的每个值,插入到二叉排序树中。
主函数中输入数据个数 n、n 个数据和需要删除的数值 value,建立二叉排序树并输出中序遍历结果,删除结点 value 后再输出中序遍历结果。