设计算法,将n个数据组成二叉排序树结构,并可以删除其中的一个结点。 输入:数据个数n、n个数据、需要删除的数值value。 输出:原始数据、二叉排序树的中序输出及删除结点value后的结果。
时间: 2024-03-13 21:43:53 浏览: 89
算法思路:
1. 将第一个数据作为二叉排序树的根节点,依次将后面的数据插入到该二叉排序树中。
2. 按照中序遍历的方式输出二叉排序树。
3. 找到需要删除的结点value,如果该结点有两个子节点,那么找到其右子树中的最小值节点,将该最小值节点的值赋值给要删除的结点,然后删除该最小值节点;如果该结点只有一个子节点或没有子节点,那么直接删除该结点。
算法实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insertNode(root, val):
if not root:
root = TreeNode(val)
elif val < root.val:
root.left = insertNode(root.left, val)
else:
root.right = insertNode(root.right, val)
return root
def inorderTraversal(root):
if not root:
return []
res = []
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
def deleteNode(root, val):
if not root:
return None
if val < root.val:
root.left = deleteNode(root.left, val)
elif val > root.val:
root.right = deleteNode(root.right, val)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
tmp = root.right
while tmp.left:
tmp = tmp.left
root.val = tmp.val
root.right = deleteNode(root.right, tmp.val)
return root
n = int(input("请输入数据个数:"))
data = list(map(int, input("请输入n个数据:").split()))
value = int(input("请输入需要删除的数值:"))
root = None
for i in range(n):
root = insertNode(root, data[i])
print("原始数据:", data)
print("二叉排序树的中序输出:", inorderTraversal(root))
root = deleteNode(root, value)
print("删除结点后的结果:", inorderTraversal(root))
```
算法时间复杂度:插入n个数据的时间复杂度为O(nlogn),中序遍历的时间复杂度为O(n),删除结点的时间复杂度为O(logn),因此总时间复杂度为O(nlogn)。
阅读全文