2020-04-22

哈弗曼树

哈弗曼树(最优二叉树)

带权路径长度最小(WPL)的树(权值越大的节点离根节点越近)

WPL(带权路径长度)

WPL(带权路径长度):树中所有叶子节点的带权路径长度之和

WPL计算举例(X的系数就是从这个节点到根节点的有几个节点)

流程分析

步骤:

1. 排序
2. 挑选最小的两个 生成新的节点
3. 两个步骤不停的交替执行(排序之后就选最小的两个生成新的然后把新的节点放到以前的序列排序)

手写流程:

哈弗曼树代码实现(List范型)

步骤分析

//先使用数组中所有元素创建若干个二叉树(只有一个节点)
//排序
//取出来权值最小的两个二叉树
//创建一颗新的二叉树
//将取出来权值最小的两个二叉树移除    
//放入原来的二叉树集合中

Node类

public class Node implements Comparable<Node>{  //要使用排序要实现Comparable类
    int value;
    Node left;
    Node right;

    public Node(int value){
        this.value=value;
    }

    @Override
    public int compareTo(Node o) {
        return -(this.value-o.value);  //自己设置输出node节点的值
    }

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

}

Test类

public class Test {
    public static void main(String[] args) {
        int[] arr=new int[]{3,7,8,29,5,11,23,14};
        System.out.println("原来的数组: "+Arrays.toString(arr));  //输出原来的数组
        Node node=createHuffmanTree(arr);  //调用方法
    }

    public static Node createHuffmanTree(int[] arr){
    //先使用数组中所有元素创建若干个二叉树(只有一个节点)
        List<Node> nodes=new ArrayList<>();
            for(int value:arr){
                nodes.add(new Node(value));
            }
        //循环处理
        while(nodes.size()>1){
          //排序
             Collections.sort(nodes);
            System.out.println("每一次剩下的数: "+nodes);
          //取出来权值最小的两个二叉树
            Node left=nodes.get(nodes.size()-1);
            Node right=nodes.get(nodes.size()-2);
          //创建一颗新的二叉树
            Node parent=new Node(left.value+right.value);
          //将取出来权值最小的两个二叉树移除
            nodes.remove(left);
            nodes.remove(right);
          //将新的放入原来的二叉树集合中
            nodes.add(parent);
        }
        System.out.println(nodes);
        return null;
    }

}

总结

1. 使用list<Node>范型去存储数组元素
2. 使用for循环add方法添加数组元素为节点
3. 使用Collections类的sort方法对范型对象排序
4. 获取范型对象的最后两个二叉树
5. 创建新的二叉树(值为第四步两个二叉树的值)
6. 通过remove方法移除
7. 通过add添加第五步新创建的二叉树
8. 可以直接输出nodes(最后只剩下结果的那个二叉树)

执行过程分析:

哈弗曼编码原理分析

通讯领域信息处理的三种方式

1. 定长编码(将对应的数字用ASCII码替换)
2. 不定长编码(将字母的出现频率计算出来 然后给固定的数字代表)
    容易出现分不清到底是代替哪个字母 
3. 哈夫曼编码(将字母出现频率计算出来 然后排序 选出最小两个生成新的 排序)
    然后左边的路权值给0 / 右边的给1

三种方式举例

定长编码

将对应的字母的翻译成ASCII码 – ASCII码翻译对应二进制

不定长编码

将对应单词的出现频率排序 – 出现最多的给0(依次给二进制)

哈夫曼编码

将对应单词的出现频率排序 – 出现最多的给0(依次给二进制) – 编写哈弗曼树(左路径给0/右路径给1) – 不同路径找到不同单词的值

哈弗曼编码代码实现

步骤分析

1. 统计字符数并且排序
2. 创建哈夫曼树
3. 创建哈夫曼树编码表
4. 编码

Node类

public class Node implements Comparable<Node>{
    Byte data;  //n:11 c:1 这种形式
    int weight;  //权值
    Node left;
    Node right;
    public Node(Byte data,int weight){
        this.data=data;
        this.weight=weight;
    }

    //实现接口方法 (获取值)
    @Override
    public int compareTo(Node o) {
        return o.weight-this.weight;
    }

    //输出node信息
    @Override
    public String toString() {
        return "Node{" + "data=" + data + ", weight=" + weight + ", left=" + left + ", right=" + right + '}';
    }

}

TestHuffmantreeCoDE类

public class TestHuffmantreeCoDE {

    public static void main(String[] args) {
     //输入一个叫msg的字符串  让他使用哈夫曼编码
        String msg="can you can a can as a can canner can a can.";
            byte[] bytes=msg.getBytes();
        //进行哈夫曼编码压缩
         byte[] b=huffmanZip(bytes);
            System.out.println("压缩前"+bytes.length);
            System.out.println("压缩后"+b.length);
    }

    //进行哈夫曼编码(主)
    private static byte[] huffmanZip(byte[] bytes) {
        //1. 先统计每一个byte出现的个数  放入一个集合
            List<Node> nodes=getNodes(bytes);  //调用方法
        //2. 创建哈弗曼树
            Node tree=createHuffmanTree(nodes);  //创建一个叫tree的哈弗曼树
        //3. 创建哈夫曼编码表
            Map<Byte,String> huffCodes=getCodes(tree);
        //4. 编码(将每个byte替换成map里面的string)
            byte[] b=zip(bytes,huffCodes);

        return b;
    }

    //4. 将每个byte替换成Map集合里面的string即可
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
        StringBuilder sb=new StringBuilder();
        //把需要压缩的byte数组处理成一个二进制的字符串
        for(byte i:bytes){
            sb.append(huffCodes.get(i));  //获取到键
        }
        //定义长度
        int len;
        if(sb.length()%8==0){
            len=sb.length()/8;
        }else{
            len=sb.length()/8+1;  //%8之后的余数还可以凑成一个
        }

        //用于存储压缩后的byte
            byte[] by=new byte[len];
        //记录新byte的位置
            int index=0;

        for(int i=0;i<sb.length();i+=8){
            String strByte;
            if(i+8>sb.length()){
                strByte = sb.substring(i); // 不截取 只显示当前的
            }else{
                strByte = sb.substring(i, i + 8); // 截取8位为一个单元
            }
            byte byt=(byte)Integer.parseInt(strByte,2); //将2进制其转成10进制
          //将截取出来的8位的单元转成10进制最后存到之前创建的by数组
            by[index++]=byt;
        }

        return by;
    }

    //在第三步中用于存储路径
    static  StringBuilder sb=new StringBuilder();
    //在第三步中用于存储哈弗曼编码
    static Map<Byte,String> huffCodes=new HashMap<>();

    //3. 创建哈弗曼树编码表
    private static Map<Byte, String> getCodes(Node tree) {
        if(tree==null){
            return null;
        }
        getCodes(tree.left,"0",sb);   //左边赋0
        getCodes(tree.right,"1",sb);  //右边赋1
        return huffCodes;
    }

    //3.1 给左右节点递归传递下面的值
    private static void getCodes(Node node, String code, StringBuilder sb) {
      //新建stringbuilder的sb2对象
        StringBuilder sb2=new StringBuilder(sb);
      //新的stringbuilder对象添加进去 0 / 1
        sb2.append(code);
      //
        if(node.data==null){  //不是节点
            getCodes(node.left,"0",sb2);
            getCodes(node.right,"1",sb2);
        }
        else{  //直到最后一个叶子节点(底部)
            huffCodes.put(node.data,sb2.toString()); //将输出 n:00 a:01 c:02这种形式
        }
    }

    //2. 创建哈夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        //
        while(nodes.size()>1){
            //排序
            Collections.sort(nodes);
            //取出两个权值最小的二叉树
                Node left=nodes.get(nodes.size()-1);
                Node right=nodes.get(nodes.size()-2);
            //创建新的二叉树
                Node parent=new Node(null,left.weight+right.weight);  //新创建的没有值 权值是下面两个相加
            //把之前的两棵二叉树设置为新创建的二叉树的子树
                parent.left=left;
                parent.right=right;
            //把之前的两棵二叉树从之前的删除
                nodes.remove(left);
                nodes.remove(right);
            //把新创建的二叉树放入集合中
                nodes.add(parent);
        }
        return nodes.get(0); //返回第0个(最大的那个)
    }

    //1. 把byte数组转化为node集合
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes=new ArrayList<>();
        //使用map数组存储每一个byte出现了多少次
            Map<Byte,Integer> counts=new HashMap<>();  //map对象叫counts   c:11 a:12 d:123 这种形式
        //s统计每一个byte出现次数
            for(byte i:bytes){
                Integer count = counts.get(i);  //统计对应每个byete出现的次数为count
                if(count==null){
                    counts.put(i,1);  //如果第一次出现  出现次数为1
                }
                else{
                    counts.put(i,count+1);  //不是第一次出现 直接出现次数+1
                }
            }
        //把每一个键值对转为一个node对象
            for(Map.Entry<Byte,Integer> i:counts.entrySet()){      //map集合遍历的一种方式
                nodes.add(new Node(i.getKey(),i.getValue()));
            }
         return null;
    }

}

哈夫曼编码解码

实现思路

1. 把byte数组转为一个二进制的字符串(使用异或补齐八位)
2. 将字符串按照指定的赫夫曼编码进行解码
    2.1 使用map将赫夫曼树编码的键值交换(现在是反向通过value查找)
    2.2 创建集合存储解码之后的数字
    2.3 处理字符串(按照0 01 11这种形式转换为 99 95这种数字)
    2.4 将存储解码的集合转为数组

解码的类

  //解码
   private static byte[] decode(Map<Byte, String> huffCodes2, byte[] bytes) {
       StringBuilder sb=new StringBuilder();
       //1. 把byte数组转为一个二进制的字符串
           for(int i=0;i<bytes.length;i++){
               byte b=bytes[i];
               boolean flag=(i==bytes.length-1);
               sb.append(byteToBitstr(!flag,b));  //不断地添加对应的二进制字符串
           }
       //2. 将字符串按照指定的赫夫曼编码进行解码
           //把赫夫曼编码的键值对进行交换(反向)
               Map<String,Byte> map=new HashMap<>();
               for(Map.Entry<Byte,String> entry:huffCodes.entrySet()){
                   map.put(entry.getValue(),entry.getKey());
               }
       //创建一个集合 用于存byte
           List<Byte> list=new ArrayList<>();

       //处理字符串(前缀编码不重复)
           for(int i=0;i<sb.length();){
               int count=1;
               boolean flag=true; //确定几位是一个判断的 (1 11 111这种)
            //截取一个byte
                 while(flag){
                   String key=sb.substring(i,i+count);  //用key去map找对应的
                   Byte b=map.get(key);
                   if(b==null){
                       count++;  //没截取到 就往下放一位找
                   }else{
                       flag=false; //截取到 就不让截取
                   }
               }
           }

        //把集合转为数组
           byte[] b=new byte[list.size()];   //[96,98,98,...]  转为数组{96,98,98,...}
           for(int i=0;i<b.length;i++){
               b[i]=list.get(i);
           }

       return b;
   }

//需要将所需要的8位截取出来
   public static String byteToBitstr(boolean flag,byte b) {
       int temp = b;
       if (flag) {
           temp |= 256; //异或
       }
       String str = Integer.toBinaryString(temp);
       if (flag) {
           return str.substring(str.length() - 8);  //取出来后八位
       }else{
           return str;  //只取出来自己的东西
       }
       
   }

哈夫曼编码压缩文件

实现原理

1. 创建一个输入流
2. 创建一个和输入流指向的文件大小一样的byte数组
3. 读取文件内容;
4. 读取结束后关闭输入流
5. 进行哈夫曼编码进行编码
6. 创建输出流
  6.1 将压缩后的byte数组写入文件
  6.2 将哈夫曼编码表写入文件
  6.3 关闭输出流

具体方法

main方法:

//进行哈夫曼压缩文件
      String src="1.bmp";  //压缩前的文件
      String dst="2.zip";  //压缩后的文件
          zipFile(src,dst);  //调用压缩方法

压缩的方法:

public static  void zipFile(String src,String dst)throws IOException {
     //1. 创建一个输入流
         InputStream is=new FileInputStream(src);  //使用输入流获取文件内容
     //2. 创建一个和输入流指向的文件大小一样的byte数组
         byte[] b=new byte[is.available()];
     //3. 读取文件内容
         is.read(b);
     //4. 读取结束后关闭
         is.close();
     //5. 进行哈夫曼编码进行编码
         byte[] bytezip=huffmanZip(b);  //调用方法
     //6. 创建输出流
         OutputStream os=new FileOutputStream(dst);
         ObjectOutputStream oos=new ObjectOutputStream(os);
       //6.1 将压缩后的byte数组写入文件
           oos.writeObject(bytezip);
       //6.2 将哈夫曼编码表写入文件
           oos.writeObject(huffCodes);
       //6.3 关闭流
           os.close();
           oos.close();

   }

哈夫曼编码解压文件

实现原理

1. 创建一个输入流
2. 读取byte数组     (解压给byte数组的)
3. 读取哈夫曼编码表  (解压给byte数组的)
4. 关闭流
5. 调用解码方法
6. 创建一个输出流
7. 写出数据
8. 关闭输出流

具体方法

//解压
   public static void unZip(String src,String dst) throws IOException, ClassNotFoundException {
       //1. 创建一个输入流
           InputStream is=new FileInputStream("2.zip");  //使用输入流获取文件内容
           ObjectInputStream ois =new ObjectInputStream(is);
       //2. 读取byte数组
           byte[] b= (byte[]) ois.readObject();
       //3. 读取哈夫曼编码表
           Map<Byte,String> codes=(Map<Byte, String>) ois.readObject();
       //4. 关闭流
           ois.close();
           is.close();
       //5. 解码
           byte[] bytes = decode(codes, b);
       //6. 创建一个输出流
            OutputStream os=new FileOutputStream(dst);
       //7. 写出数据
            os.write(bytes);
       //8. 关闭输出流
            os.close();
   }

哈夫曼编码完整代码(Node不展示)

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class TestHuffmanCode {

	public static void main(String[] args) {
//		String msg="can you can a can as a can canner can a can.";
//		byte[] bytes = msg.getBytes();
//		//进行赫夫曼编码压缩
//		byte[] b = huffmanZip(bytes);
//		//使用赫夫曼编码进行解码
//		byte[] newBytes = decode(huffCodes,b);
//		System.out.println(new String(newBytes));
		String src="1.bmp";
		String dst="2.zip";
//		try {
//			zipFile(src, dst);
//		} catch (IOException e) {
//			e.printStackTrace();
//		}
		try {
			unZip("2.zip", "3.bmp");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	/**
	 * 文件的解压
	 * @param src
	 * @param dst
	 * @throws Exception 
	 */
	public static void unZip(String src,String dst) throws Exception {
		//创建一个输入流
		InputStream is  = new FileInputStream("2.zip");
		ObjectInputStream ois = new ObjectInputStream(is);
		//读取byte数组
		byte[] b = (byte[]) ois.readObject();
		//读取赫夫曼编码表
		Map<Byte, String> codes = (Map<Byte, String>) ois.readObject();
		ois.close();
		is.close();
		//解码
		byte[] bytes = decode(codes, b);
		//创建一个输出流
		OutputStream os  = new FileOutputStream(dst);
		//写出数据
		os.write(bytes);
		os.close();
	}
	
	/**
	 * 压缩文件
	 * @param src
	 * @param dst
	 * @throws IOException
	 */
	public static void zipFile(String src,String dst) throws IOException {
		//创建一个输入流
		InputStream is = new FileInputStream(src);
		//创建一个和输入流指向的文件大小一样的byte数组
		byte[] b = new byte[is.available()];
		//读取文件内容
		is.read(b);
		is.close();
		//使用赫夫曼编码进行编码
		byte[] byteZip = huffmanZip(b);
		//输出流
		OutputStream os = new FileOutputStream(dst);
		ObjectOutputStream oos = new ObjectOutputStream(os);
		//把压缩后的byte数组写入文件
		oos.writeObject(byteZip);
		//把赫夫曼编码表写入文件
		oos.writeObject(huffCodes);
		oos.close();
		os.close();
	}
	
	/**
	 * 使用指定的赫夫曼编码表进行解码
	 * @param huffCodes2
	 * @param b
	 * @return
	 */
	private static byte[] decode(Map<Byte, String> huffCodes, byte[] bytes) {
		StringBuilder sb = new StringBuilder();
		//把byte数组转为一个二进制的字符串
		for(int i=0;i<bytes.length;i++) {
			byte b = bytes[i];
			//是否是最后一个。
			boolean flag = (i==bytes.length-1);
			sb.append(byteToBitStr(!flag,b));
		}
		//把字符串按照指定的赫夫曼编码进行解码
		//把赫夫曼编码的键值对进行调换
		Map<String, Byte> map = new HashMap<>();
		for(Map.Entry<Byte, String> entry:huffCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		//创建一个集合，用于存byte
		List<Byte> list = new ArrayList<>();
		//处理字符串
		for(int i=0;i<sb.length();) {
			int count=1;
			boolean flag = true;
			Byte b=null;
			//截取出一个byte
			while(flag) {
				String key = sb.substring(i, i+count);
				b = map.get(key);
				if(b==null) {
					count++;
				}else {
					flag=false;
				}
			}
			list.add(b);
			i+=count;
		}
		//把集合转为数组
		byte[] b = new byte[list.size()];
		for(int i=0;i<b.length;i++) {
			b[i]=list.get(i);
		}
		return b;
	}
	
	private static String byteToBitStr(boolean flag,byte b) {
		int temp=b;
		if(flag) {
			temp|=256;
		}
		String str = Integer.toBinaryString(temp);
		if(flag) {
			return str.substring(str.length()-8);
		}else {
			return str;
		}
	}

	/**
	 * 进行赫夫曼编码压缩的方法
	 * @param bytes
	 * @return
	 */
	private static byte[] huffmanZip(byte[] bytes) {
		//先统计每一个byte出现的次数，并放入一个集合中
		List<Node> nodes = getNodes(bytes);
		//创建一颗赫夫曼树
		Node tree = createHuffmanTree(nodes);
		//创建一个赫夫曼编码表
		Map<Byte, String> huffCodes = getCodes(tree);
		//编码
		byte[] b = zip(bytes,huffCodes);
		return b;
	}
	
	/**
	 * 进行赫夫曼编码
	 * @param bytes
	 * @param huffCodes2
	 * @return
	 */
	private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
		StringBuilder sb = new StringBuilder();
		//把需要压缩的byte数组处理成一个二进制的字符串
		for(byte b:bytes) {
			sb.append(huffCodes.get(b));
		}
		//定义长度
		int len;
		if(sb.length()%8==0) {
			len=sb.length()/8;
		}else {
			len=sb.length()/8+1;
		}
		//用于存储压缩后的byte
		byte[] by = new byte[len];
		//记录新byte的位置
		int index = 0;
		for(int i=0;i<sb.length();i+=8) {
			String strByte;
			if(i+8>sb.length()) {
				strByte = sb.substring(i);
			}else {
				strByte = sb.substring(i, i+8);
			}
			byte byt = (byte)Integer.parseInt(strByte, 2);
			by[index]=byt;
			index++;
		}
		return by;
	}

	//用于临时存储路径
	static StringBuilder sb = new StringBuilder();
	//用于存储赫夫曼编码
	static Map<Byte, String> huffCodes = new HashMap<>();
	/**
	 * 根据赫夫曼树获取赫夫曼编码
	 * @param tree
	 * @return
	 */
	private static Map<Byte, String> getCodes(Node tree) {
		if(tree==null) {
			return null;
		}
		getCodes(tree.left,"0",sb);
		getCodes(tree.right,"1",sb);
		return huffCodes;
	}

	private static void getCodes(Node node, String code, StringBuilder sb) {
		StringBuilder sb2 = new StringBuilder(sb);
		sb2.append(code);
		if(node.data==null) {
			getCodes(node.left, "0", sb2);
			getCodes(node.right, "1", sb2);
		}else {
			huffCodes.put(node.data, sb2.toString());
		}
	}

	/**
	 * 创建赫夫曼树
	 * @param nodes
	 * @return
	 */
	private static Node createHuffmanTree(List<Node> nodes) {
		while(nodes.size()>1) {
			//排序
			Collections.sort(nodes);
			//取出两个权值最低的二叉树
			Node left = nodes.get(nodes.size()-1);
			Node right = nodes.get(nodes.size()-2);
			//创建一颗新的二叉树
			Node parent = new Node(null, left.weight+right.weight);
			//把之前取出来的两颗二叉树设置为新创建的二叉树的子树
			parent.left=left;
			parent.right=right;
			//把前面取出来的两颗二叉树删除
			nodes.remove(left);
			nodes.remove(right);
			//把新创建的二叉树放入集合中
			nodes.add(parent);
		}
		return nodes.get(0);
	}

	/**
	 * 把byte数组转为node集合
	 * @param bytes
	 * @return
	 */
	private static List<Node> getNodes(byte[] bytes) {
		List<Node> nodes = new ArrayList<>();
		//存储每一个byte出现了多少次。
		Map<Byte, Integer> counts = new HashMap<>();
		//统计每一个byte出现的次数
		for(byte b:bytes) {
			Integer count = counts.get(b);
			if(count==null) {
				counts.put(b, 1);
			}else {
				counts.put(b, count+1);
			}
		}
		//把每一个键值对转为一个node对象
		for(Map.Entry<Byte, Integer> entry:counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}
		return nodes;
	}

}

2020-04-18

二叉树

二叉树(任何子节点数<=2)

1. 最大度为2
2. 可以为空
3. 有序树(左右节点不同)

存储方式

1. 链式存储
2. 顺序存储

满二叉树(很完美)

最层都是最饱满的样子

完全二叉树(编号没有间断)

编号连续的满二叉树的子集

二叉树链式存储

实现功能

1. 前/中/后序遍历
2. 前/中/后序查找 (当前满足/左节点满足/右节点满足)
3. 删除子树【递归】 (当前节点可删/左节点/右节点)

三种遍历方法解析

不断递归自己的方法遍历

// 前序遍历(根左右)
    public void frontShow() {
        System.out.print(value+" "); //先输出当前节点内容
        if (leftNode != null) {
            leftNode.frontShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.frontShow();  //右节点
        }
    }

    // 中序遍历(左根右)
    public void midShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        System.out.print(value+" "); //先输出当前节点内容
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
    }

    //后序遍历(左右根)
    public void afterShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
        System.out.print(value+" "); //先输出当前节点内容
    }

查找节点

判断节点的value值和查找的i是否相等

//前序查找
   public TreeNode frontSerach(int i){
       TreeNode target=null;
       if(this.value==i) {
           return this;   //当前节点的值就是要查找的值
       }else{
           if(leftNode!=null){
               target=leftNode.frontSerach(i); //左边的值查到的话给target
           }
           if(target!=null){
               return target;  //如果查到了就不为空 返回target
           }
           if(rightNode!=null){
               target=rightNode.frontSerach(i);  //右边的值可以查到
           }
       }
           return target;
   }

删除子树

如果是根节点直接为null/其他的话就不断递归判断左右节点

//删除子树
    public void delete(int i) {
        TreeNode parent=this;  //把上一层节点存起来
        if(parent.leftNode!=null&&parent.leftNode.value==i){  //左节点是这个值
            parent.leftNode=null;  ///这个节点置空
            return;
        }
        if(parent.rightNode!=null&&parent.rightNode.value==i){  //右节点是这个值
            parent.rightNode=null;  //这个节点置空
            return;
        }
        parent=leftNode;  //左边节点给上一层节点  递归
        if(parent!=null){
            parent.delete(i);  
        }
        parent=rightNode;  //右边节点给上一层节点 递归
        if(parent!=null){
            parent.delete(i);
        }
    }

完整代码

1. BinaryTree类 :创建树(set/get方法) 所需要的方法定义(调用TreeNode方法)
2. TreeNode类 : 描述节点权和左右儿子(方法具体实现)
3. TestBinaryTree类 ：创建树添加节点

BinaryTree类

public class BinaryTree {
    TreeNode root;

    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }
    //获取根节点
    public TreeNode getRoot() {
        return root;
    }

    //前序遍历
    public void frontShow(){
        if(root!=null){
            root.frontShow();   //其实就是去TreeNode里面实现
        }
    }
    //中序遍历
    public void midShow(){
        if(root!=null) {
            root.midShow();   //其实就是去TreeNode里面实现
        }
    }
    //后序遍历
    public void afterShow() {
        if (root != null) {
            root.afterShow();   //其实就是去TreeNode里面实现
        }
    }

    //前序查找
    public TreeNode frontSearch(int i){
        return root.frontSerach(i);
    }

    //删除子树
    public void delete(int i) {
        if(root.value==i){
            root=null; //当前的节点值刚好是要删除的 直接为null
        }else{
            root.delete(i); //删除节点
        }
    }

}

TreeNode类

public class TreeNode {
   //节点的权
        int value;
   //左儿子
        TreeNode leftNode;
   //右儿子
         TreeNode rightNode;

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public TreeNode(int value){
        this.value=value;
    }

    // 前序遍历(根左右)
    public void frontShow() {
        System.out.print(value+" "); //先输出当前节点内容
        if (leftNode != null) {
            leftNode.frontShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.frontShow();  //右节点
        }
    }

    // 中序遍历(左根右)
    public void midShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        System.out.print(value+" "); //先输出当前节点内容
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
    }

    //后序遍历(左右根)
    public void afterShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
        System.out.print(value+" "); //先输出当前节点内容
    }

    //前序查找
    public TreeNode frontSerach(int i){
        TreeNode target=null;
        if(this.value==i) {
            return this;   //当前节点的值就是要查找的值
        }else{
            if(leftNode!=null){
                target=leftNode.frontSerach(i); //左边的值查到的话给target
            }
            if(target!=null){
                return target;  //如果查到了就不为空 返回target
            }
            if(rightNode!=null){
                target=rightNode.frontSerach(i);  //右边的值可以查到
            }
        }
            return target;
    }

    //删除子树
    public void delete(int i) {
        TreeNode parent=this;  //把上一层节点存起来
        if(parent.leftNode!=null&&parent.leftNode.value==i){  //左节点是这个值
            parent.leftNode=null;
            return;
        }
        if(parent.rightNode!=null&&parent.rightNode.value==i){  //右节点是这个值
            parent.rightNode=null;
            return;
        }
        parent=leftNode;  //左边节点给上一层节点  递归
        if(parent!=null){
            parent.delete(i);
        }
        parent=rightNode;  //右边节点给上一层节点 递归
        if(parent!=null){
            parent.delete(i);
        }
    }

}

TestBinaryTree类

public class TestBinaryTree {
    public static void main(String[] args) {
      //创建一棵树
        BinaryTree binTree=new BinaryTree();
      //创建一个根节点
        TreeNode root=new TreeNode(1);
      //根节点赋给树
        binTree.setRoot(root);  //根节点赋给树

      //创建两个节点
        TreeNode rootL=new TreeNode(2);  //创建第二层的2
        TreeNode rootR=new TreeNode(3);  //创建第二层的3
      //新节点设置为根的两个节点
        root.setLeftNode(rootL);
        root.setRightNode(rootR);

      //给根的左节点2创建两个节点
         rootL.setLeftNode(new TreeNode(4));
         rootL.setRightNode(new TreeNode(5));
      //给根的右节点3创建两个节点
         rootR.setLeftNode(new TreeNode(6));
         rootR.setRightNode(new TreeNode(7));

      //前序遍历
        System.out.print("前序遍历:");
        binTree.frontShow();
        System.out.println();
      //中序遍历
        System.out.print("中序遍历:");
        binTree.midShow();
        System.out.println();
      //后序遍历
        System.out.print("后序遍历:");
        binTree.afterShow();
        System.out.println();

      //前序查找
        TreeNode result=binTree.frontSearch(3);
        System.out.println("前序查找结果:"+result);

     //删除子树(切点上层节点和它的关系)
        binTree.delete(2);
        binTree.frontShow();

    }
}

执行结果:

二叉树顺序存储

只考虑完全二叉树(编号连续)

顺序存储的性质

1. 第n个元素的左子节点 : 2*n+1
2. 第n个元素的右子节点 : 2*n+2
3. 任何一个节点的父节点 : (n-1)/2

具体类(三种遍历)

public class ArrayBinaryTree {

    int[] data;  //定义一个数组用于后面方法实现

    public ArrayBinaryTree(int[] data){   //构造方法传入数组
        this.data=data;
    }

    public void frontShow(){
        frontShow(0);
    }

    //前序遍历
    public void frontShow(int i){
        if(data==null||data.length==0){
            return;  //如果数组为空或者长度为0就输出0
        }
        System.out.println(data[i]);  //  输出当前的节点 (根)
        if(2*i+1<data.length){
            frontShow(2*i+1);  //递归  找左节点(2n+1)
        }
        if(2*i+2<data.length){
            frontShow(2*i+2);  //递归  找右节点(2n+2)
        }

    }

}

测试类

public class Shunxu {
    public static void main(String[] args) {
        int[] data=new int[]{1,2,3,4,5,6,7};  //定义一个链表存储的在数组内
        ArrayBinaryTree tree=new ArrayBinaryTree(data);  //传入数组
        tree.frontShow();  //前序遍历

    }
}

结果:

线索二叉树(双向链表)

线索二叉树概念：

1. 一个节点的前一个节点 --> 前驱节点(左边标记为lflag)
2. 一个节点的后一个节点 --> 后继节点(右边标记为rflag)

具体实现(可知前后节点信息)

中序线索化二叉树(关键点)

//中序线索化二叉树
       //用于临时存储前驱结点
           ThreadedNode pre=null;

   public void threadNodes(){
       threadNodes(root); //通过root不停的递归
   }

   public void threadNodes(ThreadedNode node){
       //1. 当前节点如果为null 直接返回
       if(node==null){
           return;
       }
       //2. 处理左子树
           threadNodes(node.leftNode);
         //2.1 如果当前节点没有了 我们处理它的前驱节点
             if (node.leftNode == null) {
                 node.leftNode=pre;    //当前节点的左指针 指向 前驱节点
                 node.leftType=1;  // 当前节点的左指针类型从0 -> 1
              }
         //2.2 前驱结点的右指针 如果是null(没有指向右下子树)
              if(pre!=null&&pre.rightNode==null){
                   pre.rightNode=node;
                   pre.rightType=1;
              }
         //2.3 每次处理一个节点，当前节点就是下一个节点的前驱节点(依次往下走 下一个的上面就是上一个)
              pre=node;

       //3. 处理右子树
           threadNodes(node.rightNode);
   }

遍历

public void threadIterate(){
    ThreadedNode node=root;
    while(node!=null){
        //循环找到最开始的节点
        while(node.leftType==0){
            node=node.leftNode;
        }
        System.out.println(node.value);  //打印当前节点的值
        //如果当前节点的右节点是后继节点，有可能后继节点还有后继节点
        while(node.rightType==1){
            node=node.rightNode;
            System.out.println(node.value);
        }
        node=node.rightNode;  //替换遍历的节点
    }
}

完整代码如下(三个类)

ThreadedBinaryTree类(二叉树的基础上添加中序线索树和遍历的方法)

public class ThreadedBinaryTree {
    
	ThreadedNode root;

    //设置根节点
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }
    //获取根节点
    public ThreadedNode getRoot() {
        return root;
    }

    //中序线索化二叉树
        //用于临时存储前驱结点
            ThreadedNode pre=null;

    public void threadNodes(){
        threadNodes(root); //通过root不停的递归
    }

    public void threadNodes(ThreadedNode node){
        //1. 当前节点如果为null 直接返回
        if(node==null){
            return;
        }
        //2. 处理左子树
            threadNodes(node.leftNode);
          //2.1 如果当前节点没有了 我们处理它的前驱节点
              if (node.leftNode == null) {
                  node.leftNode=pre;    //当前节点的左指针 指向 前驱节点
                  node.leftType=1;  // 当前节点的左指针类型从0 -> 1
               }
          //2.2 前驱结点的右指针 如果是null(没有指向右下子树)
               if(pre!=null&&pre.rightNode==null){
                    pre.rightNode=node;
                    pre.rightType=1;
               }
          //2.3 每次处理一个节点，当前节点就是下一个节点的前驱节点(依次往下走 下一个的上面就是上一个)
               pre=node;

        //3. 处理右子树
            threadNodes(node.rightNode);
    }

    //遍历线索二叉树
    public void threadIterate(){
        ThreadedNode node=root;
        while(node!=null){
            //循环找到最开始的节点
            while(node.leftType==0){
                node=node.leftNode;
            }
            System.out.println(node.value);  //打印当前节点的值
            //如果当前节点的右节点是后继节点，有可能后继节点还有后继节点
            while(node.rightType==1){
                node=node.rightNode;
                System.out.println(node.value);
            }
            node=node.rightNode;  //替换遍历的节点
        }
    }

    //前序遍历
    public void frontShow(){
        if(root!=null){
            root.frontShow();   //其实就是去TreeNode里面实现
        }
    }
    //中序遍历
    public void midShow(){
        if(root!=null) {
            root.midShow();   //其实就是去TreeNode里面实现
        }
    }
    //后序遍历
    public void afterShow() {
        if (root != null) {
            root.afterShow();   //其实就是去TreeNode里面实现
        }
    }

    //前序查找
    public ThreadedNode frontSearch(int i){
        return root.frontSerach(i);
    }

    //删除子树
    public void delete(int i) {
        if(root.value==i){
            root=null; //当前的节点值刚好是要删除的 直接为null
        }else{
            root.delete(i); //删除节点
        }
    }

}

TestThreadedBinaryTree测试类

public class TestThreadedBinaryTree {
    public static void main(String[] args) {
        //创建一棵树
        ThreadedBinaryTree binTree=new ThreadedBinaryTree();
        //创建一个根节点
        ThreadedNode root=new ThreadedNode(1);
        //根节点赋给树
        binTree.setRoot(root);  //根节点赋给树

        //创建两个节点
        ThreadedNode rootL=new ThreadedNode(2);  //创建第二层的2
        ThreadedNode rootR=new ThreadedNode(3);  //创建第二层的3
        //新节点设置为根的两个节点
        root.setLeftNode(rootL);
        root.setRightNode(rootR);

        //给根的左节点2创建两个节点
        rootL.setLeftNode(new ThreadedNode(4));
        ThreadedNode fiveNode=new ThreadedNode(5);
        rootL.setRightNode(fiveNode);
        //给根的右节点3创建两个节点
        rootR.setLeftNode(new ThreadedNode(6));
        rootR.setRightNode(new ThreadedNode(7));

        //中序遍历
        System.out.print("中序遍历:");
        binTree.midShow();
        System.out.println();
        System.out.println("---------------");

        //中序线索二叉树
        System.out.print("5后面的节点:");
        binTree.threadNodes();
        //查看5的后继节点
           ThreadedNode after=fiveNode.rightNode;
            System.out.println(after.value);
            binTree.threadIterate();  //测试遍历

    }
}

ThreadedNode节点类(只需要添加左右指针类型)

public class ThreadedNode {
    //节点的权
    int value;
    //左儿子
    ThreadedNode leftNode;
    //右儿子
    ThreadedNode rightNode;

    //用于标识指针类型
        int leftType;
        int rightType;

    public void setLeftNode(ThreadedNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(ThreadedNode rightNode) {
        this.rightNode = rightNode;
    }

    public ThreadedNode(int value){
        this.value=value;
    }

    // 前序遍历(根左右)
    public void frontShow() {
        System.out.print(value+" "); //先输出当前节点内容
        if (leftNode != null) {
            leftNode.frontShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.frontShow();  //右节点
        }
    }

    // 中序遍历(左根右)
    public void midShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        System.out.print(value+" "); //先输出当前节点内容
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
    }

    //后序遍历(左右根)
    public void afterShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
        System.out.print(value+" "); //先输出当前节点内容
    }

    //前序查找
    public ThreadedNode frontSerach(int i){
        ThreadedNode target=null;
        if(this.value==i) {
            return this;   //当前节点的值就是要查找的值
        }else{
            if(leftNode!=null){
                target=leftNode.frontSerach(i); //左边的值查到的话给target
            }
            if(target!=null){
                return target;  //如果查到了就不为空 返回target
            }
            if(rightNode!=null){
                target=rightNode.frontSerach(i);  //右边的值可以查到
            }
        }
        return target;
    }

    //删除子树
    public void delete(int i) {
        ThreadedNode parent=this;  //把上一层节点存起来
        if(parent.leftNode!=null&&parent.leftNode.value==i){  //左节点是这个值
            parent.leftNode=null;
            return;
        }
        if(parent.rightNode!=null&&parent.rightNode.value==i){  //右节点是这个值
            parent.rightNode=null;
            return;
        }
        parent=leftNode;  //左边节点给上一层节点  递归
        if(parent!=null){
            parent.delete(i);
        }
        parent=rightNode;  //右边节点给上一层节点 递归
        if(parent!=null){
            parent.delete(i);
        }
    }

}

结果:

二叉排序树BST(二叉查找树/二叉搜索树)

任何一个非叶子节点 : 左子节点<当前节点<右子节点

具体实现的代码框架

1. BinarySortTree类 : 一个root根节点 然后围绕写方法
2. Node节点类 : 具体方法实现
3. TestBinarySortTree测试类 : 测试结果

创建二叉排序树(添加节点)

实现思路

1. 空树 -- 直接让要添加的节点成为root根节点
2. 不为空树 -- 调用Node实现方法
   2.1 要添加的节点为空 -- 直接返回
   2.2 要添加的节点的值 < 当前节点的值
        2.2.1 当前节点有左节点 -- 继续递归找
        2.2.2 当前节点下面空 -- 直接添加到左节点的位置
   2.2 要添加的节点的值 > 当前节点的值
        2.2.1 当前节点有右节点 -- 继续递归找
        2.2.2 当前节点下面空 -- 直接添加到右节点的位置

BinarySortTree类写方法


//向二叉排序树中添加节点
    public void add(Node node){
        //1. 如果是空树
            if(root==null){
                root=node;  //这个节点添加为根节点
            }
        //2. 不是空树
            else{
                root.add(node); //调用Node类的方法添加
            }
    }

Node类具体实现

//向子树中添加节点
    public void add(Node node) {
        //1.传入的节点为空
        if(node==null){
            return;  //直接结束
        }
        //2.传入的节点的值和当前子树的根节点大小关系
          //2.1 传入节点值 < 子树的根节点的值
          if(node.value<this.value) {
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.left==null){
                  this.left=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.left.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
          //2.2 传入节点值 > 子树的根节点的值
          else{
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.right==null){
                  this.right=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.right.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
    }

查找节点

实现思路

1. 空树 -- 返回null
2. 不为空树 -- 调用Node实现方法
    2.1 传入的值 == 当前节点值   -- 返回当前节点
    2.2 传入的值 < 当前节点值    -- 找左边
         2.2.1 如果左边为空   -- 返回null
         2.2.2 如果左边不为空 -- 把左节点当做判断的当前节点(递归)  
    2.3 传入的值 > 当前节点值    -- 找右边
         2.3.1 如果右边为空   -- 返回null
         2.3.2 如果右边不为空 -- 把右节点当做判断的当前节点(递归)

BinarySortTree类写方法

//查找
   public Node search(int value){
     //1. 如果空树 -- 返回null
       if(root==null){
           return null;
       }
     //2. 如果不为空
       else{
           return root.search(value);
       }
   }

Node类具体实现

//查找节点
   public Node search(int value) {
     //1. 传入的值 == 当前节点值
       if(this.value==value){
           return this;  //返回当前节点
       }
     //2. 传入的值 < 当前节点值  -- 找左边
       else if(value<this.value){
           if(left==null){return null;}  //为空返回null
           return this.left.search(value);
       }
     //3. 传入的值 > 当前节点值  -- 找右边
       else{
           if(right==null){return null;}  //为空返回null
           return this.right.search(value);
       }
   }

测试添加节点和查询功能

public class TestBinarySortTree {

    public static void main(String[] args) {
        int[] arr=new int[]{7,3,10,12,5,1,9};
        //1. 创建一颗二叉排序树
            BinarySortTree bst=new BinarySortTree();
        //2. 循环添加
            for(int i:arr){
                bst.add(new Node(i));
            }
        //3. 中序遍历
            bst.midShow();
                 System.out.println("----------------------");
        //4. 查找数中的值
            Node node = bst.search(10);
                System.out.println("查找值为10的节点的值 : "+node.value);
            Node node2 = bst.search(20);
                System.out.println("查找值为20的节点是不是为空 : "+node2);
                System.out.println("查找值为20的节点的值 : "+node2.value);

    }

}

测试结果:

删除节点

三种情况概述

1. 删除叶子节点(两种情况): 让父节点不指向它(左边/右边)
2. 删除有一颗子树的节点(四种情况): 让它的子树代替它的位置(它在左/右边 子树在左/右边)
3. 删除有两颗子树的节点(两种情况): 
    1. 找到右边最小的替换掉删除的点(它没有叶子节点)
    2. 找到右边最小的替换掉删除的点+右节点替换掉最小的点的位置 (它有右节点(左节点的话就是第一种情况))

删除叶子节点(2种情况)

实现思路

1. 删除的叶子节点是左节点  -- 让父节点的左节点为空
2. 删除的叶子节点是右节点  -- 让父节点的右节点为空

图示解释

BinarySortTree类写方法


if(target.left==null&&target.right==null)
               {
                   //2.1.1 要删除的节点是父节点的左节点
                   if (parent.left.value == value)
                   {
                       parent.left = null;  //直接让父节点把它为null
                   }
                   //2.1.2 要删除的节点是父节点的右节点
                   else
                   {
                       parent.right = null; //直接让父节点把它为null
                   }
               }

Node类具体实现

//查找父节点
public Node searchParent(int value) {
    if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
        return this;
    }else {
        if(this.value>value&&this.left!=null){
            return this.left.searchParent(value);
        }else
            if(this.value<value&&this.right!=null){
            return this.right.searchParent(value);
        }
    }
    return null;
}

删除有一颗子树的节点(4种情况)

实现思路

1. 删除的节点是父节点的左/右节点？ 删除的节点的子节点是左/右节点？
    1.1 要删除的节点有的是左子节点
        1.1.1 要删除的节点是父节点的左节点(左左)   -- 将删除节点的左节点赋给父节点的左节点
        1.1.2 要删除的节点是父节点的右节点(右左)   -- 将删除节点的左节点赋给父节点的右节点
    1.2 要删除的节点有的是右子节点 
        1.2.1 要删除的节点是父节点的左节点(左右)   -- 将删除节点的右节点赋给父节点的左节点
        1.2.2 要删除的节点是父节点的右节点(右右)   -- 将删除节点的右节点赋给父节点的右节点

图示解释

BinarySortTree类写方法


//2.3.1 左子节点
     if(target.left!=null)
        {
            //2.3.1.1 要删除的节点是父节点的左节点
             if(parent.left.value==value)
             {
                  parent.left=target.left;     //要删除的是父节点的左节点 然后它有的是左节点
             }
             //2.3.1.2 要删除的节点是父节点的右节点
             else
             {
                  parent.right=target.left;     //要删除的是父节点的右节点 然后它有的是左节点
             }
         }
 //2.3.2 右子节点
      else
      {
            //2.3.2.1 要删除的节点是父节点的左节点
             if(parent.left.value==value)
             {
                  parent.left=target.right;     //要删除的是父节点的右节点 然后它有的是左节点
             }
            //2.3.2.2 要删除的节点是父节点的右节点
             else
             {
                  parent.right=target.right;     //要删除的是父节点的右节点 然后它有的是右节点
             }
     }

删除有两颗子树的节点(2种情况)

1. 右边最小值有没有子节点？
    1.1 右边最小值没有子节点 -- 直接将最小值的节点值赋给要删除的节点的值
    1.1 右边最小值有子节点(只有右节点) -- 直接将最小值的节点值赋给要删除的节点的值 +子节点的值赋给最小值的节点值

实现思路

BinarySortTree类写方法

if(target.left!=null&&target.right!=null)
  {
        //2.2.1 删除右子树最小的节点并且获取到该节点的值
               int min=deleteMin(target.right);  
        //2.2.2 替换目标节点中的值
               target.value=min;  //最小的值赋给要删除的节点的值
  }

完整代码

BinarySortTree类写方法

package com.company.erchapaixushu;
public class BinarySortTree {

    //root根节点
        Node root;

    //向二叉排序树中添加节点
    public void add(Node node){
        //1. 如果是空树
            if(root==null){
                root=node;  //这个节点添加为根节点
            }
        //2. 不是空树
            else{
                root.add(node); //调用Node类的方法添加
            }
    }

    //中序遍历(刚好是从小到大)
    public void midShow(){
        if(root!=null){
            root.midShow(root);  //查找这个根节点开始的中序遍历
        }
    }

    //查找节点
    public Node search(int value){
      //1. 如果空树 -- 返回null
        if(root==null){
            return null;
        }
      //2. 如果不为空
        else{
            return root.search(value);
        }
    }

    //删除节点
    public void delete(int value){
        if(root==null)
        {
            return; //空树直接返回
        }
        else
        {
            //1. 找到这个节点
                Node target = search(value);
                if(target==null)
                {
                    return;
                }
            //2. 找到它的父节点
                Node parent=searchParent(value);
                //2.1 要删除的是叶子节点
                if(target.left==null&&target.right==null)
                {
                    //2.1.1 要删除的节点是父节点的左节点
                    if (parent.left.value == value)
                    {
                        parent.left = null;  //直接让父节点把它为null
                    }
                    //2.1.2 要删除的节点是父节点的右节点
                    else
                    {
                        parent.right = null; //直接让父节点把它为null
                    }
                }

                //2.2 要删除的节点有两个子节点
                else
                    if(target.left!=null&&target.right!=null)
                    {
                        //2.2.1 删除右子树最小的节点并且获取到该节点的值
                            int min=deleteMin(target.right);
                        //2.2.2 替换目标节点中的值
                            target.value=min;
                    }

                //2.3 要删除的节点是有一个子节点
                    else
                    {
                        //2.3.1 左子节点
                        if(target.left!=null)
                        {
                            //2.3.1.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.left;     //要删除的是父节点的左节点 然后它有的是左节点
                            }
                            //2.3.1.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.left;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                        }
                        //2.3.2 右子节点
                        else
                        {
                            //2.3.2.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.right;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                            //2.3.2.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.right;     //要删除的是父节点的右节点 然后它有的是右节点
                            }
                        }
                    }
                }
        }

    //删除右边最小的节点并且获取该节点的值
    private int deleteMin(Node node) {
        Node target=node;
        //递归一直找最左边
        while(target.left!=null){  //右边的子树里面的左节点一直可以找下去  就一定是最小的
            target=target.left;
        }
        //最小的值有右子节点
        delete(target.value);  //那么剩下了一个叶子节点肯定会通过delete方法补上去
        return target.value;  //直接返回结果
    }

    //查找父节点
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

}

Node类写具体实现

package com.company.erchapaixushu;
public class Node {
    int value;  //此节点的值
    Node left;  //左节点
    Node right; //右节点

    public Node(int value){
        this.value=value;  //构造方法获取值
    }

    //向子树中添加节点
    public void add(Node node) {
        //1.传入的节点为空
        if(node==null){
            return;  //直接结束
        }
        //2.传入的节点的值和当前子树的根节点大小关系
          //2.1 传入节点值 < 子树的根节点的值
          if(node.value<this.value) {
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.left==null){
                  this.left=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.left.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
          //2.2 传入节点值 > 子树的根节点的值
          else{
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.right==null){
                  this.right=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.right.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
    }

    //中序遍历(刚好是从小到大)
    public void midShow(Node node) {
        if(node==null){
            return;  //为空就结束
        }
        midShow(node.left);  //左子树继续递归查
        System.out.println(node.value); //打印当前节点的值
        midShow(node.right);  //右子树继续递归查
    }

    //查找节点
    public Node search(int value) {
      //1. 传入的值 == 当前节点值
        if(this.value==value){
            return this;  //返回当前节点
        }
      //2. 传入的值 < 当前节点值  -- 找左边
        else if(value<this.value){
            if(left==null){return null;}  //为空返回null
            return this.left.search(value);
        }
      //3. 传入的值 > 当前节点值  -- 找右边
        else{
            if(right==null){return null;}  //为空返回null
            return this.right.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;   //它的左子节点或者右子节点符合条件
        }else {
            if(this.value>value&&this.left!=null){
                return this.left.searchParent(value);  //左边
            }else
                if(this.value<value&&this.right!=null){
                return this.right.searchParent(value);  //右边
            }
        }
        return null;  //都不满足 返回空
    }

}

TestBinarySortTree类

package com.company.erchapaixushu;
public class TestBinarySortTree {
    public static void main(String[] args) {
        int[] arr=new int[]{7,3,10,12,5,1,9};
        //1. 创建一颗二叉排序树
            BinarySortTree bst=new BinarySortTree();
        //2. 循环添加
            for(int i:arr){
                bst.add(new Node(i));
            }

        //3. 中序遍历
            bst.midShow();
                 System.out.println("----------------------");

        //4. 查找数中的值
            Node node = bst.search(10);
                System.out.println("查找值为10的节点的值 : "+node.value);
            Node node2 = bst.search(20);
                System.out.println("查找值为20的节点是不是为空 : "+node2);
                System.out.println("----------------------");

        //5. 查看父节点
            Node p1=bst.searchParent(10);
                System.out.println("输入的值的父节点是: "+p1.value);
                System.out.println("----------------------");

        //6. 删除叶子节点
            bst.delete(5); //删除叶子节点
            bst.midShow(); //删除之后查看
                System.out.println("----------------------");

        //7. 删除有一个节点的节点
            bst.delete(3); //有一个1的左节点
            bst.midShow();
                System.out.println("----------------------");

        //8. 删除有两个子节点
            bst.delete(7);  //根节点
            bst.midShow();
                System.out.println("----------------------");

    }

}

结果展示

叶子节点和有一个节点的值:

有两个节点的值:

平衡二叉树(AVL树)

平衡二叉树概念

前提: 必须是一个二叉排序树
条件: 任何一个非叶子节点满足: |左子树高度-右子树高度|<1
存在意义: 提高一般的二叉排序树的查找效率

准备获高度方法和add方法添加判断平衡

之前的add方法内部需要判断是不是平衡!!!!!!!
  //3. 查询是否平衡
          //3.1 左左情况(向右转)
            if(leftHight()-rightHight()>=2)    //左边太多 向右转(原来根的左节点作为新的根节点)
			{  
                rightRotate();  //调用具体实现内写的方法
            }
          //3.2 右右情况(向左转)
            if(leftHight()-rightHight()<=-2)    //右边太多 向左转(原来根的右节点作为新的根节点)
			{
                leftRotate(); //调用具体实现内写的方法
            }

-------------------------------

//当前节点的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;  //当前节点高度=左右子树最大的+1
    }

//左子树的高度 (避免为空)
    public int leftHight(){
        if(left==null){  //有可能为空
            return 0;
        }
        return left.height();
    }

//右子树的高度 (避免为空)
    public int rightHight(){
        if(right==null){  //有可能为空
            return 0;
        }
        return right.height();
    }

构造平衡二叉树(单旋转)

左左情况(右旋转)

左左情况怎么变换：

左左情况代码实现:

Node类实现：

//左左情况 -- 右旋转
  private void rightRotate() {
      //1. 创建新节点(值==当前节点的值)
          Node newRight=new Node(this.value);
      //2. 当前节点的右节点 --> 新节点的右节点   (原来的根节点和它右边子树已经挪走了)
          newRight.right=this.right;
      //3. 当前节点的左节点的右节点 --> 新节点的左节点  (原来的根节点的左节点的右子树成为新节点的左节点)
          newRight.left=this.left.right;
      //4. 当前节点值 --> 当前节点的左节点的值 (左边节点被替换掉)
          this.value=this.left.value;
      //5. 当前节点的左节点的左节点 --> 当前节点的左节点 (相当于直接把当前节点的左节点被扔出去)
          this.left=this.left.left;
      //6. 新节点 --> 当前节点的右节点
          this.right=newRight;
  }

右右情况(左旋转)

右右情况怎么变换：

右右情况代码实现:

Node类实现：

//右右情况 -- 左旋转
  private void leftRotate() {
      //1. 创建新节点(值==当前节点的值)
          Node newLeft=new Node(this.value);
      //2. 当前节点的左节点 --> 新节点的左节点   (原来的根节点和它左边子树已经挪走了)
          newLeft.left=this.left;
      //3. 当前节点的右节点的左节点 --> 新节点的右节点  (原来的根节点的右节点的左子树成为新节点的右节点)
          newLeft.right=this.right.left;
      //4. 当前节点值 --> 当前节点的右节点的值 (右边节点被替换掉)
          this.value=this.right.value;
      //5. 当前节点的右节点的右节点 --> 当前节点的右节点 (相当于直接把当前节点的右节点被扔出去)
          this.right=this.right.right;
      //6. 新节点 --> 当前节点的左节点
          this.left=newLeft;
  }

完整代码

Node类(二叉排序树的基础上添加查询高度的方法 + 左/右旋转的方法 + add方法判断是否平衡)

public class Node {
    int value;  //此节点的值
    Node left;  //左节点
    Node right; //右节点

    public Node(int value){
        this.value=value;  //构造方法获取值
    }

    //向子树中添加节点
    public void add(Node node) {
        //1.传入的节点为空
        if(node==null){
            return;  //直接结束
        }
        //2.传入的节点的值和当前子树的根节点大小关系
          //2.1 传入节点值 < 子树的根节点的值
          if(node.value<this.value) {
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.left==null){
                  this.left=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.left.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
          //2.2 传入节点值 > 子树的根节点的值
          else{
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.right==null){
                  this.right=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.right.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
        //3. 查询是否平衡
          //3.1 左左情况(向右转)
            if(leftHight()-rightHight()>=2){   //左边太多 向右转(原来根的左节点作为新的根节点)
                rightRotate();
            }
          //3.2 右右情况(向左转)
            if(leftHight()-rightHight()<=-2) {
                leftRotate();
            }

    }

    //右右情况 -- 左旋转
    private void leftRotate() {
        //1. 创建新节点(值==当前节点的值)
            Node newLeft=new Node(this.value);
        //2. 当前节点的左节点 --> 新节点的左节点   (原来的根节点和它左边子树已经挪走了)
            newLeft.left=this.left;
        //3. 当前节点的右节点的左节点 --> 新节点的右节点  (原来的根节点的右节点的左子树成为新节点的右节点)
            newLeft.right=this.right.left;
        //4. 当前节点值 --> 当前节点的右节点的值 (右边节点被替换掉)
            this.value=this.right.value;
        //5. 当前节点的右节点的右节点 --> 当前节点的右节点 (相当于直接把当前节点的右节点被扔出去)
            this.right=this.right.right;
        //6. 新节点 --> 当前节点的左节点
            this.left=newLeft;
    }


    //左左情况 -- 右旋转
    private void rightRotate() {
        //1. 创建新节点(值==当前节点的值)
            Node newRight=new Node(this.value);
        //2. 当前节点的右节点 --> 新节点的右节点   (原来的根节点和它右边子树已经挪走了)
            newRight.right=this.right;
        //3. 当前节点的左节点的右节点 --> 新节点的左节点  (原来的根节点的左节点的右子树成为新节点的左节点)
            newRight.left=this.left.right;
        //4. 当前节点值 --> 当前节点的左节点的值 (左边节点被替换掉)
            this.value=this.left.value;
        //5. 当前节点的左节点的左节点 --> 当前节点的左节点 (相当于直接把当前节点的左节点被扔出去)
            this.left=this.left.left;
        //6. 新节点 --> 当前节点的右节点
            this.right=newRight;
    }

    //当前节点的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;  //当前节点高度=左右子树最大的+1
    }

    //左子树的高度 (避免为空)
    public int leftHight(){
        if(left==null){  //有可能为空
            return 0;
        }
        return left.height();
    }

    //右子树的高度 (避免为空)
    public int rightHight(){
        if(right==null){  //有可能为空
            return 0;
        }
        return right.height();
    }


    //中序遍历(刚好是从小到大)
    public void midShow(Node node) {
        if(node==null){
            return;  //为空就结束
        }
        midShow(node.left);  //左子树继续递归查
        System.out.println(node.value); //打印当前节点的值
        midShow(node.right);  //右子树继续递归查
    }

    //查找节点
    public Node search(int value) {
      //1. 传入的值 == 当前节点值
        if(this.value==value){
            return this;  //返回当前节点
        }
      //2. 传入的值 < 当前节点值  -- 找左边
        else if(value<this.value){
            if(left==null){return null;}  //为空返回null
            return this.left.search(value);
        }
      //3. 传入的值 > 当前节点值  -- 找右边
        else{
            if(right==null){return null;}  //为空返回null
            return this.right.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;
        }else {
            if(this.value>value&&this.left!=null){
                return this.left.searchParent(value);
            }else
                if(this.value<value&&this.right!=null){
                return this.right.searchParent(value);
            }
        }
        return null;
    }

}

** TestBinarySortTree类(尝试输出)**

public class TestBinarySortTree {
    public static void main(String[] args) {
        int[] arr=new int[]{8,9,6,7,5,4};    //用于改变左边不平衡
      //int[] arr=new int[]{2,1,4,3,5,6};    //用于改变右边不平衡
        //1. 创建一颗二叉排序树
            BinarySortTree bst=new BinarySortTree();
        //2. 循环添加
            for(int i:arr){
                bst.add(new Node(i));
            }
        //3.查看高度
            System.out.println("左左情况变为平衡二叉树之后树的高度:"+bst.root.height());
        //4.查看根节点的值(更新后的)
            System.out.println("左左情况变为平衡二叉树之后根的值"+bst.root.value);
        //5.中序遍历
            System.out.println("中序遍历左左情况之后:");
            bst.midShow();
    }
}

BinarySortTree类(和之前的二叉排序树没有变化)

public class BinarySortTree {

    //root根节点
        Node root;

    //向二叉排序树中添加节点
    public void add(Node node){
        //1. 如果是空树
            if(root==null){
                root=node;  //这个节点添加为根节点
            }
        //2. 不是空树
            else{
                root.add(node); //调用Node类的方法添加
            }
    }

    //中序遍历(刚好是从小到大)
    public void midShow(){
        if(root!=null){
            root.midShow(root);  //查找这个根节点开始的中序遍历
        }
    }

    //查找节点
    public Node search(int value){
      //1. 如果空树 -- 返回null
        if(root==null){
            return null;
        }
      //2. 如果不为空
        else{
            return root.search(value);
        }
    }

    //删除节点
    public void delete(int value){
        if(root==null)
        {
            return; //空树直接返回
        }
        else
        {
            //1. 找到这个节点
                Node target = search(value);
                if(target==null)
                {
                    return;
                }
            //2. 找到它的父节点
                Node parent=searchParent(value);
                //2.1 要删除的是叶子节点
                if(target.left==null&&target.right==null)
                {
                    //2.1.1 要删除的节点是父节点的左节点
                    if (parent.left.value == value)
                    {
                        parent.left = null;  //直接让父节点把它为null
                    }
                    //2.1.2 要删除的节点是父节点的右节点
                    else
                    {
                        parent.right = null; //直接让父节点把它为null
                    }
                }

                //2.2 要删除的节点有两个子节点
                else
                    if(target.left!=null&&target.right!=null)
                    {
                        //2.2.1 删除右子树最小的节点并且获取到该节点的值
                            int min=deleteMin(target.right);
                        //2.2.2 替换目标节点中的值
                            target.value=min;
                    }

                //2.3 要删除的节点是有一个子节点
                    else
                    {
                        //2.3.1 左子节点
                        if(target.left!=null)
                        {
                            //2.3.1.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.left;     //要删除的是父节点的左节点 然后它有的是左节点
                            }
                            //2.3.1.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.left;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                        }
                        //2.3.2 右子节点
                        else
                        {
                            //2.3.2.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.right;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                            //2.3.2.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.right;     //要删除的是父节点的右节点 然后它有的是右节点
                            }
                        }
                    }
                }
        }

    //删除右边最小的节点并且获取该节点的值
    private int deleteMin(Node node) {
        Node target=node;
        //递归一直找最左边
        while(target.left!=null){  //右边的子树里面的左节点一直可以找下去  就一定是最小的
            target=target.left;
        }
        //最小的值有右子节点
        delete(target.value);  //那么剩下了一个叶子节点肯定会通过delete方法补上去
        return target.value;  //直接返回结果
    }

    //查找父节点
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

}

测试左左情况结果:

测试右右情况结果:

构造平衡二叉树(双旋转)

二叉排序树经过一次旋转之后还是不平衡的所以还需要第二次旋转

双旋转条件

1. 根的左节点的左高度 < 右高度(左少右多)  -- 1.1 根的左节点先左旋转 1.2 整体再右旋转
2. 根的右节点的右高度 < 左高度(左多右少)  -- 2.1 根的右节点先右旋转 2.2 整体再左旋转

举例：

Node类更新(单循环添加特定条件)

//3.1 左左情况(向右转)
            if(leftHight()-rightHight()>=2){   //左边太多 向右转(原来根的左节点作为新的根节点)
                //3.1.1 双旋转
                if(left!=null&&left.leftHight()<left.rightHight()){  //根的左节点的左高度<右高度
                    left.leftRotate();  //左节点先左旋转
                    rightRotate();  //整体再右旋转
                }
                //3.1.2 单旋转
                else{
                    rightRotate();
                }
            }
          //3.2 右右情况(向左转)
            if(leftHight()-rightHight()<=-2) {
                //3.2.1 双旋转
                if(right!=null&&right.rightHight()<right.leftHight()){  //根的右节点的右高度<左高度
                    right.rightRotate();  //右节点先右旋转
                    leftRotate();  //整体再左旋转
                }
                //3.2.2 单旋转
                else {
                    leftRotate();
                }

双旋转结果：

多路查找树

多路查找树分类：

1. 2-3树(B树的特例)
2. 2-3-4树(B树的特例)
3. B树和B+树

数据存储原理

B树提高普通二叉树的效率:

2-3树原理

满足条件：

1. B树中所有的叶子节点都在同一层
2. 有两个子节点的节点 --> 二节点  (二节点要么有两个节点，要么没有子节点)
3. 有三个子节点的节点 --> 三节点  (三节点要么有三个节点，要么没有子节点)
4. 有四个子节点的节点 --> 四节点  (四节点要么有四个节点，要么没有子节点)

B树和B+树原理

很多的二/三/四节点组成的二叉树

B树和B+树的区别

1. B+树的叶子节点存放内容(有序的链式结构)

2020-04-18

树

树概念

特殊树

二叉树

1. 满二叉树 : (最后一层是满的 很完美)   
2. 完全二叉树 : (编号之后中间序号没有断)
3. 二叉排序树/二叉查找树/二叉搜索树 : (左子树结点的关键字均<右子树的节点繁荣关键字)
4. 平衡二叉树 : (树的任意一个节点的左右子树的深度差不超过1)

线索二叉树

通过给节点给前后值能够知道这个节点前后节点是哪个

赫夫曼树

主要用于数据压缩(通过两个最小的值不断生成新节点)

平衡二叉树

一种二叉排序树 + |左子树高度-右子树高度|<1

多路查找树

主要学的是B和B+树

2020-04-15

排序

排序算法(8个)

排序算法概述：

性能对比：

冒泡排序

原理

1.比较两个相邻的元素，将值大的元素交换到右边(直到比较最后两个数)
2.然后开始下一轮，直至倒数第二个数交换成功

动态图：

具体实现

public class BubbleSort {
    public static void main(String[] args){
        int []arr=new int[]{5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr)); //先输出之前的数组
        maopao(arr) ;
        System.out.println(Arrays.toString(arr)); //输出排序之后的数组
    }

    //冒泡排序
    public static void maopao(int[] arr){
        //控制共比较多少轮(除过最后一个数都需要去排序)
        for(int i=0;i<arr.length-1;i++){
            //控制比较次数(每次排序时之前拍好的数字就不需要比较)
            for(int j=0;j<arr.length-1-i;j++){
                    if(arr[j]>arr[j+1]){
                        int temp=arr[j];  //三个数交换的方法
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
            }
        }
    }

}

结果：

快速排序

原理

1. 选择一个标准数(随机数/第一个) --> 一列数字分为左小右大
2. 确定左右两个指针low和high(low<high的情况下去将判断的数字区分成两类数)
3. 确定start和end两个数为数组的一开始和一结束(start<end的情况下快速排序还没有结束)
4. 判断指针左移和数字交换 (假设标准数为2)
    4.1 判断最右边开始的数字
            4.1.1 如果标准数比最右边的数小 2<=9  high指针左移 2 9
            4.1.2 如果标准数比最右边的数大 2>=1  用1把2替换掉 1 2  (一旦换数字就判断左边的去)
    4.2 接下来判断最左边开始的数字
            4.2.1 如果最左边的数比标准数小 1<=2  low指针右移  1 2
            4.2.2 如果最左边的数比标准数大 3>=2  用2把3替换掉 2 3  (一旦换数字就判断右边的去)
    4.3 不断地判断右边的只要换数字了就判断左边的只要换数字就继续交替执行!!!!!!!!!!!

5. 因为low和high碰在 要把重复的值用标准值去替换掉(low和high指向的同一个位置的那个数字要么替换了右边的要么被右边替换过来的所以肯定是两个重复的数字需要用标准值替换)
6. 接下来就是递归调用方法(不断地让两边去快排)
    6.1 处理左边的数字
         kuaisu(arr,start,low) //从start到low指针
    6.2 处理右边的数字
         kuaisu(arr,low+1,end) //从low+1的位置到end

动态图：

分析图示：

具体实现

public class QuickSort {
    public static void main(String[] args) {
        int []arr=new int[]{5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr));  //输出之前的数组
        kuaisu(arr,0,arr.length-1); //开头和结尾相当于指针
        System.out.println(Arrays.toString(arr));  //输出排序之后的数组
    }

    public static void kuaisu(int[] arr,int start,int end){  //传入数组和前后两个参数
        if(start<end){  //如果左边和右边冲突就是快速排序的结束条件
            //将第一个数作为标准数
           		 int biao=arr[start];
            //需要排序的下标
                 int low=start;
                 int high=end;

       //找比标准大的数字和比标准小的数字
           while(low<high){
            	while(low<high&&biao<=arr[high]){  // 假设标准数是2 <= 右边现在数是9
            	        high--; //右边的指针左移(符合条件)
            	    }
            //使用右边的数字替换左边的数字 (标准数是2 >= 右边是1  )
                arr[low]=arr[high];  //用1把2替换掉(做到小数左移)

             //如果左边的数字比标准数小
                while(low<high&&arr[low]<=biao){
                    	low++;  //左边指针右移(符合条件)
                	}
             //使用左边的数字替换右边的数字 ( 左边的8 >= 标准数是2) 
                arr[high]=arr[low];  //将8替换2

          }

          //标准数替换掉重复的数字(low/high都可以)
          	  arr[low]=biao;  
          //处理所有小的数字
          	  kuaisu(arr,start,low);
          //处理所有大的数字
          	  kuaisu(arr,low+1,end);
        }
    }

}

结果：

插入排序(直接插入排序)

原理

1. 最大的特点就是：我在排当前数的时候前面的数必须是有序的
2. 从第二个数开始
    2.1 遍历所有前面的数字 如果当前数(2) < 前面的数字(3 4) : 说明我还可以左移 (前面的数字给后面的数字)
    2.2 如果当前数(2) > / = 前面的数(1 2 3) : 说明已经不用挪动了就可以2替换3的位置 (3已经在上面的条件里面挪到后面了)

动态图：

具体实现


public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //int n=input.nextInt();
        int[] a=new int[]{1,5,3,6,9,4,11,87,23};
        find(a);  //调用方法返回结果
        System.out.println(Arrays.toString(a));
    }

    public static void find(int[] a){
      for(int i=1;i<a.length;i++){  //从第二位开始遍历
          int temp=a[i];  //将要插入的数字存放到temp里面
          int flag; //定义flag下标 因为for循环外面还要用
          for(flag=i-1;flag>=0&&a[flag]>temp;flag--){  //找0到i-1位置遍历
              a[flag+1]=a[flag];  //只有满足前面比要插入的数字大 才让他往后挪动
          } 
          a[flag+1]=temp;  //最后flag通过for会给一个值 然后将要插入的数字插入位置
      }
    }

}

结果：

插入排序(希尔排序)

原理

1. 根据(总数/2)的方法不断去组队排序 
  假如是9个数字 ：     
    1.1 第一轮是9/2=4(按照4的间隔对应的数字排序 0和4和8位置的排序对比 1和5的对比 2和6的对比 3和7的对比)
    1.2 第二轮是4/2=2(按照2的间隔对应的数字进行排序对比 ) 
    1.3 直到/2为1的时候结束
2. 通过这个方法比直接插入排序效率高(万一最后一个数字是最小的话就可以很快速的放到前面去)

动态图：

具体实现

public class ShellSort {
    public static void main(String[] args) {
        int []arr=new int[]{5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr){
        //遍历所有的步长
            for(int d=arr.length/2;d>0;d/=2){
                //遍历所有的元素
                    for(int i=d;i<arr.length;i++){ 
                      //遍历一个组的所有元素
                        for(int j=i-d;j>=0;j-=d){  //j是从
                            if(arr[j]>arr[j+d]){  //前大于后  3 2
                                int temp=arr[j];  //两个数交换
                                arr[j]=arr[j+d];
                                arr[j+d]=temp;
                            }
                        }
                    }
            }
    }

}

结果：

选择排序(简单选择排序)

原理

1. 我们就是每次都判断之后的所有的数字。每次把最小的数字换到判断的这个点上。
2. 如果后面有比现在的位置小的数字就把下标记下来最后让之前的最小的数字的下标和现在的数字更换位置。

具体实现


public class XuanZ {
    public static void main(String[] args) {
        int[] arr=new int[]{3,4,5,7,1,2,0,3,6,8};
        System.out.println(Arrays.toString(arr));  //输出未排序的顺序
        	xuanze(arr);
        System.out.println(Arrays.toString(arr));  //排序之后的顺序
    }

    public static void xuanze(int[] arr) {
        //遍历所有的数
            for(int i=0;i<arr.length;i++){
                int minIndex=i;
            //把当前遍历的数和后面所有的数依次进行比较
                //记录最小的数的下标
                for(int j=i+1;j<arr.length;j++){ //从第二个开始
                    if(arr[minIndex]>arr[j]){  //后面有数字更小 就把它记录下
                        minIndex=j;
                    }
                }
                //最小的数和当前遍历的下标不一致  后面有数字替换了当前的数字
                    if(i!=minIndex){
                        int temp=arr[i];
                        arr[i]=arr[minIndex];
                        arr[minIndex]=temp;
                    }

            }
    }

}

结果：

归并排序(递归)

原理

1. 将其划分为两部分一直到不能分解(递归)
2. 两部分开始归并 
3. 最终返回回来就是一个排序好的数组

递归思路：

动态图：

具体实现


public class GuiB {
    public static void main(String[] args) {
        int[] arr=new int[]{1,3,5,2,4,6,8,10};
        System.out.println(Arrays.toString(arr)); //排序前
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));  //排序后
    }

    public static void mergeSort(int[] arr,int low,int high){
        int middle=(high+low)/2;  //取中间位置
        if(low<high)
        {
            mergeSort(arr,low,middle);  //处理左边
            mergeSort(arr,middle+1,high);  //处理右边
            merge(arr,low,middle,high);  //归并
        }
    }

    public static void merge(int[]arr,int low,int middle,int high){
       //用于存储归并后的临时数组
        int[] temp=new int[high-low+1];
       //记录第一个数组中需要遍历的下标
        int i=low;
       //记录第二个数组中需要遍历的下表
        int j=middle+1;
       //记录临时变量存放下标
        int index=0;
      //遍历两个数组 取出小的数字放如临时数组中
        while (i<=middle&&j<=high){
            if(arr[i]<=arr[j]){   //左边数组的小  放入之后下标++
                temp[index]=arr[i];
                i++;
                index++;
            }
            else{   //右边数组的小 放入之后下标++
                temp[index]=arr[j];
                j++;
                index++;
            }
        }
    //处理多余数据
        while(j<=high){   //右边数组多了
            temp[index]=arr[j];
            j++;
            index++;
        }
        while(i<=middle){  //左边数组多了
            temp[index]=arr[i];
            i++;
            index++;
        }

     //临时数组重新存入
        for(int k=0;k<temp.length;k++){
            arr[k+low]=temp[k];
        }

    }

}

结果：

基数排序(适用多位数)

原理

1. 大概思路就是每次对排序的数字进行取余(个位到十位一直到最大数字的最高位停止)
2. 每次取余之后把数字放在余数和0..9对应的二维数组内 (第一次是99 取余之后是9就放在二维数组第一个属性是9的位置里面)
3. 然后按照0..9的顺序从二维数组取出来放入原来的数组 然后又取余数按照余数放进二维数组
4. 一直到最后一次取出来就肯定是按顺序

动态图：

具体实现

public class RadixSort {
    public static void main(String[] args) {
     int[] arr=new int[]{23,6,9,189,45,6,8,123549,56};  //需要排序的数字
        	jishu(arr);
        System.out.println(Arrays.toString(arr)); //排序之后
    }

    public static void jishu(int[] arr){
        //存储数组中最大的数字  --确定排几次
            int max=Integer.MIN_VALUE;
            for(int i=0;i<arr.length;i++){
                if(arr[i]>max){
                    max=arr[i];  //取出来最大的数字 后面会求出几位数控制循环范围
                }
            }

        //求最大数字是几位数
            int maxLength=(max+"").length(); //数字+""就会成为字符串

        //第一个下标就是表示余数的十个可能 第二个就是每个对应下标存放多少个数字
            int[][] temp=new int[10][arr.length];  //0..9的二维数组存放对应余数的数字
        //记录相应数组中数个数
            int[] counts=new int[10];  //记录0..9的二维数组里面存了几个数字

            for(int i=0,n=1;i<maxLength;i++,n*=10){
                for(int j=0;j<arr.length;j++){  //每个数字每次计算余数
                    int ys=arr[j]/n%10;  //获取余数
                    temp[ys][counts[ys]]=arr[j];  //counts[ys]是0..9对应下标存放了几个(方便二维数组存放顺序)
                    counts[ys]++;  //存放的数字+1
                }

              //循环取数
                int index=0;
                for(int k=0;k<counts.length;k++){
                    if(counts[k]!=0){  //记录存了几个数字的数组不为空(二维数组里面有数)
                        for(int l=0;l<counts[k];l++){  //遍历二维数组中存的排序的数字
                                  arr[index++]=temp[k][l];  //数字再放到原来数组
                        }              
                    }
                }

			//让记录二维数组存数的数组全部清空 (下一次取余计数好用!!!)
				for(int z=0;z<counts.length;z++){
	                    counts[z]=0;
	                }
	
	       }

    }
}

结果：

基数排序(队列)

现在使用队列进行存放(队列添加)和每一次存放之后返回(出队) – 减少了二维数组和计数数组的麻烦

队列

public class MyQueue {

    int[] elements;

    public MyQueue() {
        elements=new int[0];
    }

    //入队
    public void add(int element) {
        // 创建一个新的数组
        int[] newArr = new int[elements.length + 1];
        // 把原数组中的元素复制到新数组中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        // 把添加的元素放入新数组中
        newArr[elements.length] = element;
        // 使用新数组替换旧数组
        elements = newArr;
    }

    //出队
    public int poll() {
        //把数组中的第0个元素取出来
        int element = elements[0];
        //创建一个新的数组
        int[] newArr = new int[elements.length-1];
        //复制原数组中的元素到新数组中
        for(int i=0;i<newArr.length;i++) {
            newArr[i]=elements[i+1];
        }
        //替换数组
        elements=newArr;
        return element;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return elements.length==0;
    }

}

主要实现类

public class RqdixQueueSort {
    public static void main(String[] args) {
        int[] arr=new int[]{23,6,9,189,45,6,8,123549,56};
            jishu(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void jishu(int[] arr){
        //存储数组中最大的数字  --确定排几次
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        //求最大数字是几位数
        int maxLength=(max+"").length(); //数字+""就会成为字符串

        //临时存放数字的队列(先进先出)
            MyQueue[] temp=new MyQueue[10];
            for(int i=0;i<temp.length;i++){
                temp[i]=new MyQueue();
            }

        for(int i=0,n=1;i<maxLength;i++,n*=10){
            for(int j=0;j<arr.length;j++){  //每个数字每次计算余数
                int ys=arr[j]/n%10;  //获取余数
                temp[ys].add(arr[j]); //队列添加
            }

            //数字取出来
            int index=0;
            for(int k=0;k<temp.length;k++){
               while(!temp[k].isEmpty()){  //记录存了几个数字的数组不为空
                    arr[index++]=temp[k].poll();  //队列出队
                }
            }

        }

    }
}

堆排序(堆)

原理

1. 升序 : 小顶堆
2. 降序 : 大顶堆

动态图：

具体实现

2020-04-15

时间复杂度和空间复杂度分析

衡量算法的优劣

1. 事后统计的方法
2. 事前分析估算的方法

时间复杂度

T(n)=O(f(n))

T(n)：是指算法中基本操作语句的重复执行次数是问题规模n的某个函数
O(f(n)):是算法的渐进时间复杂度

常见时间复杂度

	常数阶O(1)
	对数阶O(log2n)
	线性阶O(n)
	线性对数阶O(nlog2n)
	平方阶O(n2)
	立方阶O(n3)
	k次方阶O(nk)
	指数阶O(2n)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

T(n)不同但是时间复杂度可能相同

例如：

T(n)=n²+5n+6 与 T(n)=3n²+3n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。

时间复杂度求法

1. 用1 代理运行实践中所有的加法常数
2. 只保留最高阶项
3. 去除最高阶项系数

2020-04-14

递归

递归(效率低)

不断调用自己

斐波那契数列

第三个数开始是前两个数之和

汉诺塔(递归)

所有问题都考虑成一个盘子和两个盘子的情况!!!!!!

public class TestHanoi {
    public static void main(String[] args) {
        han(3,'A','B','C');  //3个盘子
    }

    //n个盘子 从A通过B传到C
    public static void han(int n,char A,char B,char C){
        
		if(n==1) {
            System.out.println("第一个盘子从"+A+"移到"+C);
        }

        else {
          //移动上面所有的盘子到中间位置(最后一个它自己走上面的方法从A->C)
            han(n-1,A,C,B);
            System.out.println("第"+n+"个盘子从"+A+"移到"+C);
          //把上面的所有盘子从中间位置移到目标位置
            han(n-1,B,A,C);   //把B上面的盘子通过A全部放到C去
        }

    }

}

以三个盘子为例：

2020-04-12

SpringBoot

1.SpringBoot概述

Spring Boot是Spring提供的一个子项目，用于快速构建Spring应用程序

1.1 SpringBoot特性

1.1.1 起步依赖

1	本质上就是一个Maven坐标，整合了完成一个功能需要的所有坐标

1.1.2 自动配置

1	遵循约定大约配置的原则，在boot程序启动后，一些bean对象会自动注入到ioc容器，不需要手动声明，简化开发

1.1.3 其它特性

1
2
3

1.内嵌的Tomcat、Jetty（无需部署WAR文件,只需要jar包即可）
2.外部化配置
3.不需要XML配置(使用两种配置文件:properties/yml)

2. SpringBoot快速配置启动

需求:

使用步骤:

2.1 创建springboot项目(需要联网)

基于Spring官方骨架，创建SpringBoot工程

基本信息描述完毕之后，勾选web开发相关依赖

点击Finish之后，就会联网创建这个SpringBoot工程，创建好之后，结构如下：

2.2 定义请求处理类

运行SpringBoot自动生成的引导类

2.3 运行启动类

运行SpringBoot自动生成的引导类

打开浏览器，输入 http://localhost:8080/hello

2.4 Web分析

3. 配置文件(两种)

3.1 application.properties配置文件

3.2 application.yml配置文件

3.3 两者对比

3.4 配置文件书写和获取(yml为例)

1.第三方技术配置信息

2.自定义配置信息

书写：

获取：

1
2
3

@Value("${键名}")

@ConfigurationProperties(prefix="共同上级/前缀")

1:Value注解:

2.ConfigurationProperties注解(设定共同前缀):

4. 整合Mybatis

整体图

4.1 添加依赖

4.2 添加配置

4.3 书写业务逻辑

1.User类

实体类主要负责编写数据库的实体信息,和数据库的表要对应

package com.itheima.springbootmybatis.pojo;
public class User {
    private Integer id;
    private String name;
    private Short age;
    private Short gender;
    private String phone;
    public User() {
    }
    public User(Integer id, String name, Short age, Short gender, String phone) {
        this.id = id;
        this.name = name;
        this.age = age;
        this.gender = gender;
        this.phone = phone;
    }
    public Integer getId() {
        return id;
    }
    public void setId(Integer id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Short getAge() {
        return age;
    }
    public void setAge(Short age) {
        this.age = age;
    }
    public Short getGender() {
        return gender;
    }
    public void setGender(Short gender) {
        this.gender = gender;
    }
    public String getPhone() {
        return phone;
    }
    public void setPhone(String phone) {
        this.phone = phone;
    }
    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                ", gender=" + gender +
                ", phone='" + phone + '\'' +
                '}';
    }
}

2.UserMapper类

主要编写sql语句 ** **–主要用到Mapper和Select注解

package com.itheima.springbootmybatis.mapper;
import com.itheima.springbootmybatis.pojo.User;
import org.apache.ibatis.annotations.Mapper;
import org.apache.ibatis.annotations.Select;

@Mapper
public interface UserMapper {
    @Select("select * from user where id=#{id}")
    public User findById(Integer id);
}

3.UserService类

主要编写所有需求方法

package com.itheima.springbootmybatis.Service;
import com.itheima.springbootmybatis.pojo.User;

public interface UserService {
    public User findById(Integer id);
}

主要实现接口方法，调用Mapper类对象实现 –主要用到Service和Autowired注解

package com.itheima.springbootmybatis.Service.impl;
import com.itheima.springbootmybatis.Service.UserService;
import com.itheima.springbootmybatis.mapper.UserMapper;
import com.itheima.springbootmybatis.pojo.User;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

@Service
public class UserServiceImpl implements UserService {
    @Autowired
    private UserMapper userMapper;
    @Override
    public User findById(Integer id) {
        return userMapper.findById(id);
    }
}

4.UserController类

主要调用Service接口对象实现 –主要用到RestController和Autowired和RequestMapping注解

package com.itheima.springbootmybatis.controller;
import com.itheima.springbootmybatis.Service.UserService;
import com.itheima.springbootmybatis.pojo.User;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class UserController {
    @Autowired
    private UserService userService;
    @RequestMapping("/findById")
    public User findById(Integer id){
        User byId = userService.findById(id);
        return byId;
    }
}

5.最终结果

5.Bean扫描(自动注解)

Springboot启动类的注解可以自动扫描，并且默认扫描启动类所在包和子包

6.来自第三方的Bean对象

6.1 怎么引入

步骤一: maven下载

步骤二：pom.xml导入jar依赖

步骤三：刷新maven之后在外部库查看

6.2 怎么注解

如果要注册的bean对象来自于第三方（不是自定义的），是无法用 @Component 及衍生注解声明bean的只能使用以下两种方式去解决bean注解

方式一：Bean注解

以下是两种方法的区别

1.存放到启动类

2.存放到配置类(@Configuration)

配置类是可以写很多bean对象，并且配置类必须存放在启动类的同级和下一级包位置，方便Bean扫描(如果放在外面就需要方法2import注解了)

方式二：Import注解

1.导入配置类

2.导入ImportSelector接口实现类

先创建一个java类重写ImportSelector接口的方法，返回值就是一个数组(要放入的bean对象)

然后在启动类中添加import注解就可以

方式三: EnableXxxx注解(封装@Import注解)

然后在启动类中添加import注解就可以

6.3 注册条件(符合条件才可以注入ioc容器)

Springboot提供了Conditional注解解决注册时候对象赋值问题，但是过于复杂所以给出了常用的三个相关注解

1. @ConditionalOnProperty(从配置文件判断)

从配置文件中的读取，读取成功注入，读取失败不注入

2.@ConditionalOnMissingBean(从IOC容器判断)

因为Country需要从配置文件中读取注入，失败了所以没有注入，这样的话下面的province就会注入

3.@ConditionalOnClass(从当前环境判断)

如果环境中有当前类就注入，没有就不注入

7.自动配置原理

7.1 原理图

其实就是将自动配置类写到一个.imports配置文件中

上图描述：

第二遍的理解

7.2 如何实现

原来的情况: 导入jar包之后只有类，需要自己写配置类和启动类import导入

现在的情况: 导入jar包的时候里面不仅仅有类，还有配置类，imports配置文件等，不需要添加任何其他操作

8.自定义starter(公共组件)

主要是自己写autoconfigure和starter两个组件

8.1 提供核心组件1-autoconfigure模块

8.2 提供核心组件2-starter模块

8.3 使用starter模块

9.Springboot父工程(为其他依赖提供兼容版本)

之前开发的SpringBoot入门案例中，我们通过maven引入的依赖，是没有指定具体的依赖版本号的。因为每一个SpringBoot工程，都有一个父工程。依赖的版本号，在父工程中统一管理

10.内置tomcat

我们的SpringBoot中，引入了web运行环境(也就是引入spring-boot-starter-web起步依赖)，其内部已经集成了内置的Tomcat服务器。

我们可以通过IDEA开发工具右侧的maven面板中，就可以看到当前工程引入的依赖。其中已经将Tomcat的相关依赖传递下来了，也就是说在SpringBoot中可以直接使用Tomcat服务器

当我们运行SpringBoot的引导类时(运行main方法)，就会看到命令行输出的日志，其中占用8080端口的就是Tomcat

11. Web后端开发总结

web后端开发现在基本上都是基于标准的三层架构进行开发的，在三层架构当中，Controller控制器层负责接收请求响应数据，Service业务层负责具体的业务逻辑处理，而Dao数据访问层也叫持久层，就是用来处理数据访问操作的，来完成数据库当中数据的增删改查操作。

在三层架构当中，前端发起请求首先会到达Controller(不进行逻辑处理)，然后Controller会直接调用Service 进行逻辑处理， Service再调用Dao完成数据访问操作

如果我们在执行具体的业务处理之前，需要去做一些通用的业务处理，比如：我们要进行统一的登录校验，我们要进行统一的字符编码等这些操作时，我们就可以借助于Javaweb当中三大组件之一的过滤器Filter或者是Spring当中提供的拦截器Interceptor来实现

而为了实现三层架构层与层之间的解耦，我们学习了Spring框架当中的第一大核心：IOC控制反转与DI依赖注入

所谓控制反转，指的是将对象创建的控制权由应用程序自身交给外部容器，这个容器就是我们常说的IOC容器或Spring容器。

而DI依赖注入指的是容器为程序提供运行时所需要的资源

除了IOC与DI我们还讲到了AOP面向切面编程，还有Spring中的事务管理、全局异常处理器，以及传递会话技术Cookie、Session以及新的会话跟踪解决方案JWT令牌，阿里云OSS对象存储服务，以及通过Mybatis持久层架构操作数据库等技术

我们在学习这些web后端开发技术的时候，我们都是基于主流的SpringBoot进行整合使用的。而SpringBoot又是用来简化开发，提高开发效率的。像过滤器、拦截器、IOC、DI、AOP、事务管理等这些技术到底是哪个框架提供的核心功能

Filter过滤器、Cookie、 Session这些都是传统的JavaWeb提供的技术。

JWT令牌、阿里云OSS对象存储服务，是现在企业项目中常见的一些解决方案。

IOC控制反转、DI依赖注入、AOP面向切面编程、事务管理、全局异常处理、拦截器等，这些技术都是 Spring Framework框架当中提供的核心功能。

Mybatis就是一个持久层的框架，是用来操作数据库的。

在Spring框架的生态中，对web程序开发提供了很好的支持，如：全局异常处理器、拦截器这些都是Spring框架中web开发模块所提供的功能，而Spring框架的web开发模块，我们也称为：SpringMVC

SpringMVC不是一个单独的框架，它是Spring框架的一部分，是Spring框架中的web开发模块，是用来简化原始的Servlet程序开发的

外界俗称的SSM，就是由：SpringMVC、Spring Framework、Mybatis三块组成。

基于传统的SSM框架进行整合开发项目会比较繁琐，而且效率也比较低，所以在现在的企业项目开发当中，基本上都是直接基于SpringBoot整合SSM进行项目开发的

2020-04-12

链表

单链表

单链表图示:

单链表的基础操作

具体实现功能:

1. 添加节点(将指针不停指向下一个 判空) 
2. 查询下一个节点(返回this.next) 
3. 获取当前节点数据(返回this.data) 
4. 判断是不是最后一个节点(只需要返回next是不是为空)

具体实现

public class Node {
    //节点内容
        int data;

    //下一个节点
        Node next;

        public Node(int data){
            this.data=data;
        }

    //追加节点
        public Node append(Node node){
            //当前节点
                Node currentNode =this;
                while(true){
                    //取出下一个节点赋给上一个节点
                    Node nextNode=currentNode.next;
                    if(nextNode==null)
                    {
                        break;  //下一个为空就跳出
                    }
                    currentNode=nextNode;  //将当前指针挪到下一个
                }
                //把想要追加的追加上去(上面循环已经肯定是到最后一个节点了)
                    currentNode.next=node;

                return this;  //可不停地追加  n1.append(n2).append(3)...
        }

    //获取下一个节点
        public Node next(){
            return this.next;  //返回next
        }

    //获取数据
        public int getData(){
            return this.data;  //获取数据
        }

    //判断是否是最后一个
        public boolean isLast(){
            return next==null;
        }
}

测试Test类

public class Test {
    public static void main(String[] args){
      //创建节点
        Node n1=new Node(1);
        Node n2=new Node(2);
        Node n3=new Node(3);
        n1.append(n2).append(n3).append(new Node(4));  // 1 --> 2 --> 3 --> 4

        System.out.println(n1.next().next().next().getData()); //数据是4的节点
        System.out.println(n1.next().next().next().isLast());  //判断数据是4的节点是不是最后一个
    }
}

测试结果：

单链表删除节点(让下下一个节点连到本节点)

//删除节点
       public  void removeNext(){
         //获取下下一个节点
          Node newNext= next.next;
         //下下一个节点直接给这个节点(直接把下一个节点删除)
           this.next=newNext;
       }

单链表插入节点(先管卸下去的节点然后再连接)

方法实现解释：

假设现在是 1 --> 2 --> 3 --> 4  我们想把5插入到2后面
具体实现:
		1. 将原来的下一个节点3先存到一个变量节点
		2. 将5连接到2后面  1 --> 2 --> 5  ||  3 --> 4
		3. 现在5已经替换了3的位置 把存3的那个变量节点连到5后面  1 --> 2 --> 5 --> 3 --> 4

方式实现


//插入节点(先将旧的插到新的上面 新的在插到要插的位置)
            public void after(Node node){
                 //获取下一个节点为下下一个节点
                    Node nextNext=next;  //现在的这个下一个节点存到一个叫nextNext的节点
                 //新加入的节点成为这个节点的下一个节点
                    this.next=node;
                 //插入的节点后面把存的那个节点接上去
                    node.next=nextNext;
            }

测试Test类

public class Test {
    public static void main(String[] args){
      //创建节点
        Node n1=new Node(1);
        Node n2=new Node(2);
        Node n3=new Node(3);
        n1.append(n2).append(n3).append(new Node(4));  // 1 --> 2 --> 3 --> 4

        Node n5=new Node(5);  //要插入的n5节点
        n1.next().after(n5); //插入到n2的后面  n1.next()就是n2
        n1.show(); //展示所有节点

    }
}

插入n5在n2后面：

循环链表

循环链表图示:

方法实现(下一个节点指向当前节点)

对比单链表: 最后一个的next要指向开头的节点

1 2	//下一个节点 LoopNode next=this;

具体代码：

public class LoopNode {
    //节点内容
    int data;

    //下一个节点
    LoopNode next=this;

    public LoopNode(int data){
        this.data=data;
    }

    //获取下一个节点
    public LoopNode next(){
        return this.next;  //返回next
    }

    //获取数据
    public int getData(){
        return this.data;  //获取数据
    }

    //判断是否是最后一个
    public boolean isLast(){
        return next==null;
    }

    //删除节点
    public  void removeNext(){
        //获取下下一个节点
        LoopNode newNext= next.next;
        //下下一个节点直接给这个节点(直接把下一个节点删除)
        this.next=newNext;
    }


    //插入节点(先将旧的插到新的上面 新的在插到要插的位置)
    public void after(LoopNode node){
        //获取下一个节点为下下一个节点
        LoopNode nextNext=next;  //下一个节点给下下一个节点
        //新加入的节点成为这个节点的下一个节点
        this.next=node;
        //下下一个节点成为新节点的下一个节点
        node.next=nextNext;
    }


}

测试Test类

public class Test {
    public static void main(String[] args){
      //创建节点
        LoopNode n1=new LoopNode(1);
        LoopNode n2=new LoopNode(2);
        LoopNode n3=new LoopNode(3);
        LoopNode n4=new LoopNode(4);

      //插入节点
        n1.after(n2);  //现在只有 1 --> 2
        n2.after(n3);  //现在是 1 --> 2 -->3
        System.out.println(n1.next().getData());  // 1的下一个节点的内容应该输出2
        System.out.println(n2.next().getData());  // 2的下一个节点的内容应该输出3
        System.out.println(n3.next().getData());  // 3的下一个节点的内容应该输出1
    }
}

具体实现结果：

双向循环链表

双向循环链表图示：

方式实现

图示解释：

具体代码：

public class DoubleNode {
    //上一个节点
        DoubleNode pre=this;  //一开始这个节点的前一个和后一个都是它自己!!!
    //下一个节点
        DoubleNode next=this;
    //节点数据
        int data;

    public DoubleNode(int data) {
        this.data=data;
    }

    //增加节点
        public void after(DoubleNode node){
          //原来的下一个节点
            DoubleNode nextNext=next;
          //把新节点作为当前节点的下一个节点
            this.next=node;
          //把当前节点作为新节点的前一个节点
            node.pre=this;
          //让原来的下一个节点作为新节点的下一个节点
            node.next=nextNext;
          //让原来的下一个节点的上一个节点作为新节点
            nextNext.pre=node;
        }

    //下一个节点
        public DoubleNode next() {
            return this.next;
        }

    //上一个节点
        public DoubleNode pre(){
            return this.pre;
        }

    //获取数据
        public int getData(){
            return this.data;
        }

}

测试Test类

public class Test {
    public static void main(String[] args){
        //创建节点
        DoubleNode n1 = new DoubleNode(1);
        DoubleNode n2 = new DoubleNode(2);
        DoubleNode n3 = new DoubleNode(3);
        //追加节点
        n1.after(n2);
        n2.after(n3); // 1 2 3 循环
        //查看上一个，自己，下一个节点的内容
        System.out.println(n2.pre().getData());  // n2的前一个节点的数据  1
        System.out.println(n2.getData());  // n2的数据  2
        System.out.println(n2.next().getData()); // n2的下一个节点的数据 3
        System.out.println(n3.next().getData()); // n3的下一个节点的数据 1
        System.out.println(n1.pre().getData());  // n1的前一个节点的数据 3
    }
}

测试代码结果：

2020-04-11

队列

队列(先进先出)

队列就跟排队一样

具体实现

具体方法:

1. 入队(新数组在旧数组的基础上加元素然后替换旧数组)
2. 出队(需要取出第一个并且返回 其余的错位传给新数据 用新数组替换旧数组即可)
3. 判空(判断数组长度是否为空)

实现方法

public class MyQueue {
    //底层用数组来存储数据
        int[] elements;

        public MyQueue(){
        elements=new int[0];
        }

    //入队(和栈一样的代码思路)
        public void add(int element){
            //创建一个新的数组
            int[] newArr =new int[elements.length+1];
            //原始数组中的元素赋值到新的数组
            for(int i=0;i<elements.length;i++){
                newArr[i]=elements[i];
            }
            //将添加的元素加入到新数据
            newArr[elements.length]=element;  //放到最后!!!
            //新数组替换旧数组
            elements=newArr;
        }

    //出队(需要取出第一个并且返回 其余的错位传给新数据 用新数组替换旧数组即可)
        public int poll(){
          //取出来第一个元素
            int element=elements[0];

          //新建数组
            int[] newArr=new int[elements.length-1];
          //旧数组除了第一个数存到新的数组
            for(int i=0;i<newArr.length;i++){
                newArr[i]=elements[i+1];  //从第二个开始错位传给新的参数
            }
          //替换数组
            elements=newArr;
          //返回队列第一个元素
            return element;
        }

    //判断栈是否为空(只需要返回布尔值是不是为空)
         public boolean isEmpty(){
             return elements.length==0;
         }

}

测试Test类

public class Test {
    public static void main(String[] args){
        //创建一个队列
            MyQueue m=new MyQueue();
            m.add(9);
            m.add(8);
            m.add(7);  // 从前往后: 9 8 7

        System.out.println(m.poll());  //第一个为9
        System.out.println(m.poll());  //第二个为8   因为9已经被踢出去了
    }
}

具体结果:

数组模拟队列

思路

1. 阿斯达请问
2. 阿斯达阿斯达

代码实现

类

1
2

2020-04-11

栈

栈(先进后出)

栈相当于手枪弹夹(不停地往下压子弹)

具体实现

具体方法

1. 压入元素(新数组在旧数组基础上加上压入的元素之后替换旧数组)
2. 取出栈顶(取出并返回栈顶 然后新数组将其他元素放入后替换旧数组)
3. 查看栈顶(只需要返回数组最后一个)
4. 判空(返回数组长度是否为空)

底层方法

public class Main {
    //底层用数组来存储数据
        int[] elements;

        public Main(){
            elements=new int[0];
        }

      //压入元素(新数组在旧数组基础上加上压入的元素之后替换旧数组)
        public void push(int element){
            //创建一个新的数组
                int[] newArr =new int[elements.length+1];
            //原始数组中的元素赋值到新的数组
                for(int i=0;i<elements.length;i++){
                    newArr[i]=elements[i];
                }
            //将添加的元素加入到新数据
                newArr[elements.length]=element;  //放到最后!!!
            //新数组替换旧数组
                elements=newArr;
        }

      //取出栈顶元素(取出并返回栈顶 然后新数组将其他元素放入后替换旧数组)
        public int pop(){
            if(elements.length==0){
                System.out.println("有异常");
            }
           //取出数组最后一个数(栈顶)
                int top= elements[elements.length-1];
           //新建数组存放其他数据
                int[] newArr=new int[elements.length-1];
            //旧数组除了最后一个存到新的数组
                for(int i=0;i<elements.length-1;i++){
                     newArr[i]=elements[i];
                }
            //替换数组
                elements=newArr;

            return top;  //返回栈顶
        }

        //查看栈顶元素(只需要返回数组最后一个)
          public int look(){
            return elements[elements.length-1];  //只是查看栈顶
        }

        //判断栈是否为空(只需要返回是不是为空)
          public boolean isEmpty(){
            return elements.length==0;
        }

}

测试Test类

public class Test {
    public static void main(String[] args){
      //创建一个栈
        Main m=new Main();
      //压入数组
        m.push(9);
        m.push(8);
        m.push(7);  // 从上到下: 7 8 9
      //取数
        System.out.println(m.pop());  // 7 因为目前最后压进去的是7
        System.out.println(m.pop());  // 8  7已经弹出去了
        System.out.println(m.look());  // 9 7.8都弹出去了
    }
}

最终执行测试：