1.编写顺序查找程序; 2.编写二分查找程序; 3.编写建立二叉排序树的程序; 4.编写在二叉排序树上的查找、插入、删除结点的程序; 5.编写使二叉排序树中序输出的程序; 6.设计一个选择式菜单,一级菜单形式如下: 查找子系统 **************************************** * 1------顺 序 查 找 * * 2------二 分 查 找 * * 3------二 叉 排 序 树 * * 0------返 回 * **************************************** 请选择菜单号(0--3):。
时间: 2023-07-06 14:37:09 浏览: 51
好的,我已经记下了你的问题。下面是我的回答:
1. 顺序查找程序示例(Python实现):
```python
def sequential_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i
return -1
```
2. 二分查找程序示例(Python实现):
```python
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key:
high = mid - 1
else:
low = mid + 1
return -1
```
3. 建立二叉排序树的程序示例(Python实现):
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert_node(root, val):
if not root:
root = TreeNode(val)
elif root.val > val:
root.left = insert_node(root.left, val)
else:
root.right = insert_node(root.right, val)
return root
```
4. 在二叉排序树上的查找、插入、删除结点的程序示例(Python实现):
```python
def search_node(root, val):
if not root or root.val == val:
return root
elif root.val > val:
return search_node(root.left, val)
else:
return search_node(root.right, val)
def insert_node(root, val):
if not root:
root = TreeNode(val)
elif root.val > val:
root.left = insert_node(root.left, val)
else:
root.right = insert_node(root.right, val)
return root
def delete_node(root, val):
if not root:
return root
if root.val > val:
root.left = delete_node(root.left, val)
elif root.val < val:
root.right = delete_node(root.right, val)
else:
if not root.left:
temp = root.right
root = None
return temp
elif not root.right:
temp = root.left
root = None
return temp
temp = get_min_node(root.right)
root.val = temp.val
root.right = delete_node(root.right, temp.val)
return root
def get_min_node(node):
while node.left:
node = node.left
return node
```
5. 使二叉排序树中序输出的程序示例(Python实现):
```python
def inorder_traversal(root):
if not root:
return []
res = []
res += inorder_traversal(root.left)
res.append(root.val)
res += inorder_traversal(root.right)
return res
```
6. 选择式菜单的设计:
```python
while True:
print("查找子系统")
print("*" * 40)
print("* 1------顺 序 查 找 *")
print("* 2------二 分 查 找 *")
print("* 3------二 叉 排 序 树 *")
print("* 0------返 回 *")
print("*" * 40)
choice = input("请选择菜单号(0--3):")
if choice == "0":
print("退出系统")
break
elif choice == "1":
arr = input("请输入待查找的数组,以逗号分隔:").split(",")
key = input("请输入要查找的关键字:")
index = sequential_search(arr, key)
if index == -1:
print("未找到关键字")
else:
print("关键字在数组中的下标为:", index)
elif choice == "2":
arr = input("请输入有序数组,以逗号分隔:").split(",")
key = input("请输入要查找的关键字:")
index = binary_search(arr, key)
if index == -1:
print("未找到关键字")
else:
print("关键字在数组中的下标为:", index)
elif choice == "3":
root = None
nums = input("请输入要插入的数字,以逗号分隔:").split(",")
for num in nums:
root = insert_node(root, int(num))
print("中序遍历结果为:", inorder_traversal(root))
while True:
print("请选择:1.查找 2.插入 3.删除 0.返回上级菜单")
sub_choice = input("请选择:")
if sub_choice == "0":
break
elif sub_choice == "1":
val = input("请输入要查找的数字:")
node = search_node(root, int(val))
if not node:
print("未找到数字")
else:
print("找到数字:", node.val)
elif sub_choice == "2":
val = input("请输入要插入的数字:")
root = insert_node(root, int(val))
print("中序遍历结果为:", inorder_traversal(root))
elif sub_choice == "3":
val = input("请输入要删除的数字:")
root = delete_node(root, int(val))
print("中序遍历结果为:", inorder_traversal(root))
else:
print("输入有误,请重新输入")
else:
print("输入有误,请重新输入")
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)