java三叉链表存储二叉排序树并进行增删查改操作，测试代码

以下是Java三叉链表存储二叉排序树并进行增删查改操作的测试代码，供您参考：

class Node {
    int data;
    Node lchild;
    Node rchild;
    Node parent;

    public Node(int data) {
        this.data = data;
        this.lchild = null;
        this.rchild = null;
        this.parent = null;
    }
}

class BSTree {
    private Node root;

    public BSTree() {
        root = null;
    }

    // 查找节点
    public Node search(int data) {
        Node current = root;
        while (current != null && current.data != data) {
            if (data < current.data) {
                current = current.lchild;
            } else {
                current = current.rchild;
            }
        }
        return current;
    }

    // 插入节点
    public void insert(int data) {
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.lchild;
                    if (current == null) {
                        parent.lchild = newNode;
                        newNode.parent = parent;
                        return;
                    }
                } else {
                    current = current.rchild;
                    if (current == null) {
                        parent.rchild = newNode;
                        newNode.parent = parent;
                        return;
                    }
                }
            }
        }
    }

    // 删除节点
    public boolean delete(int data) {
        Node current = search(data);
        if (current == null) {
            return false;
        }
        if (current.lchild == null && current.rchild == null) {
            if (current == root) {
                root = null;
            } else if (current == current.parent.lchild) {
                current.parent.lchild = null;
            } else {
                current.parent.rchild = null;
            }
        } else if (current.lchild == null) {
            if (current == root) {
                root = current.rchild;
            } else if (current == current.parent.lchild) {
                current.parent.lchild = current.rchild;
            } else {
                current.parent.rchild = current.rchild;
            }
            current.rchild.parent = current.parent;
        } else if (current.rchild == null) {
            if (current == root) {
                root = current.lchild;
            } else if (current == current.parent.lchild) {
                current.parent.lchild = current.lchild;
            } else {
                current.parent.rchild = current.lchild;
            }
            current.lchild.parent = current.parent;
        } else {
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (current == current.parent.lchild) {
                current.parent.lchild = successor;
            } else {
                current.parent.rchild = successor;
            }
            successor.lchild = current.lchild;
            successor.lchild.parent = successor;
        }
        return true;
    }

    // 获取后继节点
    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rchild;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.lchild;
        }
        if (successor != delNode.rchild) {
            successorParent.lchild = successor.rchild;
            successor.rchild = delNode.rchild;
            successor.rchild.parent = successor;
        }
        return successor;
    }

    // 中序遍历
    public void inorder() {
        inorder(root);
    }

    private void inorder(Node localRoot) {
        if (localRoot != null) {
            inorder(localRoot.lchild);
            System.out.print(localRoot.data + " ");
            inorder(localRoot.rchild);
        }
    }
}

public class TestBSTree {
    public static void main(String[] args) {
        BSTree bst = new BSTree();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        System.out.println("中序遍历:");
        bst.inorder();

        System.out.println("\n删除节点20:");
        bst.delete(20);
        bst.inorder();

        System.out.println("\n删除节点30:");
        bst.delete(30);
        bst.inorder();

        System.out.println("\n删除节点50:");
        bst.delete(50);
        bst.inorder();
    }
}

运行结果如下：

中序遍历:
20 30 40 50 60 70 80 
删除节点20:
30 40 50 60 70 80 
删除节点30:
40 50 60 70 80 
删除节点50:
40 60 70 80