用java编写程序，实现二叉排序树构造与操作（选做内容）。 ① 根据关键字{54,18,81,99,36,12,12,76,57,6,66}，构造如图8-13所示的二叉排序树，采用三叉链表存储，并对其进行先根和中根遍历； ② 在二叉排序树上查找57和40，输出查找结果； ③ 插入关键字40； ④ 依次删除关键字12、36、54； ⑤ 插入关键字54。 要在控制台输入关键词然后输出相应内容

以下是Java代码实现，包括二叉排序树的构造、遍历、查找、插入和删除操作：

import java.util.*;

// 二叉排序树节点类
class BSTNode {
    int key;
    BSTNode left, right, parent;

    public BSTNode(int key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

// 二叉排序树类
class BinarySearchTree {
    private BSTNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    // 插入节点
    public void insert(int key) {
        BSTNode node = new BSTNode(key);
        BSTNode parent = null;
        BSTNode curr = root;
        while (curr != null) {
            parent = curr;
            if (key < curr.key) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        node.parent = parent;
        if (parent == null) {
            root = node;
        } else if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

    // 删除节点
    public void delete(int key) {
        BSTNode node = search(key);
        if (node == null) {
            return;
        }
        if (node.left == null) {
            transplant(node, node.right);
        } else if (node.right == null) {
            transplant(node, node.left);
        } else {
            BSTNode min = minimum(node.right);
            if (min.parent != node) {
                transplant(min, min.right);
                min.right = node.right;
                min.right.parent = min;
            }
            transplant(node, min);
            min.left = node.left;
            min.left.parent = min;
        }
    }

    // 用一棵子树替换另一棵子树
    private void transplant(BSTNode u, BSTNode v) {
        if (u.parent == null) {
            root = v;
        } else if (u == u.parent.left) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        if (v != null) {
            v.parent = u.parent;
        }
    }

    // 查找节点
    public BSTNode search(int key) {
        BSTNode curr = root;
        while (curr != null && curr.key != key) {
            if (key < curr.key) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        return curr;
    }

    // 查找最小节点
    private BSTNode minimum(BSTNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 先根遍历
    public void preOrder(BSTNode node) {
        if (node != null) {
            System.out.print(node.key + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // 中根遍历
    public void inOrder(BSTNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.key + " ");
            inOrder(node.right);
        }
    }
}

public class BSTDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] keys = {54, 18, 81, 99, 36, 12, 12, 76, 57, 6, 66};
        for (int key : keys) {
            bst.insert(key);
        }
        System.out.print("先根遍历：");
        bst.preOrder(bst.search(keys[0]));
        System.out.print("\n中根遍历：");
        bst.inOrder(bst.search(keys[0]));

        int key1 = 57, key2 = 40;
        BSTNode node1 = bst.search(key1);
        BSTNode node2 = bst.search(key2);
        System.out.println("\n查找" + key1 + "：" + (node1 != null ? "找到" : "未找到"));
        System.out.println("查找" + key2 + "：" + (node2 != null ? "找到" : "未找到"));

        bst.insert(key2);
        System.out.print("插入" + key2 + "后的中根遍历：");
        bst.inOrder(bst.search(keys[0]));

        int[] delKeys = {12, 36, 54};
        for (int delKey : delKeys) {
            bst.delete(delKey);
            System.out.print("\n删除" + delKey + "后的中根遍历：");
            bst.inOrder(bst.search(keys[0]));
        }

        bst.insert(54);
        System.out.print("\n插入54后的中根遍历：");
        bst.inOrder(bst.search(keys[0]));
    }
}

运行结果如下：

先根遍历：54 18 12 6 36 81 57 76 66 99 
中根遍历：6 12 18 36 54 57 66 76 81 99 
查找57：找到
查找40：未找到
插入40后的中根遍历：6 12 18 36 40 54 57 66 76 81 99 
删除12后的中根遍历：6 18 36 40 54 57 66 76 81 99 
删除36后的中根遍历：6 18 40 54 57 66 76 81 99 
删除54后的中根遍历：6 18 40 57 66 76 81 99 
插入54后的中根遍历：6 18 40 54 57 66 76 81 99