Java数据结构之对二叉树的插入、查找、删除操作

//根节点
    public Node root;
    /**
     * 插入节点
     * @param value
     */
    public void insert(long value){
        //封装节点
        Node node = new Node(value);
        //引用当前节点
        Node current = root;
        //引用父节点
        Node parent;
        //如果root为null，也就是第一插入的时候
        if(root == null){
            root = node;
            return;
        }else {
            while(true) {
                //父节点指向当前节点
                parent = current;
                //如果当前指向的节点大于插入节点，则向左走
                if (current.data > value) {
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = node;
                        return;
                    }
                } else {
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = node;
                        return;
                    }
                }
            }
        }

/**
     * 查找节点
     * @param value
     */
    public Node find(long value){
        //引用当前节点，从根节点开始
        Node current = root;
        while(current.data != value){
            if(current.data > value){
                current = current.leftChild;
            }else{
                current = current.rightChild;
            }
            if(current == null){
                return null;
            }
        }
        return current;
    }

要删除中间节点必须先找到它的中序后继节点进行替换

/**
     * 获得中序后继节点
     */
    public Node getSuccessor(Node deleteNode){
        //中序节点
        Node successor = deleteNode;
        //中序父节点
        Node successorParent = deleteNode;
        //当前节点
        Node current = deleteNode.leftChild;
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        if(successor != deleteNode.rightChild){
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = deleteNode.rightChild;
        }
        return successor;
    }

/**
     * 删除节点
     * @param value
     */
    public Boolean delete(long value){
        //引用当前节点，从根节点开始
        Node current = root;
        //引用当前节点的父节点
        Node parent = root;
        //是否为左节点
        boolean isLeftChild = true;
        while(current.data != value){
            parent = current;
            //进行比较，比较查找值和当前节点的大小
            if(current.data > value){
                current = current.leftChild;
                isLeftChild = true;
            }else {
                current = current.rightChild;
                isLeftChild = false;
            }
            //如果查不到
            if(current == null){
                return false;
            }
        }
        //删除叶子节点，也就是该节点没有子节点
        if(current.leftChild == null && current.rightChild == null){
            if(current == root){
                root = null;
            }
            //判断如果他是他的父节点的左子节点
            else if(isLeftChild){
                parent.leftChild = null;
            }else {
                parent.rightChild = null;
            }
        }else if(current.rightChild == null){
            if(current == root){
                root = current.leftChild;
            }else if(isLeftChild){
                parent.leftChild = current.leftChild;
            }else {
                parent.rightChild = current.leftChild;
            }
        }else if(current.leftChild == null) {
            if (current == root) {
                root = current.rightChild;
            } else if (isLeftChild) {
                parent.leftChild = current.rightChild;
            } else {
                parent.rightChild = current.rightChild;
            }
        }else {
            Node successor = getSuccessor(current);
            if(current == root){
                root = successor;
            }else if(isLeftChild){
                parent.leftChild = successor;
            }else{
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;
        }
        return true;
    }