1.二分查找法

  1. public class BinarySort {
  3.     //递归查找
  4.     //二分法
  5.     public static int recurrenceBinarySort(int[] arr,int l,int r,int v) {
  6.         int mid =l+(r-l)/2;
  7.         if(l>r) {
  8.             return -1;
  9.         }
  10.         if(arr[mid] == v) {
  11.             return mid;
  12.         }
  13.         if(arr[mid] > v) {
  14.             return recurrenceBinarySort(arr,l,mid-1,v);
  15.         }else {
  16.             return recurrenceBinarySort(arr,mid+1,r,v);
  17.         }
  18.     }
  20.     //非递归二分查找
  21.     public static int binarySort(int[] arr,int l,int r,int v) {
  22.         while(l<=r) {
  23.             int mid =l+(r-l)/2;
  24.             //System.out.println(mid);
  25.             if(arr[mid] == v) {
  26.                 return mid;
  27.             }else if(arr[mid] >v){
  28.                 r = mid-1;
  29.             }else {
  30.                 l = mid+1;
  31.             }
  32.         }
  33.         return -1;
  34.     }

2.二叉搜索树

Binary Search Tree
不仅可查找数据，还可以高效地插入，动态维护数据
特点
每个节点的键值大于左孩子
每个节点的键值小于右孩子
以左右孩子为根的子树仍为二叉搜索树

2.1 遍历 前中后层序

  1.     //前序遍历 中左右
  2.     public void preOrder() {
  3.         preOrder(root);
  4.     }
  5.     //前序遍历
  6.     private void preOrder(BinaryTree root) {
  7.         if(root == null) {
  8.             return;
  9.         }
  10.         System.out.print(root.key);
  11.         preOrder(root.Left);
  12.         preOrder(root.Right);
  13.     }
  14.     //中序遍历 左中右
  15.     public void inOrder() {
  16.         inOrder(root);
  17.     }
  18.     //中序遍历
  19.     private void inOrder(BinaryTree root) {
  20.         if(root ==null) {
  21.             return;
  22.         }
  23.         inOrder(root.Left);
  24.         System.out.print(root.key);
  25.         inOrder(root.Right);
  26.     }
  27.     //后序遍历 左右中
  28.     public void postOrder() {
  29.         postOrder(root);
  30.     }
  31.     //后序遍历
  32.     private void postOrder(BinaryTree root) {
  33.         if(root ==null) {
  34.             return;
  35.         }
  36.         postOrder(root.Left);
  37.         postOrder(root.Right);
  38.         System.out.println(root.key);
  39.     }
  40.     //层序遍历
  41.     public void levelOrder() {
  42.         levelOrder(root);
  43.     }
  44.     /*
  45.      * 层序遍历
  46.      * 创建 LinkedList集合
  47.      */
  48.     private void levelOrder(BinaryTree root) {
  49.         LinkedList<BinaryTree> nodes = new LinkedList<BinaryTree>();
  50.         if(root == null) {
  51.             return;
  52.         }
  53.         //当root 不为空时
  54.         nodes.addFirst(root);
  55.         while(nodes.size()>0) {
  56.             BinaryTree firstNode = nodes.getFirst();
  57.             //如集合的第一个节点有左孩子，则进集合
  58.             if(firstNode.Left !=null) {
  59.                 nodes.addLast(firstNode.Left);
  60.             }
  61.             //如集合的第一个节点有右孩子,则进集合
  62.             if(firstNode.Right != null) {
  63.                 nodes.addLast(firstNode.Right);
  64.             }
  65.             //去除集合的第一个元素
  66.             BinaryTree reNode = nodes.removeFirst();
  67.             System.out.print(reNode.key);
  68.         }
  69.     }

2.2 二叉树建立

public class BinaryTree {
    //定义数据结构
    private int key;
    private int value;
    private BinaryTree Left;    //左孩子树
    private BinaryTree Right;    //右孩子树
    private static int count = 0;  //记录二叉树节点个数

    BinaryTree root;   //根节点


    public int getKey() {
        return key;
    }
    public void setKey(int key) {
        this.key = key;
    }
    public BinaryTree() {}
    //初始化二叉树
    public BinaryTree(int key,int value) {
        this.key = key;
        this.value = value;
        this.Left = null;
        this.Right = null;
    }

    //插入函数
    public void insert(int key,int value) {
        root = insert(root,key,value);
    }
    /*
     * 插入函数 实现函数
     * node ： 根节点
     * 结果：返回根节点
     */

    private BinaryTree insert(BinaryTree node,int key,int value) {
        if(node == null) {  //如果node为空
            count++;
            return new BinaryTree(key,value);
        }
        if(key == node.key) { // 当key == 当前node.key
            node.value = value;

        }else if(key < node.key) { // 当key小于当前node.key
            node.Left = insert(node.Left,key,value);

        }else{  //当前key大于当前node.key
            node.Right = insert(node.Right,key,value);

        }
        //返回根节点
        return node;
    }
}

2.3 求最大小键值

    //获取二叉树中最小key的节点
    public BinaryTree minimum() {
        return minimum(root);
    }

    //获取二叉树中最小key的节点
    private BinaryTree minimum(BinaryTree root) {
        //如果当前节点的左孩子为空
        if(root.Left == null || root ==null) {
            return root;
        }            
        //如果左孩子不为空
        return minimum(root.Left);

    }

    //获取二叉树的最大key的节点
    public BinaryTree maximum() {
        return maximum(root);
    }
    //获取二叉树的最大key的节点
    private BinaryTree maximum(BinaryTree root) {
        if(root.Right == null || root == null) {
            return root;
        }
        return maximum(root.Right);
    }

2.4删除最大最小键值

    //删除二叉树最大的key，并返回根节点
    public BinaryTree removeMax() {
        root = removeMax(root);
        return root;
    }

    //删除二叉树最大的key，并返回根节点
    public BinaryTree removeMax(BinaryTree root) {
        //如果找到最大key
        if(root.Right == null || root == null) {
            if(root.Left == null) {//如没有左孩子
                return null;
            }else {
                return root.Left;
            }
        }

        root.Right = removeMax(root.Right);
        return root;
    }
    //删除二叉搜索树的最小值 并返回跟节点
    public BinaryTree removeMin() {
        root = removeMin(root);
        return root;
    }

    //删除二叉搜索树的最小值 并返回根节点
    private BinaryTree removeMin(BinaryTree node) {
        if(node.Left == null || node == null) {  //找到最小值了
            if(node.Right == null) {     //如果该最小值没有右孩子
                return null;
            }else {  //该最小值有右孩子
                return node.Right;
            }
        }
        node.Left = removeMin(node.Left);
        return node;
    }

2.5 删除任意节点

    //删除二叉树的任何节点 返回根节点
    public void remove(int key) {
        root = remove(root,key);
    }

    private BinaryTree remove(BinaryTree root,int key) {


        if(root.key == key || root == null) {  //如果当前root的key == key
            if(root.Right == null){  //如果没有右孩子
                count--;
                return root.Right;
            }else if(root.Left == null) {  //如果没有左孩子
                count--;
                return root.Left;
            }else {     //左右孩子都存在
                /*
                 * 获取该孩子 右孩子的最小值
                 * 以该最小值来代替该root
                 */
                BinaryTree rightMinNode = minimum(root.Right);
                //新节点的右孩子等于 右子树删除最小值之后的根节点
                rightMinNode.Right = removeMin(root.Right);
                rightMinNode.Left = root.Left;
                return rightMinNode;
            }
        }else if(key>root.key) {//如果key>root.key
            root.Right = remove(root.Right,key);
        }else { //如果key<root.key
            root.Left = remove(root.Left,key);
        }
        return root;
    }

2. 6运行

public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
         bt.insert(5, 5);
         bt.insert(2, 2);
         bt.insert(8, 8);
         bt.insert(1, 1);
         bt.insert(3, 3);
         bt.insert(6, 6);
         bt.insert(9, 9);
         System.out.print("层序： ");
         bt.levelOrder();
         System.out.println();
         bt.remove(5);
         bt.remove(9);
         System.out.println("删除节点 5和9");
         System.out.print("层序： ");
         bt.levelOrder();
         System.out.println();
         //bt.removeMin();
         //bt.removeMin();
         //bt.removeMin();
         System.out.println("最小值：" +bt.minimum().getKey());
         System.out.println("最大值：" +bt.maximum().getKey());

    }
}

image.png

2. 7二分搜索树的局限性

二分搜索树可能退化成链表

4.Treap

5.trie