树——二叉搜索树的实现

public class Node{
    private int value;
    private Node leftNode;
    private Node rightNode;
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public Node getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }
    public Node getRightNode() {
        return rightNode;
    }
    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }
    public Node(){
    }
    public Node(int value){
        this.value = value;
    }
}

public class Serach2Tree {

    private Node rootNode;
    
    //加入节点
    public void addNode(int value){
        if(rootNode==null){
            rootNode = new Node(value);
        }else{
            addNode(rootNode,value);
        }
    }
    //递归遍历加入
    private void addNode(Node node,int value){
        if(node==null){
            node = new Node(value);
        }else{
            if(node.getValue()>value){
                if(node.getLeftNode()!=null){
                    addNode(node.getLeftNode(),value);
                }else{
                    node.setLeftNode(new Node(value));
                }
            }else if(node.getValue()<value){
                if(node.getRightNode()!=null){
                    addNode(node.getRightNode(),value);
                }else{
                    node.setRightNode(new Node(value));
                }
            }
        }
    }
    //查找节点
    public Node findNode(int value){
        System.out.println();
        if(rootNode==null){
            return null;
        }else{
            return findNode(rootNode,value);
        }
        
    }
    //递归查找节点
    private Node findNode(Node node,int value){
        
        if(node==null){
            return null;
        }
        System.out.print(node.getValue()+"=>");
        if(node.getValue()==value){
            return node;
        }else {
            Node n = null;
            if(node.getValue()>value){
                n = findNode(node.getLeftNode(),value);
            }
            if(node.getValue()<value){
                n = findNode(node.getRightNode(),value);
            }
            return n;
        }
    }
    
    //删除节点
    public void delete(int value){
        delete(rootNode,value);
    }
    
    //递归查找删除节点
    private void delete(Node node,int value){
        if(node==null){
            return;
        }
        if(node.getValue()>value){
            if(node.getLeftNode()==null){
                return;
            }else{
                if(node.getLeftNode().getValue()==value){
                    if(node.getLeftNode().getLeftNode()==null&&node.getLeftNode().getRightNode()==null){
                        node.setLeftNode(null);
                    }else if(node.getLeftNode().getLeftNode()==null&&node.getLeftNode().getRightNode()!=null){
                        node.setLeftNode(node.getLeftNode().getRightNode());
                    }else if(node.getLeftNode().getLeftNode()!=null&&node.getLeftNode().getRightNode()==null){
                        node.setLeftNode(node.getLeftNode().getLeftNode());
                    }else if(node.getLeftNode().getLeftNode()!=null&&node.getLeftNode().getRightNode()!=null){
                        Node p = node;
                        Node d = node.getLeftNode();
                        Node l = node.getLeftNode().getLeftNode();
                        Node r = node.getLeftNode().getRightNode();
                        if(r.getLeftNode()==null){
                            p.setLeftNode(r);
                            r.setLeftNode(l);
                        }else{
                            Node sp = getRL(r);
                            Node s = sp.getLeftNode();
                            sp.setLeftNode(s.getRightNode());
                            s.setLeftNode(l);
                            s.setRightNode(r);
                            p.setLeftNode(s);
                        }
                    }
                }else{
                    delete(node.getLeftNode(),value);
                }
            }
        }
        if(node.getValue()<value){
            if(node.getRightNode()==null){
                return;
            }else{
                if(node.getRightNode().getValue()==value){
                    if(node.getRightNode().getLeftNode()==null&&node.getRightNode().getRightNode()==null){
                        node.setRightNode(null);
                    }else if(node.getRightNode().getLeftNode()==null&&node.getRightNode().getRightNode()!=null){
                        node.setRightNode(node.getRightNode().getRightNode());
                    }else if(node.getRightNode().getLeftNode()!=null&&node.getRightNode().getRightNode()==null){
                        node.setRightNode(node.getRightNode().getLeftNode());
                    }else if(node.getRightNode().getLeftNode()!=null&&node.getRightNode().getRightNode()!=null){
                        Node p = node;
                        Node d = node.getRightNode();
                        Node l = node.getRightNode().getLeftNode();
                        Node r = node.getRightNode().getRightNode();
                        if(l.getRightNode()==null){
                            p.setRightNode(l);
                            l.setRightNode(r);
                        }else{
                            Node sp = getLR(l);
                            Node s = sp.getRightNode();
                            sp.setRightNode(s.getLeftNode());
                            s.setRightNode(r);
                            s.setLeftNode(l);
                            p.setRightNode(s);
                        }
                    }
                }else{
                    delete(node.getRightNode(),value);
                }
            }
        }
    }
    //递归查找右节点的左子节点树为空的节点
    private Node getRL(Node r){
        if(r.getLeftNode()!=null&&r.getLeftNode().getLeftNode()==null){
            return r;
        }else{
            return getRL(r.getLeftNode());
        }
    }
    //递归查找左节点的右子节点树为空的节点
    private Node getLR(Node l){
        if(l.getRightNode()!=null&&l.getRightNode().getRightNode()==null){
            return l;
        }else{
            return getLR(l.getRightNode());
        }
    }
    
    
    public static void main(String[] args) {
        int[] is = new int[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,55,53,80};
        Serach2Tree serach2Tree = new Serach2Tree();
        for(int i=0;i<is.length;i++){
            serach2Tree.addNode(is[i]);
        }
        serach2Tree.findNode(65);
        serach2Tree.delete(60);
        serach2Tree.findNode(65);
    }
}