二叉搜索树（TreeMapTreeSet）

1.概念

TreeMap&TreeSet都是有序的集合都是基于二叉搜索树来实现的
二叉搜索树：是一种特殊的二叉树
若左子树不为空，则左子树上的所有节点都小于根节点
若右子树不为空，则右子树上的所有节点都大于根节点
所有左右子树都满足这个条件

2.二叉搜索树的底层代码实现

(1)首先构建二叉树

 public class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node root;

(2)实现插入功能；

分两种情况树是否为空树
当子树为空树直接插入
当子树不为空按照条件限制进行插入

public void cha(int val) {
        Node cut = new Node(val);
        if (root == null) {
            root = cut;
        }
        Node cur = root;
        Node parter = null;
        while (cur != null) {
            if (cut.val > cur.val) {
                parter = cur;
                cur = cur.right;
            } else if (val == cur.val) {//如果树中已经含有val数据则直接退出
                return;
            } else {
                parter = cur;
                cur = cur.left;
            }
        }
        if (parter.val < cut.val) {//不能使用parter.left(right)！=null去判断两边都是null直接后续插入不了
            parter.right = cut;
        } else {
            parter.left = cut;
        }
    }

插入第一张图1~9测试一下

   public static void main(String[] args) {
        int []arr={5,3,4,1,7,8,2,6,0,9};
        BinarySearchTree binarySearchTree=new BinarySearchTree();
        for (int i=0;i< arr.length;i++){
            binarySearchTree.cha(arr[i]);
        }
    }

(3)实现查找

若根节点不为空
当根节点.val==val 返回true
当根节点.val>val 去左子树找
当根节点.val<val 去右子树找

 public boolean jc(int val) {
        Node cur = root;
        while (cur != null) {
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                return true;
            }
        }
        return false;
    }

(4)删除（重点）

设删除节点为cur，删除节点的双亲节点为parter
分三大方向
(一）：当cur.left==null

1.当cur==root时root=root.right

2.cur!=null时
当parter.left==cur
parte.left=cur.right;

当parter.right==cur
parte.right=cur.right;

(二):当cur.right==null

1.当cur==root时root=root.left

2.cur!=null时
当parter.left==cur
parte.left=cur.left;

当parter.right==cur
parte.right=cur.left;
(三)cur.left!=null&&cur.right!=null
需要使⽤替换法进⾏删除，即在它的右⼦树中寻找中序下的第⼀个结点(关键码最⼩)，⽤它的值填补到被删除节点中，再来处理该结点的删除问题

代码：

 public void remove(int val) {
        Node cut = new Node(val);
        Node cur = root;
        Node parter = null;
        while (cur != null) {
            if (cut.val > cur.val) {
                parter = cur;
                cur = cur.right;
            } else if (val < cur.val) {
                parter = cur;
                cur = cur.left;
            } else {
                delet(parter,cur);
                return;
            }
        }
    }
    public void delet(Node parter,Node cur){
      if(cur.right==null){
          if(cur==root){
              root=root.left;
          }
          if(parter.left==cur){
              parter.left=cur.left;
          }
          if(parter.right==cur){
              parter.right=cur.left;
          }

      }else if(cur.left==null){
          if(cur==root){
              root=root.right;
          }
          if(parter.left==cur){
              parter.left=cur.right;
          }
          if(parter.right==cur){
              parter.right=cur.right;
          }
      }else {
          Node target=cur.right;
          Node ptarget=cur;
          while (target.left!=null){
              ptarget=target;
              target=target.left;
          }
          cur.val=target.val;
          if(ptarget.left==target){
              ptarget.left=target.right;
          }else {
              ptarget.right=target.right;
          }
      }

3.TreeMap

MapMap是⼀个接⼝，不能直接实例化对象，如果要实例化对象可以实例化其实现类TreeMap

public static void main(String[] args) {
        Map<String ,Integer>map=new TreeMap<>();
        map.put("认知觉醒",68);
        map.put("西游记",66);
        map.put("骆驼祥子",58);
        System.out.println(map.get("认知觉醒"));
        //找到就返回对应的value没找到就返回所赋的默认值
        System.out.println(map.getOrDefault("红楼梦",0));
        //返回不重复的集合   根据key的大小进行排序
        System.out.println(map.keySet());
        map.put("西游记",44);
        //value可覆盖
        System.out.println(map.values());
        System.out.println(map.containsKey("被讨厌的勇气"));
        System.out.println(map.containsValue(55));
        //返回所key与value对应关系
        Map<String,Integer>map2=new TreeMap<>();
        String[]arr={"a","b","c","d","a","b","c"};
        for (String s:arr){
            if(!map2.containsKey(s)){
                map2.put(s,1);
            }else {
                int temp=map2.get(s);
                map2.put(s,temp+1);
            }
        }
        for (Map.Entry<String, Integer> entry:map2.entrySet()){
            System.out.println("该字母是"+entry.getKey()+"出现了"+entry.getValue()+"次");
        }
    }

4.TreeSet
Set继承Collection的接口类

  public static void main(String[] args) {
        //Set继承了Collection接口
        Set<String> set=new TreeSet<>();
        set.add("西游记");
        set.add("认知觉醒");
        set.add("骆驼祥子");
        set.add("西游记");
        //重复元素不被添加
        System.out.println(set.toString());
        System.out.println(set.contains("Sv"));
        //返回迭代器
        for (Iterator<String> iterator=set.iterator();iterator.hasNext();){
            String temp= iterator.next();
            System.out.println(temp);
        }
        System.out.println(set.size());
        System.out.println(set.isEmpty());
        int[]arr=new int[set.size()];
        for (int i = 0; i <set.size() ; i++) {
            System.out.println(set);
        }

        String []arr1={"西游记","认知觉醒","骆驼祥子","红楼梦"};
        //判断结合arr1中的元素在set中是否存在
        System.out.println(set.containsAll(Arrays.asList(arr1)));
        System.out.println();
        for (int i = 0; i <arr1.length ; i++) {
            //判断set中是否含有arr1[i]元素  且将set不含的元素添加进去
            System.out.println(set.addAll(Collections.singleton((arr1[i]))));
        }
        System.out.println(set.toString());
        set.remove("西游记");
        System.out.println(set.toString());
        //清空元素
        set.clear();
        System.out.println(set.toString());
    }