java 二叉树的增删查

package binarytree0804;

import lombok.Data;

@Data
public class Node {

    private Integer data;

    private Node left;

    private Node right;

}

package binarytree0804;

public class BinaryTree {


    public static Node insert(Node node, Node root) {
        if (node.getData() < root.getData()) {
            if (root.getLeft() == null) {
                root.setLeft(node);
                return root;
            }
            insert(node,root.getLeft());
        }
        if (node.getData() > root.getData()) {
            if (root.getRight() == null) {
                root.setRight(node);
                return root;
            }
            insert(node,root.getRight());
        }
        return null;
    }

    public static Node search(Node node,Node root) {
        if (node.getData() == root.getData()) {
            return root;
        }

        if (node.getData() < root.getData()) {
            if (root.getLeft() == null) {
                return null;
            }
            return search(node,root.getLeft());
        }
        if (node.getData() > root.getData()) {
            if (root.getRight() == null) {
                return null;
            }
            return search(node,root.getRight());
        }
        return null;
    }

    public static Node delete(Node node,Node root) {
        Node sn = search(node,root);
        if ( sn == null) {
            return null;
        }

        if (sn.getLeft() != null && sn.getRight() != null) {
            Node cn = sn.getLeft();
            sn.setData(sn.getRight().getData());
            sn.setLeft(sn.getRight().getLeft());
            sn.setRight(sn.getRight().getRight());
            insert(cn,sn);
            return sn;
        }

        if (sn.getLeft() != null) {
            sn.setRight(sn.getLeft().getRight());
            sn.setData(sn.getLeft().getData());
            sn.setLeft(sn.getLeft().getLeft());
            return sn;
        }

        if (sn.getRight() != null) {
            sn.setLeft(sn.getRight().getLeft());
            sn.setData(sn.getRight().getData());
            sn.setRight(sn.getRight().getRight());
            return sn;
        }
        sn.setData(null);
        clear(root);
        return sn;
    }

    public static void clear(Node root){
        if (root != null) {
            if (root.getLeft() != null) {
                if (root.getLeft().getData() == null) {
                    root.setLeft(null);
                }
                clear(root.getLeft());
            }
            if (root.getRight() != null) {
                if (root.getRight().getData() == null) {
                    root.setRight(null);
                }
                clear(root.getRight());
            }
        }

    }


    public static void main(String[] args) {
        Node root = new Node();
        root.setData(9);

        Node n1 = new Node();
        n1.setData(4);
        insert(n1,root);

        Node n2 = new Node();
        n2.setData(11);
        insert(n2,root);

        Node n4 = new Node();
        n4.setData(12);
        insert(n4,root);

        Node n3 = new Node();
        n3.setData(2);
        insert(n3,root);

        Node n5 = new Node();
        n5.setData(10);
        insert(n5,root);

        System.out.println(root);
        System.out.println(delete(n5,root));
        System.out.println(root);

        System.out.println(search(n4,root));


    }

}