java实现普通二叉树增删改查（通过实现Comparable比较器接口实现二叉树的k值的泛型的比较）

//定义一棵二叉树
public class Tree {
    //二叉树的结点
    class TreeNode implements Comparable {       //让节点实现比较器接口
        K k; //结点的k值
        V v;//结点的v值
        TreeNode left;//结点的左节点（连接下一个结点）
        TreeNode right;//结点的右节点（连接下一个结点）

        public TreeNode(K k, V v, TreeNode left, TreeNode right) {
            this.k = k;
            this.v = v;
            this.left = left;
            this.right = right;
        }


        @Override
        public int compareTo(K k) {   //实现比较器的比较方法

            if (k instanceof Integer) {
                return ((Integer) k).compareTo(((Integer) this.k));
                //如果k是整型 就调用Integer类型写好的比较方法  如果传过来的k大于当前节点的k,就返回一个大于0的值。
            } else if (k instanceof String) {
                return ((String) k).compareTo((String) this.k);
                // 如果k是字符串类型 就调用String类型写好的比较方法
            }

            return 0; //其实return 0在这里不起作用 因为key一般都为整型和字符串类型 ，已经满足上面的条件了。一般Key不会存对象。
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "k=" + k +
                    ", v=" + v +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }

    }

    private TreeNode root;  //根节点

    public Tree() {
        this.root = new TreeNode(null, null, null, null);  //初始化

    }

    public void add(K k, V v) {

        if (root.k == null) {
            root = new TreeNode<>(k, v, null, null);
        } else {
            root = addNode(k, v, root);       //根节点不为空，就去addNode()方法去添加相应，addNode()方法是为了递归而实现的
        }

    }

    public TreeNode addNode(K k, V v, TreeNode node) {
        int index = node.compareTo(k);
        if (index < 0) {
            if (node.left == null) {
                node.left = new TreeNode(k, v, null, null);
            } else {
                node.left = addNode(k, v, node.left);
            }
        }
        if (index > 0) {
            if (node.right == null) {
                node.right = new TreeNode(k, v, null, null);
            } else {
                node.right = addNode(k, v, node.right);
            }
        }
        //如果index==0 根据实际业务 看是替换value值还是其他的值
        return node;
    }

    public void outFirst() {    //先序遍历
        if (root.k == null)
            System.out.println("为空树,无法进行先序遍历");
        else {
            outFirst(root);
            System.out.println();
        }
    }

    public void outFirst(TreeNode node) {
        if (node == null)
            return;
        System.out.print(node.v + "  ");
        outFirst(node.left);
        outFirst(node.right);
    }

    public void outCenter() {    //中序遍历
        if (root.k == null)
            System.out.println("为空树,无法进行中序遍历");
        else {
            outCenter(root);

            System.out.println();
        }
    }

    public void outCenter(TreeNode node) {
        if (node == null)
            return;

        outCenter(node.left);
        System.out.print(node.v + "  ");
        outCenter(node.right);
    }

    public void outLast() {    //后序遍历
        if (root.k == null)
            System.out.print("为空树,无法进行后序遍历");
        else {
            outLast(root);
            System.out.println();
        }
    }

    public void outLast(TreeNode node) {  //后续遍历
        if (node == null)
            return;
        outLast(node.left);

        outLast(node.right);
        System.out.print(node.v + "  ");
    }

    public V getValue(K k) {
        V v = null;
        if (root.k == null) {
            System.out.println("二叉树为空，没有相应的Value值");
        } else {
            v = findValue(k, root, v);  //看能否找到 找到返回v 找不到返回Null
        }
        return v;
    }

    public V findValue(K k, TreeNode node, V v) {
        if (node == null) {
            System.out.println("二叉树中不存在该k");
            return null;
        }
        int index = node.compareTo(k);

        if (index > 0) {
            v = (V) findValue(k, node.right, v);
        } else if (index < 0) {
            v = (V) findValue(k, node.left, v);
        } else {
            return node.v;
        }
        return v;
    }

    public  boolean delete(K k){
        boolean bool=false;
        if(root.k==null){
            System.out.println("二叉树为空,无法删除节点");
            return  false;
        }else {
            TreeNode curr = root;
         bool=   find(k,root,curr);
        }
        return  bool;
    }
    public  boolean find(K k,TreeNode node,TreeNode curr){
          boolean bool=false;
          if(node==null){
              System.out.println("无法找到此k值");
              return  false;
          }
         int index = node.compareTo(k);
        if (index > 0) {
            curr=node;
         bool= find(k,node.right,curr);
        } else if (index < 0) {
            curr=node;
         bool=   find(k,node.left,curr);
        } else {
          bool=  deleteNode(k,node,curr);
        }
           return  bool;
    }

    private boolean deleteNode(K k, TreeNode node, TreeNode curr) {
        String from="";
        if (Objects.equals(curr.left,node) ){
            from = "左";
        } else if(Objects.equals(curr.right,node)) {
            from = "右";
        }else if (Objects.equals(node,curr)){   //根节点
            from = "根";
        }
        if (node.left == null && node.right == null) { //叶子节点
            if (from.equals("左")) {
                curr.left = null;
            }
            else if(from.equals("右")){
                curr.right=null;
            }else{   //根
                System.out.println("删除节点为根节点,且没有后继结点。删除成功,此时二叉树为空。");
                root=new TreeNode<>(null,null,null,null);
                return true;
            }
        }else if(node.left!=null&&node.right==null){
              if(from.equals("左")){
                  curr.left=node.left;
              }
              else if(from.equals("右")){
                  curr.right=node.left;
              }else{
                  root=node.left;
              }
        }else if(node.left==null&&node.right!=null){  //被删除节点的左节点为空 有节点不为空 直接删 接右节点的
            if(from.equals("左")){
                curr.left=node.right;
            }
            else if(from.equals("右")){
                curr.right=node.right;
            }else {
                root=node.right;
            }
        }else{   //当被删除节点的左节点、右节点均有值时，拿右节点的最小值来替换
              TreeNode t;
            if(node.right.left==null){
                t=node.right;
                node.right=null;
            }else {
                 t = findMin(node.right.left, node.right);
            }
             node.k=t.k;
             node.v=t.v;
        }
          return  true;
    }

    private TreeNode findMin(TreeNode node,TreeNode curr) {
        TreeNode t=null;
        if (node.left==null)
        {
            t=node;
         curr.left=null;
//            node=null;
            return  t;
        }
        else {
            curr=node;
          t=  findMin(node.left,curr);

        }
        return  curr;

    }
}