算法笔记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的大小取决于磁盘页的大小。