1.编写顺序查找程序; 2.编写二分查找程序; 3.编写建立二叉排序树的程序; 4.编写在二叉排序树上的查找、插入、删除结点的程序; 5.编写使二叉排序树中序输出的程序; 6.设计一个选择式菜单,一级菜单形式如下: 查找子系统 **************************************** * 1------顺 序 查 找 * * 2------二 分 查 找 * * 3------二 叉 排 序 树 * * 0------返 回 * **************************************** 请选择菜单号(0--3):。
时间: 2023-07-06 22:37:09 浏览: 97
编写完整的程序实现顺序的建立、查找、插入、删除等基本操作
好的,这是一个比较复杂的问题,需要较长的代码实现。以下是一个可能的Java实现,供您参考:
```
import java.util.Scanner;
// 定义二叉排序树结点类
class BSTNode {
int key;
BSTNode left;
BSTNode right;
public BSTNode(int key) {
this.key = key;
left = null;
right = null;
}
}
// 定义二叉排序树类
class BST {
private BSTNode root;
public BST() {
root = null;
}
// 插入结点
public void insert(int key) {
root = insert(root, key);
}
private BSTNode insert(BSTNode node, int key) {
if (node == null) {
node = new BSTNode(key);
return node;
}
if (key < node.key) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
return node;
}
// 删除结点
public void delete(int key) {
root = delete(root, key);
}
private BSTNode delete(BSTNode node, int key) {
if (node == null) {
return node;
}
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else {
if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
BSTNode temp = findMin(node.right);
node.key = temp.key;
node.right = delete(node.right, temp.key);
}
}
return node;
}
private BSTNode findMin(BSTNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// 查找结点
public boolean search(int key) {
return search(root, key);
}
private boolean search(BSTNode node, int key) {
if (node == null) {
return false;
}
if (key == node.key) {
return true;
} else if (key < node.key) {
return search(node.left, key);
} else {
return search(node.right, key);
}
}
// 中序遍历输出
public void inorder() {
inorder(root);
}
private void inorder(BSTNode node) {
if (node != null) {
inorder(node.left);
System.out.print(node.key + " ");
inorder(node.right);
}
}
}
// 主程序
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BST bst = new BST();
int choice = -1;
while (choice != 0) {
// 显示菜单
System.out.println("查找子系统");
System.out.println("****************************************");
System.out.println("* 1------顺 序 查 找 *");
System.out.println("* 2------二 分 查 找 *");
System.out.println("* 3------二 叉 排 序 树 *");
System.out.println("* 0------返 回 *");
System.out.println("****************************************");
System.out.print("请选择菜单号(0--3):");
choice = scanner.nextInt();
switch (choice) {
case 1:
// 顺序查找
System.out.print("请输入要查找的数:");
int key = scanner.nextInt();
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
boolean found = false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
found = true;
break;
}
}
if (found) {
System.out.println("找到了");
} else {
System.out.println("没找到");
}
break;
case 2:
// 二分查找
System.out.print("请输入要查找的数:");
key = scanner.nextInt();
arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int low = 0;
int high = arr.length - 1;
found = false;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
found = true;
break;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (found) {
System.out.println("找到了");
} else {
System.out.println("没找到");
}
break;
case 3:
// 二叉排序树
System.out.print("请输入要插入的数(以0结束):");
key = scanner.nextInt();
while (key != 0) {
bst.insert(key);
System.out.print("请输入要插入的数(以0结束):");
key = scanner.nextInt();
}
System.out.print("请输入要查找的数:");
key = scanner.nextInt();
found = bst.search(key);
if (found) {
System.out.println("找到了");
} else {
System.out.println("没找到");
}
System.out.print("请输入要删除的数:");
key = scanner.nextInt();
bst.delete(key);
bst.inorder();
System.out.println();
break;
case 0:
// 返回
break;
default:
System.out.println("输入错误,请重新输入");
break;
}
}
scanner.close();
}
}
```
阅读全文