算法笔记2

一、哈希表

雇员类

/**
 * 雇员类
 */
class Employee{
    private int id;
    private String name;
    //指针域
    private Employee next;
    static int idUp = 0;

    public Employee(String name) {
        this.id = idUp++;
        this.name = name;
    }

    public Employee() {
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Employee getNext() {
        return next;
    }

    public void setNext(Employee next) {
        this.next = next;
    }
}

雇员链表类

/**
 * 雇员链表
 */
class EmpList{
    /**
     * 头结点*（有值）
     */
    private Employee head;

    public EmpList(Employee head) {
        this.head = head;
    }

    public EmpList() {
    }

    public Employee getHead() {
        return head;
    }

    public void setHead(Employee head) {
        this.head = head;
    }

    /**
     * 添加员工
     */
    public void addEmp(Employee employee){
        //链表为空则添加到头结点
        if(head == null){
            setHead(employee);
            return;
        }
        //寻找到尾节点
        Employee tempNode = head;
        while (true){
           if(tempNode.getNext() == null){
               break;
           }
           tempNode = tempNode.getNext();
        }
        //添加到尾节点
        tempNode.setNext(employee);
    }
    /**
     * 遍历链表
     */
    public void showList(){
        Employee tempNode = head;
        while (true){
            if (tempNode == null){
                break;
            }
            //if (head == null){
            //    System.out.println("此链表为空，无员工");
            //    //return;
            //}
            System.out.printf("id="+tempNode.getId()+", name="+tempNode.getName()+"---->");
            tempNode = tempNode.getNext();
        }
        System.out.println("");
    }

}

哈希表

class HashMap{
    private EmpList[] empLists;
    private int size;

    public HashMap(int size) {
        this.size = size;
        //初始化数组
        empLists = new EmpList[size];
        for (int i = 0; i < size; i++) {
            empLists[i] = new EmpList();
        }
    }
    /**
     * 删除员工
     */
    public void delEmpById(int id){
        //寻找在第几条链表中
        int index = id%size;
        //获取当前链表头结点
        Employee head = empLists[index].getHead();
        Employee temp = head;
        while (true){
            if (temp == null){
                //没有该id
                return;
            }
            //删除头结点
            if (temp.getId() == id){
                //重新设置头结点
                empLists[index].setHead(temp.getNext());
                return;
            }
            //删除其他节点
            if (temp.getNext().getId() == id){
                temp.setNext(temp.getNext().getNext()==null?null:temp.getNext().getNext());
            }
            temp = temp.getNext();

        }
    }
    /**
     * 查找员工
     */
    public String findEmpById(int id){
        String name;
        String error;
        //寻找在第几条链表中
        int index = id%size;
        //获取当前链表头结点
        Employee head = empLists[index].getHead();
        Employee temp = head;
        while (true){
            if (temp == null){
                error = "没有该员工";
                return error;
            }
            if (temp.getId() == id){
                name = temp.getName();
                return name;
            }
            temp = temp.getNext();
        }
    }
    /**
     * 添加员工
     */
    public void addEmp(Employee employee){
        int id = employee.getId();
        int index = id%size;
        empLists[index].addEmp(employee);
    }
    /**
     * 遍历哈希表
     */
    public void showMap(){
        for (int i = 0; i < empLists.length; i++){
            empLists[i].showList();
        }
    }
}

二、树

2.0二叉树

节点类

/**
 * 节点类
 */
class HeroNode{
    private int no;
    private String name;
    /**
     * 左指针
     */
    private HeroNode left;
    /**
     * 右指针
     */
    private HeroNode right;


    /**
     * 前序遍历（父，左，右）
     */
    public void preorderTraversal(){
        //先输出父节点
        System.out.println(this);
        if (this.left!=null){
            //向左递归
            this.left.preorderTraversal();
        }
        if (this.right!=null){
            //向右递归
            this.right.preorderTraversal();
        }


    }
    /**
     * 中序遍历（左，父，右）
     */
    public void inOrderTraversal(){

        if (this.left!=null){
            //向左递归
            this.left.inOrderTraversal();
        }
        //先输出父节点
        System.out.println(this);
        if (this.right!=null){
            //向右递归
            this.right.inOrderTraversal();
        }


    }
    /**
     * 后序遍历（左，右，父）
     */
    public void postOrderTraversal(){

        if (this.left!=null){
            //向左递归
            this.left.postOrderTraversal();
        }
        if (this.right!=null){
            //向右递归
            this.right.postOrderTraversal();
        }
        //先输出父节点
        System.out.println(this);


    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

二叉树类的遍历

class BinaryTree{
    /**
     * 根节点
     */
    private HeroNode root;

    public BinaryTree(HeroNode root) {
        this.root = root;
    }

    public BinaryTree() {
    }
    /**
     * 添加
     */
    public void addNode(HeroNode node){

    }
    /**
     * 前序遍历
     */
    public void preorderTraversal(){
        if (root != null){
            root.preorderTraversal();
        }
        else {
            System.out.println("树为空");
        }
    }
    /**
     * 中序
     */
    public void inOrderTraversal(){
        if (root != null){
            root.inOrderTraversal();
        }
        else {
            System.out.println("树为空");
        }
    }
    /**
     * 后序
     */
    public void postOrderTraversal(){
        if (root != null){
            root.postOrderTraversal();
        }
        else {
            System.out.println("树为空");
        }
    }
}

二叉树的前中后序查找

/**
 * 前序遍历查找
 */
public HeroNode preorderFind(int num){
    HeroNode heroNode = null;
    System.out.println("前序查找----");
    if (this.getNo() == num){
        return this;
    }
    if (this.left != null){
        heroNode = this.left.preorderFind(num);
    }
    if (heroNode != null){
        return heroNode;
    }
    if (this.right != null){
        heroNode = this.right.preorderFind(num);
    }
    return heroNode;
}

/**
 * 中序查找
 */
public HeroNode inOrderFind(int num){
    HeroNode node = null;
    if (this.left != null){
        node =  this.left.inOrderFind(num);
    }
    if (node != null){
        return node;
    }
    System.out.println("中序查找----");
    if (this.getNo() == num){
        return this;
    }
    if (this.right != null){
        node = this.right.inOrderFind(num);
    }
    return node;

}

/**
 * 后序查找
 */
public HeroNode postFind(int num){
    HeroNode node = null;
    if (this.left != null){
        node = this.left.postFind(num);
    }
    if (node != null){
        return node;
    }
    if (this.right!=null){
        node = this.right.postFind(num);
    }
    if (node != null){
        return node;
    }
    System.out.println("后序查找----");
    if (this.getNo() == num){
        return this;
    }
    return node;
}

删除节点

/**
 * 删除节点
 */
public boolean delNode(int delNum){
    boolean ifDel = Boolean.FALSE;
    if (this.left != null && this.left.getNo() == delNum){
        this.left = null;
        ifDel =true;
        return ifDel;
    }
    if (this.right != null && this.right.getNo() == delNum){
        this.right = null;
        ifDel =true;
        return ifDel;
    }
    if (this.left!=null){
        ifDel =  this.left.delNode(delNum);
    }
    if (ifDel){
        return ifDel;
    }
    if (this.right!= null){
        return this.right.delNode(delNum);
    }  
    return ifDel;

}

2.1顺序存储二叉树

class SequentialBinaryTree{
    private int[] arr;

    public void setArr(int[] arr) {
        this.arr = arr;
    }
    /**
     * 前序遍历
     */
    public void proOrder(){
        //空的数组
        if(arr == null||arr.length == 0){
            try {
                throw new TimeoutException("空数组");
            } catch (TimeoutException e) {
                e.printStackTrace();
            }
            return;
        }
        preOrderHelper(0);
    }
    /**
     * 前序遍历help
     */
    public void preOrderHelper(int index){
        //输出当前节点
        System.out.printf(arr[index]+" ");
        //递归左节点
        if (2*index+1 < arr.length){
            preOrderHelper(2*index+1);
        }
        if (2*index+2 < arr.length){
            preOrderHelper(2*index+2);
        }

    }
}

2.2线索化二叉树

(前序线索化)

叶子节点的left和right分别指向前驱和后继

/**
 * 节点线索化
 */
public void setThreading(){
    if (pre != null && pre.right == null){
        //后继
        pre.right = this;
        //标识符更新
        this.ifLeftNodeTree = false;
        //return;
    }
    //叶子节点
    if (this.left == null){
        //左指针指向前驱
        this.left = pre;
        //标识符更新
        this.ifLeftNodeTree = false;
        pre = this;
        return;
    }
    pre = this;
    if (this.left != null){
        this.left.setThreading();
    }

    if (this.right != null){
        //pre = this;
        this.right.setThreading();
    }
}

线索化前序遍历

/**
 * 线索化前序遍历
 */
public void preOrderByThreading(){
    ThreadedBinaryTreeNode temp = this;
    while (true){
        System.out.println(temp);
        if (temp.ifLeftNodeTree){
            temp = temp.left;
        }
        else {
            temp = temp.right;
        }
        if (temp.right == null){
            System.out.println(temp);
            break;
        }
    }
}

2.3赫夫曼树

/**
 * 排序为赫夫曼树
 */
public  hoffNode toHoffmanTree(int [] arr){

    List<hoffNode> list = new ArrayList<>();
    for (int i : arr) {
        list.add(new hoffNode(i));
    }
    hoffNode root = new hoffNode();
    //while (list.size()>1){
    int times = list.size()-1;
    for (int i = 0; i < times;i++){
        Collections.sort(list);
        //最小的node
        hoffNode leftNode = list.get(0);
        //第二小的node
        hoffNode  rightNode= list.get(1);
        //组合一个新node
        hoffNode newHofumanNode = new hoffNode(leftNode.getValue() + rightNode.getValue());
        newHofumanNode.setLeft(leftNode);
        newHofumanNode.setRight(rightNode);
        list.remove(leftNode);
        list.remove(rightNode);
        //将新节点放入list中
        list.add(newHofumanNode);
    }
    root = list.get(0);
    return root;
}

赫夫曼编码

package tree;

import com.sun.org.apache.bcel.internal.classfile.Code;

import java.io.*;
import java.util.*;

/**
 * @Author: 郜宇博
 * @Date: 2021/8/4 15:10
 */
public class HoffmanCodeDemo {
    /**
     * 赫夫曼编码表
     */
    static Map<Byte,String>  bytesHoffmanCode = new HashMap<>();
    /**
     * 赫夫曼字符串的最后剩余字符个数（不足8个），用于解码
     */
    //static int originalFileBytesLength = 0;
    static int endLength = 0;
    public static void main(String[] args) {
        //String content = "i like like like java do you like a java";
        ////获取每个字符的权重，添加到node中
        //byte[] bytes = content.getBytes();
        ////压缩
        //byte[] hoffmanByte = hoffmanZip(bytes);
        ////解压
        //byte[] decode = decode(bytesHoffmanCode, hoffmanByte, bytes.length);
        //String s = new String(decode);
        //System.out.println("s = " + s);


        String srcPath = "e://src.pptx";
        String destPath = "e://dest.zip";
        fileZipByHoffman(srcPath,destPath);
        System.out.println("压缩成功");

        //String srcPath1 = "e://dest.zip";
        //String destPath1 = "e://originalFile.jpg";
        //fileDecodeByHoffman(srcPath1,destPath1);
        //System.out.println("解压成功");
    }


    /**
     * 文件解压
     * @param srcPath
     * @param destPath
     */
    public static void fileDecodeByHoffman(String srcPath,String destPath){
        //定义文件输入流
        InputStream is = null;
        ObjectInputStream ois = null;
        //定义输出流
        OutputStream os = null;

        try {
            //创建文件输入流
            is = new FileInputStream(srcPath);
            //创建和输入流is有关的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte[]数组 huffamnBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte,String> bytesHoffmanCode =(Map<Byte, String>) ois.readObject();
            //读出最后字符长度
            endLength = (int) ois.readObject();
            //解码
            byte[] decodeBytes = decode(bytesHoffmanCode, huffmanBytes);
            //将bytes写到目标文件
            os = new FileOutputStream(destPath);
            //写数据
            os.write(decodeBytes);

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }finally {
            try {
                if (is!=null){
                    is.close();
                }
                if (os != null){
                    os.close();
                }
                if (ois != null){
                    ois.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    /**
     * 文件压缩
     * @param srcPath 源文件目录
     * @param destPath  目的文件目录
     */
    public static void fileZipByHoffman(String srcPath,String destPath){
        //创建输出流
        OutputStream outputStream = null;
        ObjectOutputStream objectOutputStream = null;
        //创建文件输入流
        FileInputStream inputStream = null;
        try {
            inputStream = new FileInputStream(srcPath);
            //创建一个和源文件大小一样的byte[]
            byte[] bytes =new byte[inputStream.available()];
            //读取文件
            inputStream.read(bytes);
            //对文件进行压缩
            byte[] huffmanBytes = hoffmanZip(bytes);
            //创建文件输出流，存放文件压缩文件
            outputStream = new FileOutputStream(destPath);
            objectOutputStream =new ObjectOutputStream(outputStream);
            objectOutputStream.writeObject(huffmanBytes);

            //存入赫夫曼编码表到压缩文件
            objectOutputStream.writeObject(bytesHoffmanCode);
            //将最后字符长度存入
            objectOutputStream.writeObject(endLength);

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                if (outputStream!=null){
                    outputStream.close();
                }
                if (objectOutputStream != null){
                    objectOutputStream.close();
                }
                if (inputStream != null){
                    inputStream.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }



    /**
     * 解压缩
     * @param map 哈夫曼编码表
     * @param bytes 压缩后的字节数组
     */
    public static byte[] decode(Map<Byte, String> map, byte[] bytes) {
        StringBuilder stringBuilder = new StringBuilder();
        Map<String, Byte> mapReverse = new HashMap<>();

        //将编码表反转，即key与value对换。
        for (Map.Entry<Byte, String> entry : map.entrySet()) {
            mapReverse.put(entry.getValue(), entry.getKey());
        }

        //将字节数组转换为二进制字符串
        for (int i = 0; i < bytes.length; i++) {
            byte b = bytes[i];
            boolean flag = (i == bytes.length - 1);
            //将字节数组中的每个字节转换为二进制
            String string = byteToBitString(!flag, b);
            stringBuilder.append(string);
        }

        //解压缩
        ArrayList<Byte> sourceByte1 = new ArrayList<>();
        int index = 1;
        for (int i = 0; i < stringBuilder.length();) {
            String substring = stringBuilder.substring(i, index);
            Byte aByte = mapReverse.get(substring);
            if (aByte != null) {
                sourceByte1.add(aByte);
                i = index;
            }
            index++;
        }
        byte[] sourceBytes = new byte[sourceByte1.size()];
        for (int i = 0; i < sourceBytes.length; i++) {
            sourceBytes[i] = sourceByte1.get(i);
        }
        return sourceBytes;
    }

    /**
     * 将字节转换为二进制
     * @param flag
     * @param b
     * @return
     */
    public static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        if (flag) {
            temp |= 256;
        }
        String string = Integer.toBinaryString(temp);
        //endLength为静态变量
        if (string.length() < endLength) {
            int length = endLength - string.length();
            for (int i = 0; i < length; i++) {
                string = '0' + string;
            }
        }
        if (flag) {
            return string.substring(string.length() - 8);
        } else {
            return string;
        }
    }

    /**
     * 赫夫曼(压缩)
     */
    public static byte[] hoffmanZip(byte[] bytes){
        List<CodeNode> nodes = getNodes(bytes);
        //1.创建赫夫曼树
        HoffmanCodeTree hoffmanCodeTree = new HoffmanCodeTree();
        //2.调用方法，使此链表存在赫夫曼树中
        CodeNode root = hoffmanCodeTree.toHoffmanTree(nodes);
        //3.获取各字符的赫夫曼编码
        Map<Byte, String> codesHoffman = getCodesHoffman(root);
        //4.将原byte数组转化为赫夫曼编码的byte数组（压缩后的数组）
        byte[] hoffmanByte = zipToHoffmanByte(bytes, bytesHoffmanCode);
        return hoffmanByte;
    }

    /**
     * 获取每个byte的权重，存储在list中
     * @param bytes
     * @return
     */
    public static List<CodeNode> getNodes(byte[] bytes){
        //用例记录字符的权重
        HashMap<Byte, Integer> map = new HashMap<>();
        for (byte aByte : bytes) {
            //如果map中不存在该字符，则添加，并将权重赋值为1
            if (!map.containsKey(aByte)){
                map.put(aByte,1);
            }
            //存在，则权重加一
            else {
                map.put(aByte,map.get(aByte)+1);
            }
        }
        //创建list集合，将map中的键值对传入list中
        List<CodeNode> list = new ArrayList<>();
        Set<Byte> set = map.keySet();
        for (Byte aByte : set) {
            list.add(new CodeNode(aByte, map.get(aByte)));
        }
        return list;
    }
    /**
     * 获取每个节点的赫夫曼编码
     */
    public static void getCodesHoffman(CodeNode codeNode,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        //判断是否为空
        if (codeNode!=null){
            //不是字符节点
            if (codeNode.getValue()==null){
                //向左递归
                getCodesHoffman(codeNode.getLeft(),"0",stringBuilder2);
                //向右递归
                getCodesHoffman(codeNode.getRight(),"1",stringBuilder2);
            }
            //字符节点
            else {
                //存储
                bytesHoffmanCode.put(codeNode.getValue(),stringBuilder2.toString());
            }
        }
    }
    /**
     * 重载getCodesHoffman
     */
    public static Map<Byte,String> getCodesHoffman(CodeNode codeNode){
        if (codeNode == null){
            try {
                throw new Exception("根节点为空");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        getCodesHoffman(codeNode.getLeft(),"0",new StringBuilder());
        getCodesHoffman(codeNode.getRight(),"1",new StringBuilder());
        return bytesHoffmanCode;
    }
    /**
     * 将原byte数组转换为压缩后的byte数组
     */
    public static byte[] zipToHoffmanByte(byte[] bytes,Map<Byte,String> map){
        StringBuilder stringBuilder = new StringBuilder();
        //遍历原数组
        for (byte aByte : bytes) {
            stringBuilder.append(map.get(aByte));
        }
        //每8为一组放入byte中
        int len = (stringBuilder.length()+7)/8;
        byte[] hoffmanByte = new byte[len];
        int index = 0;
        //8个一组（step = 8）
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String partStr = "";
            //截取8个
            if (i+8 <= stringBuilder.length()){
                partStr = stringBuilder.substring(i,i+8);
            }
            //不足8个
            else {
                partStr = stringBuilder.substring(i);
                endLength = stringBuilder.length() - i;
            }
            //将截取的部分放入byte中
            hoffmanByte[index++] = (byte) Integer.parseInt(partStr,2);
        }
        return hoffmanByte;
    }
}

/**
 * 赫夫曼树存字符
 */
class HoffmanCodeTree{
    private CodeNode root;

    public HoffmanCodeTree(CodeNode root) {
        this.root = root;
    }

    public HoffmanCodeTree() {
    }

    public CodeNode getRoot() {
        return root;
    }

    public void setRoot(CodeNode root) {
        this.root = root;
    }



    /**
     * 排序为赫夫曼树
     */
    public CodeNode toHoffmanTree(List<CodeNode> list){
        //while (list.size()>1){
        int times = list.size()-1;
        for (int i = 0; i < times;i++){
            Collections.sort(list);
            //最小的node
            CodeNode leftNode = list.get(0);
            //第二小的node
            CodeNode  rightNode= list.get(1);
            //组合一个新node
            CodeNode newHofumanNode = new CodeNode(null,leftNode.getWeight() + rightNode.getWeight());
            newHofumanNode.setLeft(leftNode);
            newHofumanNode.setRight(rightNode);
            list.remove(leftNode);
            list.remove(rightNode);
            //将新节点放入list中
            list.add(newHofumanNode);
        }
        root = list.get(0);
        return root;
    }
    /**
     *
     *前序遍历
     */
    public void preOrder(){
        if (root!=null){
            root.preorderTraversal();
        }
        else {
            System.out.println("空树");
        }
    }
}

/**
 * 字符节点
 */
class CodeNode implements Comparable<CodeNode>{
    /**
     * 字符
     */
    private Byte value;
    /**
     * 字符权重（出现次数）
     */
    private int weight;
    private CodeNode left;
    private CodeNode right;

    public CodeNode(Byte value, int weight) {
        this.value = value;
        this.weight = weight;
    }

    public Byte getValue() {
        return value;
    }

    public void setValue(Byte value) {
        this.value = value;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public CodeNode getLeft() {
        return left;
    }

    public void setLeft(CodeNode left) {
        this.left = left;
    }

    public CodeNode getRight() {
        return right;
    }

    public void setRight(CodeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "CodeNode{" +
                "value=" + value +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(CodeNode o) {
        return this.getWeight()-o.getWeight();
    }
    /**
     * 前序遍历
     */
    public void preorderTraversal(){
        System.out.println(this);
        if (this.left!=null){
            this.left.preorderTraversal();
        }
        if (this.right!=null){
            this.right.preorderTraversal();
        }
    }
}

2.4二叉排序树

设计 到删除节点、寻找节点、寻找父节点，删除右子树最小节点

二叉排序节点类

/**
 * 二叉排序节点
 */
class BinarySortNode{
    private int val;
    private BinarySortNode left;
    private BinarySortNode right;

    public BinarySortNode(int val) {
        this.val = val;
    }


    /**
     * 中序遍历
     */
    public void inOrderTraversal(){
        if (this.left != null){
            this.left.inOrderTraversal();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.inOrderTraversal();
        }
    }

    /**
     * 寻找节点
     * @param val
     * @return
     */
    public BinarySortNode searchNode(int val){
        //当前节点等于
        if (this.getVal() == val){
            return this;
        }
        else {
            //寻找节点小于当前节点
            if (val < this.getVal()){
                //向左递归寻找
                if (this.left == null){
                    //此路没有
                    return null;
                }
                return this.left.searchNode(val);
            }
            //寻找节点大于当前节点
            else {
                //向右递归
                if (this.right == null){
                    return null;
                }
                return this.right.searchNode(val);
            }
        }
    }

    /**
     * 寻找节点的父节点
     * @param val
     * @return
     */
    public BinarySortNode searchNodeParent(int val){
        //当前节点的子节点等于val值
        if ((this.left!=null&&this.left.getVal() == val) || (this.right!=null&&this.right.getVal() == val)){
            return this;
        }
        else {
            //寻找值小于根节点,且根节点的左节点不为空
            if (val < this.getVal() && this.left!=null){
                //递归寻找
                return this.left.searchNodeParent(val);
            }
            else if (val>=this.getVal()&& this.right!=null){
                return this.right.searchNodeParent(val);
            }
            //左右子节点都为空
            else {
                return null;
            }
        }
    }

    /**
     * 添加节点（左节点小于根节点，
     *          右节点大于根节点）
     * @param node
     */
    public void addNode(BinarySortNode node){
        if (node!=null){
            //将添加的节点值小于当前节点
            if (node.getVal() < this.getVal()){
                //当前节点的左子树为空
                if(this.left == null){
                    //添加到左节点
                    this.left = node;
                }
                else {
                    //继续向左递归
                    this.left.addNode(node);
                }
            }
            //将添加节点大于根节点
            else {
                if (this.right == null){
                    //添加
                    this.right = node;
                }
                else {
                    this.right.addNode(node);
                }
            }
        }
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public BinarySortNode getLeft() {
        return left;
    }

    public void setLeft(BinarySortNode left) {
        this.left = left;
    }

    public BinarySortNode getRight() {
        return right;
    }

    public void setRight(BinarySortNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "BinarySortNode{" +
                "val=" + val +
                '}';
    }
}

二叉排序树类

/**
 * 二叉排序树
 */
class BinarySortTree{
    private BinarySortNode root;

    public BinarySortTree(BinarySortNode root) {
        this.root = root;
    }

    public BinarySortTree() {
    }

    /**
     * 寻找节点
     * @param val
     * @return
     */
    public BinarySortNode searchNode(int val){
        if (root == null){
            return null;
        }
        else {
            return root.searchNode(val);
        }
    }

    /**
     * 寻找父节点
     * @param val
     * @return
     */
    public BinarySortNode searchNodeParent(int val){
        if (root == null){
            return null;
        }
        else {
            return root.searchNodeParent(val);
        }
    }

    /**
     * 删除以root为根节点的右子树的最小节点并返回
     * @param root
     * @return
     */
    public BinarySortNode delRightTreeMin(BinarySortNode root){
        BinarySortNode temp = root;
        while (temp.getLeft()!=null){
            temp = temp.getLeft();
        }
        //删除最小节点
        deleteNode(temp.getVal());
        return temp;
    }

    /**
     * 删除节点
     * @param val
     * @return
     */
    public void deleteNode(int val){
        if (root == null){
            return;
        }
        else {
            //找到删除的节点
            BinarySortNode delNode = searchNode(val);
            //没找到
            if (delNode == null){
                return;
            }
            //找到了
            //0.如果数只有一个节点，那么根节点删除
            if(root.getLeft() == null&& root.getRight()==null){
                root = null;
            }

            //获取父亲节点
            BinarySortNode delNodeParent = searchNodeParent(val);
            //判断叶子节点
            //1.如果删除的为叶子节点
            if (delNode.getLeft() == null && delNode.getRight() == null){
                //将删点在左节点
                if (delNodeParent.getLeft()!=null&& delNodeParent.getLeft().getVal() == val) {
                    delNodeParent.setLeft(null);
                }
                else if (delNodeParent.getRight()!=null&& delNodeParent.getRight().getVal() == val){
                    delNodeParent.setRight(null);
                }
            }
            //2.如果删除节点有两科子树
            else if (delNode.getRight() != null && delNode.getLeft()!=null){
                int min = delRightTreeMin(delNode).getVal();
                delNode.setVal(min);
            }
            //3.如果删除节点只有一颗子树
            else {
                //判断存在那颗子树
                //存在左子树
                if (delNode.getLeft() !=null){
                    //判断为父节点的左节点
                    if (delNodeParent.getLeft()!=null && delNodeParent.getLeft().getVal() == val){
                        //更新父节点的子节点
                        delNodeParent.setLeft(delNode.getLeft());
                    }
                    else {
                        delNodeParent.setRight(delNode.getLeft());
                    }
                }
                //存在右子树
                else {
                    //判断为父节点的左节点
                    if (delNodeParent.getLeft()!=null && delNodeParent.getLeft().getVal() == val){
                        //更新父节点的子节点
                        delNodeParent.setLeft(delNode.getRight());
                    }
                    else {
                        delNodeParent.setRight(delNode.getRight());
                    }
                }
            }
        }
    }

    /**
     * 添加节点
     */
    public void addNode(BinarySortNode node){
        //根节点为空
        if (root == null){
            //添加
            root = node;

        }
        else {
            root.addNode(node);
        }
    }

    /**
     * 中序遍历
     */
    public void inOrderTraversal(){
        if (root != null){
            root.inOrderTraversal();
        }
        else {
            try {
                throw new Exception("数为空，不可遍历");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public BinarySortNode getRoot() {
        return root;
    }

    public void setRoot(BinarySortNode root) {
        this.root = root;
    }
}

2.5二叉平衡树（AVL）

左右子树的高度差不大于1

1.左、右旋转

/**
 * 左旋转
 */
public void rotateLeft(){
    //1.创建新节点,值为当前根节点值
    AVLNode newNode = new AVLNode(this.val);
    //2.新节点的左节点 设置为 根节点的左节点
    newNode.setLeft(this.getLeft());
    //3.新节点的右节点 设置为 根节点右节点的左节点
    newNode.setRight(this.right.left);
    
    //4.根节点的值设置为 根节点右节点的值
    this.val = this.getLeft().getVal();
    //5.根节点的右节点设置为 根节点右节点的右节点（相当于把根节点的右节点替换为根节点）
    this.setRight(this.getRight().getRight());
    //6.根节点的左节点设置为 新节点
    this.setLeft(newNode);

}
/**
 * 右旋转
 */
public void rotateRight(){
    //1.创建新节点，值设置为根节点的值
    AVLNode newNode = new AVLNode(this.val);
    //2.新节点的右节点设置为根节点的右节点
    newNode.setRight(this.getRight());
    //3.新节点的左节点设置为 根节点左节点的右节点
    newNode.setLeft(this.left.right);
    
    //4.根节点的值设置为 根节点的左节点值
    this.val = this.getLeft().getVal();
    //5.根节点的左节点设置为根节点左节点的左节点
    this.setLeft(this.left.left);
    //6.根节点的右节点设置为 新节点
    this.setRight(newNode);
}

2.在二叉排序树添加时应进行判断，然后左右旋转，从而形成平衡树

/**
 * 添加节点
 */
public void addNode(AVLNode node){
    //根节点为空
    if (root == null){
        //添加
        root = node;

    }
    else {
        root.addNode(node);
    }
    //当添加完应判断是否属于平衡二叉树，不符合则进行旋转
    //右子树高度减左子树高度>1 左旋
    if (  (root.getRightChildTreeHeight() - root.getLeftChildTreeHeight()  )>1){
        //如果右子树的左子树高度>右子树右子树高度
        //先把根节点的右子树右旋，再左旋
        if (root.getRight()!=null && root.getRight().getLeftChildTreeHeight() >root.getRight().getRightChildTreeHeight()) {
            root.getRight().rotateRight();
        }
        //左旋
        root.rotateLeft();
    }
    else if ((root.getLeftChildTreeHeight() - root.getRightChildTreeHeight()  )>1){
        if (root.getLeft()!=null 
            && 
            root.getLeft().getRightChildTreeHeight() >root.getLeft().getLeftChildTreeHeight()) {
            root.getLeft().rotateLeft();
        }
        root.rotateRight();
    }
}

2.6 2-3树

要求：

1. 所有叶子节点在同一层
2. 二节点要么有两个节点，要么没有节点
3. 三节点要么有三个节点，要么没有节点
4. 构建时，如果不满足则向上拆，如果上层满，则拆本层。并且遵循二叉排序树的规则。

M阶B树（B-树）特点

1. 一种二叉搜索树。
2. 除根节点外的所有非叶节点至少含有（M/2（向上取整）-1）个关键字，每个节点最多有M-1个关键字，并且以升序排列。所以M阶B树的除根节点外的所有非叶节点的关键字取值区间为[M/2-1(向上取整),M-1]。
3. 每个节点最多有M-1个关键字

M阶B+数特点

1. 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）。

2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接（叶子节点组成一个链表）。

3. 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。

4. 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

5. 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。

B树的优点

1.B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

B+树的优点

1. 所有的叶子结点使用链表相连，便于区间查找和遍历。B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
2. b+树的中间节点不保存数据，能容纳更多节点元素。

B树和B+树的共同优点

考虑磁盘IO的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，m的大小取决于磁盘页的大小。