数据结构与算法——Java版

朴灿烈づ我的快乐病毒、 2022-08-28 07:42 127阅读 0赞

### 文章目录 ###

*  数据结构
 *   *  概述
     *  常见的数据结构
     *  数据结构分类
     *   *  存储结构
         *  逻辑结构
     *  数组
     *  线性表
     *   *  线性表的存储结构
         *  单链表
         *  循环链表
         *  双链表
     *  栈和队列
     *   *  栈
         *  队列
         *  递归
     *  算法
     *   *  常用算法
         *  时间复杂度(Time Complexity)
         *   *  最坏时间复杂度和平均时间复杂度：
             *  时间复杂度计算
         *  空间复杂度（Space Complexity）
     *  排序
     *   *  交换排序
         *   *  冒泡排序
             *  快速排序
         *  插入排序
         *   *  直接插入排序
             *  希尔排序
         *  选择排序
         *   *  直接选择排序
             *  堆排序
         *  归并排序
         *  基数排序
     *  树
     *   *  树的术语
         *  二叉树
         *   *  二叉树的性质
             *  二叉树的遍历
             *  顺序存储的二叉树
         *  线索二叉树
         *  赫夫曼树
         *   *  构建赫夫曼树
             *  赫夫曼编码
             *  压缩文件
             *  解压文件
         *  二叉排序树
         *  AVL树
         *  多路查找树
     *  哈希表
     *   *  散列函数的设计
         *  散列冲突的解决方案
     *  图

# 数据结构 #

## 概述 ##

数据结构（英语：data structure）是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。

1.  数据：
    
     *  数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合的统称。
2.  数据项：
    
     *  时数据元素中独立含义的、不可分割的最小标识单位。
     *  如描述学生相关信息的姓名、性别、学号等都是数据项
3.  数据元素：
    
     *  表示一个事物的一组数据。
     *  如一条描述一位学生的完整信息的数据记录就是一个数据元素；
4.  数据对象：
    
     *  数据对象是性质相同的数据元素的集合，是数据的子集。
     *  如一个学校的所有学生的集合就是数据对象，空间中所有点的结合也是数据对象。
5.  关键字：
    
     *  一个数据元素中，能够识别该元素的一个或多个数据项
6.  主关键字：
    
     *  能够唯一识别数据元素的关键字
7.  结点：
    
     *  存储一个数据元素的存储单元称为结点，一个结点至少包括：数据域存储数据元素；地址域(也称链)存储前驱或后继元素地址

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

## 常见的数据结构 ##

*  **栈（Stack）**: 栈是一种特殊的线代表，它只能在一个表的一个固定端进行数据节点的插入和删除操作。
 *  **队列（Queue）**：队列和栈类似，也是一种特殊的线代表。和栈不同的是，队列只允许在表的一段进行插入操作，而在另一端进行删除操作。
 *  **数组（Array）**： 数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
 *  **链表（Linked List）**：链表是一种数据元素按照链式存储结构的数据结构，这种存储结构具有物理上存在非连续的特点。
 *  **树（Tree）**：树是典型的非线性结构，它是包括，2个结点的有穷集合K。
 *  **图（Graph）**：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
 *  **堆（Heap）**：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
 *  **散列表（Hash Table）**： 散列表源自散列函数（Hash function），其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行操作而直接取得所查记录。

## 数据结构分类 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70]

数据的存储结构：

数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示，是数据的逻辑结构在计算机中的表示。

### 存储结构 ###

**顺序存储结构**：

把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，节点之间的逻辑关系由存储单元的邻接关系来体现。

![在这里插入图片描述][20210713113823436.png]

*  优点：是节省存储空间，因为分配给数据的存储单元全用存放节点的数据，节点之间的逻辑关系没有占用额外的存储空间。
 *  缺点： 插入和删除操作需要移动元素，效率低

**链式存储结构**：

数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。

![在这里插入图片描述][20210713113936576.png]

每个结点室友数据域和指针域组成。元素之间的逻辑关系通过存储结点之间的链接关系反映出来。

*  特点：
    
    1.  比顺序存储结构的存储密度小
    2.  逻辑上相邻的结点物理上不比相邻
    3.  插入、删除灵活(不必移动节点，只要改变节点中的指针)
    4.  查找节点时链式存储要比顺序存储慢

**索引存储结构**： 除建立存储节点信息外，还建立附加的索引表示来标识节点的地址。比如：图书、字典的目录。

**散列存储结构**：根据节点的关键字直接计算出该节点的存储地址

### 逻辑结构 ###

## 数组 ##

数组的基本使用

public class TestArray {
        
    
    	public static void main(String[] args) {
        
    		//创建一个数据
    		int[] arr1 = new int[3];
    		//获取数组长度
    		int length1 = arr1.length;
    		System.out.println("arr1's length：" + length1);
    		//访问数组中的元素：数组名【下标】   注意：下标从0开始，最大可以取到长度-1
    		int element0 = arr1[0];
    		System.out.println("element0:" + element0);
    		// 为数组中的元素赋值
    		arr1[0] = 99;
    		System.out.println("element0:" + arr1[0]);
    		arr1[1]  = 99;
    		arr1[2] = 97;
    		// 遍历数组
    		for (int i = 0; i < length1; i++) {
        
    			System.out.println("arr1 element" + i + ":" + arr1[i]);
    		}
    		//创建数组的同时为数组中的元素赋值
    		int[] arr2 = new int[] {
        90,80,70,60,50};
    		//获取数组的长度
    		System.out.println("arr2 length:"+ arr2.length);
    	}
    }

数组元素的添加

public class TestOpArray {
        
    
    	public static void main(String[] args) {
        
    		// 解决数组的长度不可变的问题
    		int[] arr = new int[]{
        9,8,7};
    		//快速查看数组中的元素
    		System.out.println(Arrays.toString(arr));
    		//要加入数组的目标元素
    		int dst = 6;
    		
    		//创建一个新的数组，长度是原数组长度+1
    		int[] newArr = new int[arr.length+1];
    		//把数组中的数据全部复制到新数组中
    		for (int i = 0; i < arr.length; i++) {
        
    			newArr[i] = arr[i];
    		}
    		
    		//把目标元素放入新数组的最后
    		newArr[arr.length] = dst;
    		//新数组替换原数组
    		arr = newArr;
    		System.out.println(Arrays.toString(arr));
    	}
    }

数组元素的删除

public class TestOpArray2 {
        
    	public static void main(String[] args) {
        
    		int[] arr = new int[] {
        9,8,7,6,5,4};
    		int dst = 0;
    		System.out.println(Arrays.toString(arr));
    		
    		int[] newArr = new int[arr.length - 1];
    		for (int i = 0; i < newArr.length; i++) {
        
    			if (i<dst) {
        
    				newArr[i] = arr[i];
    			}else {
        
    				newArr[i] = arr[i+1];
    			}
    		}
    		
    		arr = newArr;
    		System.out.println(Arrays.toString(arr));	
    	}
    }

面向对象的数组

public class Myarray {
        
    
    	private int[] elements;
    	
    	public Myarray() {
        
    		elements = new int[0];
    	}
    	
    	//获取数组长度的方法
    	public int size() {
        
    		return elements.length;
    	}
    	
    	//往数组的末尾添加一个元素
    	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 void show() {
        
    		System.out.println(Arrays.toString(elements));
    	}
    	
    	
    	//删除数组中的元素
    	public void delete(int index) {
        
    		//判断下标是否越界
    		if (index<0 || index>elements.length-1) {
        
    			throw new RuntimeException("下标越界");
    		}
    		//创建一个新的数组，长度为原数组的长度-1
    		int[] newArr = new int[elements.length-1];
    		for (int i = 0; i < newArr.length; i++) {
        
    			//想要删除的元素前面的元素
    			if (i<index) {
        
    				newArr[i] = elements[i];
    			}else {
        
    				newArr[i] = elements[i+1];
    			}
    		}
    		elements = newArr;
    	}
    	
    	//获取某个元素
    	public int get(int index) {
        
    		return elements[index];
    	}
    	
    	//插入一个元素到指定位置
    	public void insert(int index, int element) {
        
    		//判断下标是否越界
    		if (index<0 || index>elements.length-1) {
        
    			throw new RuntimeException("下标越界");
    		}
    		//创建一个新的数组
    		int[] newArr = new int[elements.length+1];
    		//将原数组中的元素放入新数组中
    		for (int i = 0; i < elements.length; i++) {
        
    			//目标位置之前的元素
    			if (i<index) {
        
    				newArr[i] = elements[i];
    			//目标元素之后的位置
    			}else {
        
    				newArr[i+1] = elements[i];
    			}
    		}
    		//插入新的元素
    		newArr[index] = element;
    		//新数组替换旧数组
    		elements = newArr;
    	}
    	
    	//替换指定位置的元素
    	public void set(int index, int element) {
        
    		//判断下标是否越界
    		if (index<0 || index>elements.length-1) {
        
    			throw new RuntimeException("下标越界");
    		}
    		elements[index] = element;
    	}
        //二分法查找
    	public int binarySearch(int target) {
        
    
    		//记录开始位置
    		int begin = 0;
    		//记录结束位置
    		int end = elements.length-1;
    		//记录中间的位置
    		int mid = (begin+end)/2;
    		//记录目标位置
    		int index=-1;
    		//循环查找
    		while(true) {
        
    			//什么情况下没有这个元素？
    			//如果开始在结束位置之后或重合
    			if (begin>=end) {
        
    				return -1;
    			}
    			
    			//判断中间的这个元素是不是要查找的元素
    			if(elements[mid]==target) {
        
    				return mid;
    			//中间这个元素不是要查的元素
    			}else {
        
    				//判断中间这个元素是不是比目标元素大
    				if(elements[mid]>target) {
        
    					//把结束位置调整到中间位置前一个位置
    					end=mid-1;
    				//中间这个元素比目标元素小
    				}else {
        
    					//把开始位置调整到中间位置的后一个位置
    					begin = mid+1;
    				}
    				//取出新的中间位置
    				mid=(begin+end)/2;
    			}
    		}
    	}
    }

## 线性表 ##

线性表是n个类型相同数据元素组成的有限序列，通常记作(a0，a1，a2…，an-1)

1.  相同数据类型
    
     *  可以看到从a0到an-1的n个数据元素是具有相同属性的元素
     *  相同数据类型意味着在内存中存储时，每个元素会占用相同的内存空间，便于后续的查询定位
2.  序列（顺序性）
    
     *  在线性表的相邻数据元素之间存在着序偶关系
     *  即ai-1是ai的直接前驱，a i是a i-1的直接后续
     *  除了表头和表尾元素外，任何一个元素都有切仅有一个直接前驱和直接后续。
3.  有限
    
     *  线性表中数据元素的个数n定义为线性表的长度，即n是一个有限值。

### 线性表的存储结构 ###

1.  顺序表——顺序存储结构
    
     *  数组：存储具有相同数据类型的元素集合。
     *  顺序表： 线性表的顺序存储结构称为顺序表。
     *  优点：
        
        1.  节省存储空间，因为分配给数据的存储单元全用存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。
        2.  索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
     *  缺点：
        
        1.  插入和删除操作需要移动元素，效率较低。
        2.  必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。
        3.  按照内容查询效率低，因为需要逐个比较判断
2.  线性链表——链式存储结构
    
     *  数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。
     *  每个结点只有一个地址域的线性链表称为单链表
        
         *  链表的第一个及结点和最后一个结点，分别称为链表的首节点和尾结点
         *  单链表的一个重要特性就是只能通过前驱结点找到后续结点，而无法从后续结点找到前驱结点 。
            
             *  在单链表进行查找操作，只能从链表的首节点开始，通过每个结点的next引用来一次访问链表中的每个结点以完成相应的查找操作
         *  单链表中结点的存储空间是在插入和删除过程中动态申请和释放的，不需要预先给单链表分配存储空间，从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程，提高了运行效率和存储空间的利用率。
         *  为了使程序更加简洁，通常在单链表的最前面添加一个哑元结点，也称为头结点（head）。
            
             *  在头结点中不存储任何实质的数据对象，其next域指向线性表中0号元素所在的结点， 可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便
             *  空单链表的头指针head为null，一条单链表最后一个结点的地址域为null，表示其后不再有结点。

### 单链表 ###

单链表的实现

//一个节点
    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;
                //如果下一个节点为null，当前节点已经是最后一个节点
                if(nextNode==null) {
        
                    break;
                }
                //赋给当前节点
                currentNode = nextNode;
            }
            //把需要追回的节点追加为找到的当前节点的下一个节点
            currentNode.next=node;
            return this;
        }
    
        //插入一个节点作为当前节点的下一个节点
        public void after(Node node) {
        
            //取出下一个节点，作为下下一个节点
            Node nextNext = next;
            //把新节点作为当前节点的下一个节点
            this.next=node;
            //把下下一个节点设置为新节点的下一个节点
            node.next=nextNext;
        }
    
        //显示所有节点信息
        public void show() {
        
            Node currentNode = this;
            while(true) {
        
                System.out.print(currentNode.data+" ");
                //取出下一个节点
                currentNode=currentNode.next;
                //如果是最后一个节点
                if(currentNode==null) {
        
                    break;
                }
            }
            System.out.println();
        }
    
        //删除下一个节点
        public void removeNext() {
        
            //取出下下一个节点
            Node newNext = next.next;
            //把下下一个节点设置为当前节点的下一个节点
            this.next=newNext;
        }
    
        // 获取下一个节点
        public Node next() {
        
            return this.next;
        }
    
        //获取节点中的数据
        public int getData() {
        
            return this.data;
        }
    
        //当前节点是否为最后一个节点
        public boolean isLast() {
        
            return next==null;
        }
    
    }

### 循环链表 ###

//循环链表
    public class LoopNode {
        
    
    	//节点内容
    	int data;
    	//下一个节点
    	LoopNode next=this;
    	
    	public LoopNode(int data) {
        
    		this.data=data;
    	}
    	
    	//插入一个节点作为当前节点的下一个节点
    	public void after(LoopNode node) {
        
    		//取出下一个节点，作为下下一个节点
    		LoopNode nextNext = next;
    		//把新节点作为当前节点的下一个节点
    		this.next=node;
    		//把下下一个节点设置为新节点的下一个节点
    		node.next=nextNext;
    	}
    	
    	//删除下一个节点
    	public void removeNext() {
        
    		//取出下下一个节点
    		LoopNode newNext = next.next;
    		//把下下一个节点设置为当前节点的下一个节点
    		this.next=newNext;
    	}
    	
    	//获取下一个节点
    	public LoopNode next() {
        
    		return this.next;
    	}
    	
    	//获取节点中的数据
    	public int getData() {
        
    		return this.data;
    	}
    	
    }

### 双链表 ###

//循环双向链表实现
    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;
    	}
    	
    }

## 栈和队列 ##

### 栈 ###

*  栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。（**先进后出**）
 *  允许操作的一端称为栈顶（Top），不允许操作的一端称为栈底（Bottom）。
 *  栈中插入元素的操作称为入栈（push），删除元素的操作称为（Pop）。
 *  没有元素的栈称为空栈。
 *  采用顺序栈存储结构的栈称为顺序栈（Sequential Stack）。
 *  采用链式结构存储的栈称为链式栈（Linked Stack）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70 1]

声明栈接口Stack

//声明栈接口Stack<T>
    public interface Stack<T>{
        
        public abstract boolean isEmpty();    //判断栈是否为空
        public abstract void push(T x);      //元素x入栈
        public abstract T peek();    //返回栈顶元素，未出栈
        public abstract T pop();0   //出栈，返回栈顶元素
    }

顺序栈

public final class SeqStack<t> implements Stack<T>{
            private SeqList<T> list;        public SeqStack(int length){
            //构造容量为length的空栈        this.list = new SeqList<T>(length);  //执行顺序表的构造方法    }        public SeqStack(){        this(64);    }        public boolean isEmpty(){        return this.list.isEmpty();    }        public void push(T x){ //元素x入栈，空对象不能入栈        this.list.insert(x); //顺序表尾插入元素x，自动扩充容量    }        public T peek(){ //返回栈顶元素（未出栈），若栈空返回 null        return this.list.get(list.size() -1);         }        public T pop(){ //出栈，返回栈顶元素；若栈空返回 null        return list.remove(list.size() -1); //若栈不空， 顺序表尾删除，返回删除元素    }}

链式栈

public final class LinkedStack<T> implements Stack<T>{
            private SingleList<T> list;        public LinkedStack(){
                this.list = new SingleList<T>();    }        public boolean isEmpty(){
                return this.list.isEmpty();    }        public void push(T x)(){
                this.list.add(0, x);    }        public T peek(){
                return this.list.get(0);    }        public T pop(){
                return this.list.remove(0);    }}

将十进制转换成二进制

public static void main(String[] args) {
        		//给定一个十进制数		int n=13;		//定义一个空栈		Deque stack = new LinkedList();		//把十进制数转换成二进制数		int t = n;   //被除数		while(t>0) {			int mod = t% 2;			stack.push(mod);			t = t/2;		}		//输出结果		System.out.print(n+"---->" );		while(!stack.isEmpty()) {			System.out.print(stack.pop());		}	}

### 队列 ###

*  队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。
 *  向队列中插入元素的过程称为入队（Enqueue），删除元素的过程称为出队（Dequeue）。
 *  允许入队的一段称为队尾（Rear），允许出队的一段称为队头（Front）。
 *  没有元素的队列称为空队列。
 *  插入和删除操作分别在队尾和队头进行，最先入队的元素总是先出队，因此队列的特点：**先进先出**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70 2]

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;	}}

顺序队列

链式队列

优先队列

### 递归 ###

在一个方法（函数）的内部调用该方法（函数）本身的编程方式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70 3]

斐波那契数列

public class TestFebonacci {
        	public static void main(String[] args) {
        		//斐波那契数列 0 1 1 2 3 5 8 13		int i = febonacci(7);		System.out.println(i);	}		//返回Fibonacci数列的第n项	public static int febonacci(int n) {		if (n<0) {			throw new IllegalArgumentException("无效参数");		}		if(n==0 || n==1) {			return n;		}else {			return febonacci(n-2)+febonacci(n-1);		}	}}

汉诺塔问题

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16]

public class TestHanoi {
        	public static void main(String[] args) {
        		hanoi(7,'A','B','C');	}		/**	 * @param n 	共有N个盘子	 * @param from	开始的柱子	 * @param in		中间的柱子	 * @param to		目标柱子	 * 无论多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子。	 */	public static void hanoi(int n,char from,char in,char to) {
        		//只有一个盘子		if(n==1) {			System.out.println("第1个盘子"+from+"移到"+to);		//无论多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子。		}else {			//移动上面所有的盘子到中间位置			hanoi(n-1,from,to,in);			//移动下面的盘子			System.out.println("第"+n+"个盘子从"+from+"移到"+to);			//把上面的所有盘子从中间位置移到目标位置			hanoi(n-1,in,from,to);		}	}}

## 算法 ##

是指令的集合，是为解决特定问题而规定的一系列操作。  
它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据结合作为输出。

特点：

1.  输入：一个算法应以待解决的问题的信息作为输入。
2.  输出：输入对应指令集处理后得到的信息。
3.  可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。
4.  有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成，因此整个算法也是在有限时间内可以结束的。
5.  确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。

算法的基本要求：

*  正确性
 *  可读性
 *  健壮性
 *  时间复杂度
 *  空间复杂度

### 常用算法 ###

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。

*  **检索**： 检索就是在数据结构李查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值得节点。
 *  **插入**： 往数据结构中增加新的节点。
 *  **删除**： 把指定的结点从数据结构中去掉。
 *  **更新**： 改变指定节点的一个或多个字段的值。
 *  **排序**： 把节点按某种指定的顺序重新排列。例如递增或递减。

如何衡量一个算法的优劣？

### 时间复杂度(Time Complexity) ###

指算法的执行时间随问题规模的增长而增长的趋势

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

#### 最坏时间复杂度和平均时间复杂度： ####

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。  
在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例，该算法的运行时间不可能大于O(n)。

**平均时间复杂度**是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

1.  难计算
2.  有很多算法的平均情况和最差情况的复杂度是一样的

所以一般讨论最坏时间复杂度

为了经一部说明算法的时间复杂度，定义了O、Ω、Θ符号

*  最坏时间复杂度，T(n) = O(n^2)
 *  最好时间复杂度，T(n) = Ω(n^2)
 *  平均时间复杂度，T(n) = Θ(n^2)

#### 时间复杂度计算 ####

根本没有必要计算时间频度，即使计算处理还要忽略常量、低次幂和最高次幂的系数，所以可以采用如下简单方法；

1.  找出算法中的基本语句
    
     *  算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
2.  计算基本语句的执行次数的数量级
    
     *  只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，
     *  可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
3.  用大O符号表示算法的时间性能
    
     *  将基本语句执行次数的数量级放入大O符号中。

常见的时间复杂度级别

*  常数阶O(1)
 *  对数阶O(log₂n)
 *  线性阶O(n)
 *  线性对数阶O(n\*log₂n)
 *  平方价O(n²)

### 空间复杂度（Space Complexity） ###

算法的存储量包括：

1.  程序本身所占空间
2.  输入数据所占空间
3.  辅助变量所占空间

输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：  
S(n) = O(g(n))

int fun(int n){
          //n为问题规模    int i, j, k, s;    s = 0;    for(i=0; i<=n; i++){        for(j=0; j<=i; j++){            for(k=0; k<=j; k++){            s++;            }        }    }    return(s);}

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为:  
S(n) = O(1)

## 排序 ##

**排序**是指将数据元素按照指定关键字值的大小递增（或递减）次序重新排列。

八种常用排序算法：

*  交换排序
    
     *  冒泡排序
     *  快速排序
 *  插入排序
    
     *  直接插入排序
     *  希尔排序
 *  选择排序
    
     *  直接选择排序
     *  堆排序+
 *  归并排序

### 交换排序 ###

#### 冒泡排序 ####

比较相邻两个元素大小，如果反序，则交换。若按升序排序，每趟将数据序列中的最大元素交换到最后位置，就像气泡从水里冒出一样。

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));		bubbleSort(arr);		System.out.println(Arrays.toString(arr));	}		//冒泡排序	/**	 * 5,7,2,9,4,1,0,5,7		共需要比较length-1轮	 * 5,7,2,9,4,1,0,5,7		 * 5,2,7,9,4,1,0,5,7	 * 5,2,7,4,1,0,5,7,9	 * 2,5   	 */	public static void bubbleSort(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，则完成排序。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

public class QuickSort {
        	public static void main(String[] args) {
        		int[] arr = new int[] {
        3,4,6,7,2,7,2,8,0,9,1};		quickSort(arr,0,arr.length-1);		System.out.println(Arrays.toString(arr));	}		public static void quickSort(int[] arr,int start,int end) {
        		if(start<end && start>=0 && end>=0 && start<arr.length && end<arr.length) {
        			//把数组中的第0个数字作为标准数			int stard=arr[start];			//记录需要排序的下标			int low=start;			int high=end;			//循环找比标准数大的数和比标准数小的数			while(low<high) {				//右边的数字比标准数大				while(low<high && stard<=arr[high]) {					high--;				}				//使用右边的数替换左边的数				arr[low]=arr[high];				//如果左边的数字比标准数小				while(low<high && arr[low]<=stard) {					low++;				}				arr[high]=arr[low];			}			//把标准数赋给低所在的位置的元素			arr[low]=stard;			//处理所有的小的数字			quickSort(arr, start, low);			//处理所有的大的数字			quickSort(arr, low+1, end);		}	}}

### 插入排序 ###

每趟将一个元素，按其关键字值的大小插入到它前面已排序的子序列中，依次重复，直到插入全部元素。

#### 直接插入排序 ####

![img][]

public class InsertSort {
        		public static void main(String[] args) {
        		int[] arr = new int[] {
        5,7,2,8,5,9,1,0};		insertSort(arr);		System.out.println(Arrays.toString(arr));	}		//插入排序	public static void insertSort(int[] arr) {		//遍历所有数字		for(int i=1;i<arr.length;i++) {			//如果当前数字比前一个数字小//			if(arr[i]<arr[i-1]) {				//把当前遍历数字存起来				int temp=arr[i];				int j;				//遍历当前数字前面所有的数字				for(j=i-1;j>=0&&temp<arr[j];j--) {					//把前一个数字赋给后一个数字					arr[j+1]=arr[j];				}				//把临时变量赋给不满足条件的后一个元素				arr[j+1]=temp;//			}		}	}}

#### 希尔排序 ####

又称缩小增量排序

将一个数据序列分成若干组，每组由若干相隔一段距离（称为增量）的元素组成，在一个组内采用直接插入排序算法进行排序。增量初值通常为数据序列长度的一半，以后每趟增量减半，最后值为1.随着增量逐渐减少，组数也减少，组内元素个数增加，数据序列接近有序。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

public class ShellSort {
        
    	public static void main(String[] args) {
        
    		int[] arr = new int[] {
         3, 5, 2, 7, 8, 1, 2, 0, 4, 7, 4, 3, 8 };
    		System.out.println(Arrays.toString(arr));
    		shellSort(arr);
    		System.out.println(Arrays.toString(arr));
    	}
    	
    	public static void shellSort(int[] arr) {
        
    		int k = 1;
    		// 遍历所有的步长
    		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) {
        
    					// 如果当前元素大于加上步长后的那个元素
    					if (arr[j] > arr[j + d]) {
        
    						int temp = arr[j];
    						arr[j] = arr[j + d];
    						arr[j + d] = temp;
    					}
    				}
    			}
    			System.out.println("第" + k + "次排序结果" + Arrays.toString(arr));
    			k++;
    		}
    	}
    }

### 选择排序 ###

#### 直接选择排序 ####

第一趟从n个元素的数据序列中选出关键字最小/大的元素并放到最前/后位置，下一趟再从n-1个元素中选出最小/大的元素并放到次前/后位置，以此类推，经过n-1趟完成排序。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

// 直接选择排序public class SelectSort {	public static void main(String[] args) {		int[] arr = new int[] {3,4,5,7,1,2,0,3,6,8};		selectSort(arr);		System.out.println(Arrays.toString(arr));	}		//选择排序	public static void selectSort(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;				}			}			//如果最小的数和当前遍历数的下标不一致，说明下标为minIndex的数比当前遍历的数更小			if(i!=minIndex) {				int temp=arr[i];				arr[i]=arr[minIndex];				arr[minIndex]=temp;			}		}	}}

#### 堆排序 ####

https://www.cnblogs.com/chengxiao/p/6129630.html

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 4]

> **堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了**

// 堆排序public class HeapSort {   public static void main(String[] args) {      int[] arr = new int[]{9, 6, 8, 7, 0, 1, 10, 4, 2};      heapSort(arr);      System.out.println(Arrays.toString(arr));   }   public static void heapSort(int[] arr) {      // 开始位置是最后一个非叶子节点，即最后一个节点的父节点      int start = (arr.length - 1) / 2;      // 调整为大顶堆      for (int i = start; i >= 0; i--) {         maxHeap(arr, arr.length, i);      }      // 先把数组中的第0个和堆中的最后一个数交换位置，再把前面的处理为大顶堆      for (int i = arr.length - 1; i > 0; i--) {         int temp = arr[0];         arr[0] = arr[i];         arr[i] = temp;         maxHeap(arr, i, 0);      }   }   public static void maxHeap(int[] arr, int size, int index) {      //左子节点      int leftNode = 2 * index + 1;      //右子节点      int rightNode = 2 * index + 2;      int max = index;      // 和两个子节点分别对比，找出最大的节点      if (leftNode < size && arr[leftNode] > arr[max]) {         max = leftNode;      }      if (rightNode < size && arr[rightNode] > arr[max]) {         max = rightNode;      }      // 交换位置      if (max != index) {         int temp = arr[index];         arr[index] = arr[max];         arr[max] = temp;         // 交换位置以后，可能会破坏之前排好的堆，所以，之前的排好的堆需要重新调整         maxHeap(arr, size, max);      }   }}

### 归并排序 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

public class MergeSort {
        	public static void main(String[] args) {
        		int[] arr = new int[] {
        1,3,5,4,2,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++;			}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];		}	}}

### 基数排序 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

// 基数排序public class RadixSort {	public static void main(String[] args) {		int[] arr = new int[] {23,6,189,45,9,287,56,1,798,34,65,652,5};		radixSort(arr);		System.out.println(Arrays.toString(arr));	}		public static void  radixSort(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];		// 用于记录在temp中相应的数组中存放的数字的数量		int[] counts = new int[10];		// 根据最大长度的数决定比较的次数		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]++;			}			// 记录取的元素需要放的位置			int index=0;			// 把数字取出来			for(int k=0;k<counts.length;k++) {				// 记录数量的数组中当前余数记录的数量不为0				if(counts[k]!=0) {					// 循环取出元素					for(int l=0;l<counts[k];l++) {						// 取出元素						arr[index] = temp[k][l];						// 记录下一个位置						index++;					}					// 把数量置为0					counts[k]=0;				}			}		}	}}

基数排序之队列实现

public class RadixQueueSort {
            public static void main(String[] args) {
                int[] arr = new int[] {
        23,6,189,45,9,287,56,1,798,34,65,652,5};        radixSort(arr);        System.out.println(Arrays.toString(arr));    }    public static void  radixSort(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();                    // 记录下一个位置                    index++;                }            }        }    }}

## 树 ##

![在这里插入图片描述][5ac23a6d191c48f1a55f8ec565a25cdb.png]

树（Tree）是由n（n>=0)个结点组成的有限集合（树中元素通常称为结点）。n=0的树称为空树；n>0的树T由以下两个条件约定构成：

1.  有个特殊的结点称为根结点，它只有后继结点，没有前驱结点。
2.  除根结点之外的其他结点分为m（0≤m <n）个互不相交的集合T0、T1、…、Tm-1，其中每个集合Ti（0≤ i<m）也具有树结构，称为根的**子树**(Subtree).

### 树的术语 ###

1.  父母、孩子和兄弟结点
    
     *  一棵树中，一个结点的子树的根结点称为**孩子**结点； 相对地，该结点是其孩子结点的**父母**结点。
     *  拥有同一个父母结点的多个结点之间称为**兄弟**(Sibling)结点。
     *  结点的**祖先**(Ancestor)是指其父母结点，以及父母的父母结点等，直至根节。 结点的**后代**(Descendant，也称子代)是指其所有孩子结点，以及孩子的孩子结点等。
2.  度
    
     *  结点的**度**(Degree)是结点所拥有子树的棵树。
     *  度为0的结点称为**叶子**(Leaf)结点,又称为终端结点；树中除叶子结点之外的其他结 点称为分支结点，又称为非叶结点或非终端结点。
     *  树的**度**是指树中各结点度的最大值。
3.  结点层次、树的高度
    
     *  结点的**层次**(Level)属性反映结点处于树中的层次位置。
     *  树的**高度**(Height)或**深度**(Depth)是树中结点的最大层次数。
4.  边、路径、直径
    
     *  设树中X结点是Y结点的父母结点，有序对(X,Y)称为连接这两个结点的分支，也称为**边**(Edge).
     *  设（X0,X1,…,Xk）(0≤k<n)是由树中结点组成的一个序列，且（Xi，Xi+1）都是树中的边，则称为序列为X0到Xk的一条**路径**(Path). **路径长度**(Path Length)为路径上的边数。
     *  二叉树的**直径**(Diameter)指从根到叶子结点一条最长路径，直径的路径长度是该二叉树的高度-1.
5.  无序树、有序树  
    在数的定义中，结点的子树 之间没有次序，可以叫唤位置，称为无序树，简称数。如果结点的子树从左至右是有次序的，不能交换位置，则称该数为有序树。
6.  森林
    
    森林是m（m>=0）棵互不相交的树的集合。给森林加上一个根节点就变成一棵树，将树的根节点删除就变成森林。

### 二叉树 ###

Binary Tree

二叉树是n（n≥0）个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。

![在这里插入图片描述][6eaad7d2e2124fd6bad83ace62093fa0.png]

#### 二叉树的性质 ####

**性质1**：二叉树第i层上的结点数目最多为 **2****\{i-1\}** (i≥1)。  
**性质2**：高度为k的二叉树至多有**2\{k\}\-1**个结点(k≥1)。  
**性质3**：在任意一棵二叉树中，若终端结点的个数为**n0**，度为2的结点数为**n2**，则**n0=n2\+1**。  
**性质4**：包含n个结点的二叉树的高度至少为**log2 (n+1)**。

满二叉树：所有叶子结点都在最后一层，而且节点的总数为：2^n - 1

![在这里插入图片描述][fb74391074874d5ea4fd84d99a015b3e.png]

完全二叉树：所有叶子结点都在最后一层或倒数第二层，且最后一层的叶子结点在左边连续，倒数第二节的叶子节点在右边连续

![在这里插入图片描述][bdaabcb7a94e4c8fb28edd7f9222b940.png]

#### 二叉树的遍历 ####

先根次序：访问根结点，遍历左子树，遍历右子树。

中根次序：遍历左子树，访问根结点，遍历右子树。

后根次序：遍历左子树，遍历右子树，访问根结点。

// 二叉树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();      }   }   public void midShow() {      if(root!=null) {         root.midShow();      }   }   public void afterShow() {      if(root!=null) {         root.afterShow();      }   }   public TreeNode frontSearch(int i) {      return root.frontSearch(i);   }   public void delete(int i) {      if(root.value==i) {         root=null;      }else {         root.delete(i);      }   }}

// 树节点public class TreeNode {   // 节点的权   int value;   // 左儿子   TreeNode leftNode;   // 右儿子   TreeNode rightNode;   public TreeNode(int value) {      this.value=value;   }   //设置左儿子   public void setLeftNode(TreeNode leftNode) {      this.leftNode = leftNode;   }   //设置右儿子   public void setRightNode(TreeNode rightNode) {      this.rightNode = rightNode;   }   //前序遍历   public void frontShow() {      //先遍历当前节点的内容      System.out.println(value);      //左节点      if(leftNode !=null) {         leftNode.frontShow();      }      //右节点      if(rightNode !=null) {         rightNode.frontShow();      }   }   // 中序遍历   public void midShow() {      // 左子节点      if(leftNode !=null) {         leftNode.midShow();      }      // 当前节点      System.out.println(value);      // 右子节点      if(rightNode !=null) {         rightNode.midShow();      }   }   // 后序遍历   public void afterShow() {      // 左子节点      if(leftNode !=null) {         leftNode.afterShow();      }      // 右子节点      if(rightNode !=null) {         rightNode.afterShow();      }      // 当前节点      System.out.println(value);   }   // 前序查找   public TreeNode frontSearch(int i) {      TreeNode target = null;      // 对比当前节点的值      if(this.value==i) {         return this;      // 当前节点的值不是要查找的节点      }else {         // 查找左儿子         if(leftNode !=null) {            // 有可能可以查到，也可以查不到，查不到的话，target还是一个null            target = leftNode.frontSearch(i);         }         // 如果不为空，说明在左儿子中已经找到         if(target!=null) {            return target;         }         // 查找右儿子         if(rightNode !=null) {            target= rightNode.frontSearch(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);      }   }}

测试

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);        // 把新创建的节点设置为根节点的子节点        root.setLeftNode(rootL);        // 创建一个右节点        TreeNode rootR = new TreeNode(3);        // 把新创建的节点设置为根节点的子节点        root.setRightNode(rootR);        // 为第二层的左节点创建两个子节点        rootL.setLeftNode(new TreeNode(4));        rootL.setRightNode(new TreeNode(5));        // 为第二层的右节点创建两个子节点        rootR.setLeftNode(new TreeNode(6));        rootR.setRightNode(new TreeNode(7));        //前序遍历树        binTree.frontShow();        System.out.println("===============");        //中序遍历        binTree.midShow();        System.out.println("===============");        //后序遍历        binTree.afterShow();        System.out.println("===============");        //前序查找        TreeNode result = binTree.frontSearch(5);        System.out.println(result);        System.out.println("===============");        //删除一个子树        binTree.delete(4);        binTree.frontShow();    }}

#### 顺序存储的二叉树 ####

二叉树主要采用链式存储结构，顺序存储结构仅适用于完全二叉树（满二叉树）。

顺序存储的二叉树的性质

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 7]

顺序存储的二叉树的遍历

public class ArrayBinaryTree {
               int[] data;   public ArrayBinaryTree(int[] data) {
              this.data=data;   }   public void frontShow() {
              frontShow(0);   }   // 前序遍历   public void frontShow(int index) {      if(data==null || data.length==0) {         return;      }      // 先遍历当前节点的内容      System.out.println(data[index]);      // 2*index+1:处理左子树      if(2*index+1 < data.length) {         frontShow(2*index+1);      }      // 2*index+2:处理右子树      if(2*index+2 < data.length) {         frontShow(2*index+2);      }   }}

public class TestArrayBinaryTree {
           public static void main(String[] args) {
              int[] data = new int[] {
        1,2,3,4,5,6,7};      ArrayBinaryTree tree = new ArrayBinaryTree(data);      //前序遍历      tree.frontShow();   }}

### 线索二叉树 ###

![在这里插入图片描述][bd213810a4524bcfa11c19c073b62708.png]

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

对二叉树以某种次序进行遍历并加上线索的过程称为**线索化**。按先/中/后根遍历次序进行线索化的二叉树分别称为**先/中/后序线索二叉树**

前驱节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱节点；

后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；

例如一颗完全二叉树（1,2,3,4,5,6,7），按照中序遍历后的顺序为：（4,2,5,1,6,3,7），1节点的前驱节点为：5，后继节点为6.  
![在这里插入图片描述][e520e22a523149d1ac545a23bb5eed72.png]

现将某结点的空指针域指向该结点的前驱后继，定义规则如下：

> 若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。  
> 若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

![在这里插入图片描述][32394ecf158947ba8fca46020987ebac.png]

**线索二叉树的实现**

/** * 线索二叉树的二叉链表结点 */public class ThreadedNode {
            // 节点的权    int value;    // 左儿子    ThreadedNode leftNode;    // 右儿子    ThreadedNode rightNode;    // 标识指针类型    int leftType = 0;    int rightType = 0;    public ThreadedNode(int value) {        this.value = value;    }    // 设置左儿子    public void setLeftNode(ThreadedNode leftNode) {        this.leftNode = leftNode;    }    // 设置右儿子    public void setRightNode(ThreadedNode rightNode) {        this.rightNode = rightNode;    }}

// 线索二叉树public class ThreadedBinaryTree {    // 根节点    ThreadedNode root;    // 用于临时存储前驱节点    ThreadedNode pre = null;    //设置根节点    public void setRoot(ThreadedNode root) {        this.root = root;    }    // 中序线索化二叉树    public void threadNodes() {        threadNodes(root);    }    public void threadNodes(ThreadedNode node) {        // 当前节点如果为null，直接返回        if (node == null) {            return;        }        // 处理左子树        threadNodes(node.leftNode);        // 处理前驱节点        if (node.leftNode == null) {            //让当前节点的左指针指向前驱节点            node.leftNode = pre;            //改变当前节点左指针的类型            node.leftType = 1;        }        // 处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树)        if (pre != null && pre.rightNode == null) {            //让前驱节点的右指针指向当前节点            pre.rightNode = node;            //改变前驱节点的右指针类型            pre.rightType = 1;        }        // 每处理一个节点，当前节点是下一个节点的前驱节点        pre = node;        // 处理右子树        threadNodes(node.rightNode);    }    //获取根节点    public ThreadedNode getRoot() {        return root;    }}

![在这里插入图片描述][34562ab96f6f4afa97f9c2f4b09dbfc4.png]

**遍历线索二叉树**

// 遍历线索二叉树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 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);      //把新创建的节点设置为根节点的子节点      root.setLeftNode(rootL);      //创建一个右节点      ThreadedNode rootR = new ThreadedNode(3);      //把新创建的节点设置为根节点的子节点      root.setRightNode(rootR);      //为第二层的左节点创建两个子节点      rootL.setLeftNode(new ThreadedNode(4));      ThreadedNode fiveNode = new ThreadedNode(5);      rootL.setRightNode(fiveNode);      //为第二层的右节点创建两个子节点      rootR.setLeftNode(new ThreadedNode(6));      rootR.setRightNode(new ThreadedNode(7));      //中序遍历树      binTree.midShow();      System.out.println("===============");      //中前线索化二叉树      binTree.threadNodes();      binTree.threadIterate();   }}

### 赫夫曼树 ###

Huffman，又叫最优二叉树：它是n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。

![在这里插入图片描述][96971c0831794969a3c0329ba082b636.png]

路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图中从根结点到结点 c 的路径长度为 3。

叶结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图中结点 b 的带权路径长度为 2 \* 5 = 10 。

树的带权路径长度WPL（weighted path length）：树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。如图 中所示的这颗树的带权路径长度为：

> WPL = 7 \* 1 + 5 \* 2 + 2 \* 3 + 4 \* 3

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。

#### 构建赫夫曼树 ####

1.  在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
2.  在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
3.  重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

public class Node implements Comparable<Node> {
           int value;   Node left;   Node right;   public Node(int value) {
              this.value = value;   }   @Override   public int compareTo(Node o) {
              return -(this.value - o.value);   }   @Override   public String toString() {
              return "TreeNode [value=" + value + "]";   }}

public class TestHuffmanTree {
        	public static void main(String[] args) {
        		int[] arr = {
        3, 7, 8, 29, 5, 11, 23, 14};		Node node = createHuffmanTree(arr);		System.out.println(node);	}	// 创建赫夫曼树	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);			//取出来权值最小的两个二叉树			//取出最权值最小的二叉树			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);		}		return nodes.get(0);	}}

#### 赫夫曼编码 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

实现步骤：

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

/**	 * 进行赫夫曼编码压缩的方法	 *	 * @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;}/**	 * 把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 (Entry<Byte, Integer> entry : counts.entrySet()) {        nodes.add(new Node(entry.getKey(), entry.getValue()));    }    return nodes;}/**	 * 创建赫夫曼树	 *	 * @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);}// 用于临时存储路径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 bytes	 * @param huffCodes	 * @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;}

赫夫曼解码

/** * 使用指定的赫夫曼编码表进行解码 * * @param huffCodes * @param bytes * @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 src * @param dst * @throws IOException */private 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 src * @param dst * @throws Exception */private static void unZip(String src, String dst) throws Exception {
           //创建一个输入流   InputStream is = new FileInputStream(src);   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();}

测试

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();      }   }}

### 二叉排序树 ###

二叉排序树（Binary Sort Tree）或者是一课空树；或者是具有下列性质的二叉树：

1.  元素以关键字为依据，每个结点都可比较相等和大小，各元素关键字互不相同。
2.  对于每个结点，其左子树（不空）上所有结点元素均小于该结点，并且右子树（不空）上所有结点元素均大于该节点。
3.  每个结点的左、右子树也分别为二叉排序树

![在这里插入图片描述][bc3b4445a20b4bbebbb8663c648eea11.png]

创建二叉排序树&添加结点

public class Node {
            int value;    Node left;    Node right;    public Node(int value) {
                this.value = value;    }    /**    * 向子树中添加节点    *    * @param node    */    public void add(Node node) {
                if (node == null) {
                    return;        }        // 判断传入的节点的值比当前子树的根节点的值大还是小        // 添加的节点比当前节点的值更小        if (node.value < this.value) {            //如果左节点为空            if (this.left == null) {                this.left = node;                //如果不为空            } else {                this.left.add(node);            }        } else {            if (this.right == null) {                this.right = node;            } else {                this.right.add(node);            }        }    }    /**	 * 中序遍历	 *	 * @param node	 */    public void midShow(Node node) {        if (node == null) {            return;        }        midShow(node.left);        System.out.println(node.value);        midShow(node.right);    }}

// 二叉排序树public class BinarySortTree {    Node root;    /**    * 向二叉排序树中添加节点    *    * @param node    */    public void add(Node node) {        //如果是一颗空树        if (root == null) {            root = node;        } else {            root.add(node);        }    }    /**	 * 中序遍历二叉排序树，从小到大的顺序	 */    public void midShow() {        if (root != null) {            root.midShow(root);        }    }}

查找结点

Node类/** * 查找节点 * * @param value */public Node search(int value) {
           if (this.value == value) {
              return this;   } else if (value < this.value) {
              if (left == null) {
                 return null;      }      return left.search(value);   } else {
              if (right == null) {
                 return null;      }      return right.search(value);   }}

BinarySortTree类/** * 节点的查找 * * @param value * @return */public Node search(int value) {
           if (root == null) {
              return null;   } else {
              return root.search(value);   }}

删除结点

/** * 搜索父节点 * * @param value * @return */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;   }}

/** * 删除节点 * * @param value */public void delete(int value) {
           if (root == null) {
              return;   } else {
              //找到这个节点      Node target = search(value);      //如果没有这个节点      if (target == null) {         return;      }      //找到他的父节点      Node parent = searchParent(value);      //要删除的节点是叶子节点      if (target.left == null && target.right == null) {         //要删除的节点是父节点的左子节点         if (parent.left.value == value) {            parent.left = null;         //要删除的节点是父节点的右子节点         } else {            parent.right = null;         }      //要删除的节点有两个子节点的情况      } else if (target.left != null && target.right != null) {         //删除右子树中值最小的节点，取获取到该节点的值         int min = deleteMin(target.right);         //替换目标节点中的值         target.value = min;      //要删除的节点有一个左子节点或右子节点      } else {         //有左子节点         if (target.left != null) {            //要删除的节点是父节点的左子节点            if (parent.left.value == value) {               parent.left = target.left;               //要删除的节点是父节点的右子节点            } else {               parent.right = target.left;            }            //有右子节点         } else {            //要删除的节点是父节点的左子节点            if (parent.left.value == value) {               parent.left = target.right;               //要删除的节点是父节点的右子节点            } else {               parent.right = target.right;            }         }      }   }}/** * 删除一颗树中最小的节点 * * @param node * @return */private int deleteMin(Node node) {   Node target = node;   //递归向左找   while (target.left != null) {      target = target.left;   }   //删除最小的这个节点   delete(target.value);   return target.value;}/** * 搜索父节点 * * @param value * @return */public Node searchParent(int value) {   if (root == null) {      return null;   } else {      return root.searchParent(value);   }}

### AVL树 ###

为了降低二叉排序树的高度，提高查找效率，两位前苏联数学家于1962年提出一种高度平衡的二叉排序树，称为平衡二叉树（又称AVL树）。

**平衡二叉树**或者是一棵空二叉树，或者是具有下列性质的二叉排序树：1. 它的左子树和右子树都是平衡二叉树；2. 左子树和右子树的高度之差的绝对值不超过1。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 9]

构建平衡二叉树之单旋转

public class Node {
            int value;    Node left;    Node right;    public Node(int value) {
                this.value = value;    }    /**    * 返回当前节点的高度    *    * @return    */    public int height() {
                return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;    }    /**    * 获取左子树的高度    *    * @return    */    public int leftHeight() {
                if (left == null) {
                    return 0;        }        return left.height();    }    /**    * 获取右子树的高度    *    * @return    */    public int rightHeight() {
                if (right == null) {
                    return 0;        }        return right.height();    }    /**    * 向子树中添加节点    *    * @param node    */    public void add(Node node) {
                if (node == null) {
                    return;        }        //判断传入的节点的值比当前子树的根节点的值大还是小        //添加的节点比当前节点的值更小        if (node.value < this.value) {            //如果左节点为空            if (this.left == null) {                this.left = node;                //如果不为空            } else {                this.left.add(node);            }        } else {            if (this.right == null) {                this.right = node;            } else {                this.right.add(node);            }        }        //查询是否平衡        //进行右旋转        if (leftHeight() - rightHeight() >= 2) {            rightRotate();        }        //左旋转        if (leftHeight() - rightHeight() <= -2) {            leftRotate();        }    }    /**    * 左旋转    */    private void leftRotate() {        Node newLeft = new Node(value);        newLeft.left = left;        newLeft.right = right.left;        value = right.value;        right = right.right;        left = newLeft;    }    /**    * 右旋转    */    private void rightRotate() {        //创建一个新的节点，值等于当前节点的值        Node newRight = new Node(value);        //把新节点的右子树设置了当前节点的右子树        newRight.right = right;        //把新节点的左子树设置为当前节点的左子树的右子树        newRight.left = left.right;        //把当前节点的值换为左子节点的值        value = left.value;        //把当前节点的左子树设置了左子树的左子树        left = left.left;        //把当前节点的右子树设置为新节点        right = newRight;    }}

public class BinarySortTree {
            Node root;    /**    * 向二叉排序树中添加节点    *    * @param node    */    public void add(Node node) {
                //如果是一颗空树        if (root == null) {            root = node;        } else {            root.add(node);        }    }}

public class TestBinarySortTree {
            public static void main(String[] args) {
                //    int[] arr = new int[] {8,9,6,7,5,4};        int[] arr = new int[] {8,9,5,4,6,7};        //创建一颗二叉排序树        BinarySortTree bst = new BinarySortTree();        //循环添加        for(int i:arr) {            bst.add(new Node(i));        }        //查看高度        System.out.println(bst.root.height());        //        System.out.println(bst.root.value);    }}

构建平衡二叉树之双旋转

修改add方法/** * 向子树中添加节点 * * @param node */public void add(Node node) {
           if (node == null) {
              return;   }   //判断传入的节点的值比当前子树的根节点的值大还是小   //添加的节点比当前节点的值更小   if (node.value < this.value) {      //如果左节点为空      if (this.left == null) {         this.left = node;         //如果不为空      } else {         this.left.add(node);      }   } else {      if (this.right == null) {         this.right = node;      } else {         this.right.add(node);      }   }   //查询是否平衡   //进行右旋转   if (leftHeight() - rightHeight() >= 2) {      //双旋转      if (left != null && left.leftHeight() < left.rightHeight()) {         //先左旋转         left.leftRotate();         //再右旋转         rightRotate();         //单旋转      } else {         rightRotate();      }   }   //左旋转   if (leftHeight() - rightHeight() <= -2) {      //双旋转      if (right != null && right.rightHeight() < right.leftHeight()) {         right.rightRotate();         leftRotate();         //单旋转      } else {         leftRotate();      }   }}

### 多路查找树 ###

一般而言，我们都是在内存中处理数据，但假如我们要操作的数据集非常大，内存无法处理了，在这种情况下对数据的处理需要不断地从硬盘等存储设备中调入或调出内存页面。

对外存设备的读写，效率并不乐观。为了降低对外存设备的访问次数，我们需要新的数据结构来处理这个问题。之前学习过的树，一个结点可以有多个孩子，但它自身只能存储一个元素。二叉树限制更多，只有两个孩子结点。在元素非常多时，要么树的度非常大（结点拥有子树的个数的最大值），要么树的高度非常大，如果我们要查找某一元素，必须多次访问外存设备，这迫使我们要打破每一个结点只能存储一个元素的限制，引入多路查找树的概念。

**多路查找树**：其每一个结点的孩子数可以多于两个，且一个结点可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

**2-3 树**

2-3 树要么为空，要么具有以下性质：

*  对于 2- 节点，和普通的 BST 节点一样，有一个数据域和两个子节点指针，两个子节点要么为空，要么也是一个2-3树，当前节点的数据的值要大于左子树中所有节点的数据，要小于右子树中所有节点的数据。
 *  对于 3- 节点，有两个数据域 a 和 b 和三个子节点指针，左子树中所有的节点数据要小于a，中子树中所有节点数据要大于 a 而小于 b ，右子树中所有节点数据要大于 b 。
 *  所有叶子都在统一层上

![在这里插入图片描述][50a25bab99d24005bbc3445f0fa9a29a.png]

B树，又称平衡多叉搜索树

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 10]

## 哈希表 ##

**散列表**（**Hash table**，也叫**哈希表**），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做**散列表**。

### 散列函数的设计 ###

*  直接定址法
 *  数字分析法
 *  平方取中法
 *  取余法
 *  随机数法

public class StuInfo {
            private int age;    private int count;    public int getAge() {
                return age;    }    public void setAge(int age) {
                this.age = age;    }    public int getCount() {
                return count;    }    public void setCount(int count) {
                this.count = count;    }    /**    * 散列函数    */    @Override    public int hashCode() {
                return age;    }    public StuInfo(int age, int count) {
                this.age = age;        this.count = count;    }    public StuInfo(int age) {
                super();        this.age = age;    }    @Override    public String toString() {
                return "StuInfo [age=" + age + ", count=" + count + "]";    }}

public class HashTable {
            private StuInfo[] data = new StuInfo[100];    /**    * 向散列表中添加元素    * @param stuInfo    */    public void put(StuInfo stuInfo) {
                //调用散列函数获取存储位置        int index = stuInfo.hashCode();        //添加元素        data[index]=stuInfo;    }    public StuInfo get(StuInfo stuInfo) {        return data[stuInfo.hashCode()];    }    @Override    public String toString() {        return "HashTable [data=" + Arrays.toString(data) + "]";    }}

public class TestHashTable {
            public static void main(String[] args) {
                StuInfo s1 = new StuInfo(16, 3);        StuInfo s2 = new StuInfo(17, 11);        StuInfo s3 = new StuInfo(18, 23);        StuInfo s4 = new StuInfo(19, 24);        StuInfo s5 = new StuInfo(20, 9);        HashTable ht = new HashTable();        ht.put(s1);        ht.put(s2);        ht.put(s3);        ht.put(s4);        ht.put(s5);        System.out.println(ht);        //想要获取的目标数据        StuInfo target = new StuInfo(18);        StuInfo info = ht.get(target);        System.out.println(info);    }}

### 散列冲突的解决方案 ###

不管hash函数设计的如何巧妙，总会有特殊的key导致hash冲突，特别是对动态查找表来说。

hash函数解决冲突的方法有以下几个常用的方法

*  开放定制法
    
     *  线性探索法
     *  二次探测法
     *  再散列法
 *  链地址法

## 图 ##

图（Graph）是由顶点（Vertex）集合及顶点间的关系集合组成的一种数据结构。顶点之间的关系成为边（Edge）。一个图G记为G=（V,E），V是顶点Vi 的有限集合，n为定点数：E是边的有限集合

![在这里插入图片描述][45560dde0335420fab2745901b1db4f5.png]

无向图

有向图

完全图

带权图

邻接顶点

/**
     * 顶点类
     */
    public class Vertex {
        
    
       private String value;
    
       public String getValue() {
        
          return value;
       }
    
       public void setValue(String value) {
        
          this.value = value;
       }
    
       public Vertex(String value) {
        
          super();
          this.value = value;
       }
    
       @Override
       public String toString() {
        
          return value;
       }
    
    }

/**
     * 图
     */
    public class Graph {
        
    
       private Vertex[] vertex;
       public int[][] adjMat;
    
       //当前遍历的下标
       private int currentIndex;
    
       public Graph(int size) {
        
          vertex = new Vertex[size];
          adjMat = new int[size][size];
       }
    
       /**
        * 向图中加入一个顶点
        *
        * @param v
        */
       public void addVertex(Vertex v) {
        
          vertex[currentSize++] = v;
       }
    
       public void addEdge(String v1, String v2) {
        
          // 找出两个顶点的下标
          int index1 = 0;
          for (int i = 0; i < vertex.length; i++) {
        
             if (vertex[i].getValue().equals(v1)) {
        
                index1 = i;
                break;
             }
          }
          int index2 = 0;
          for (int i = 0; i < vertex.length; i++) {
        
             if (vertex[i].getValue().equals(v2)) {
        
                index2 = i;
                break;
             }
          }
          adjMat[index1][index2] = 1;
          adjMat[index2][index1] = 1;
       }
    }

public class TestGraph {
        
       public static void main(String[] args) {
        
          Vertex v1 = new Vertex("A");
          Vertex v2 = new Vertex("B");
          Vertex v3 = new Vertex("C");
          Vertex v4 = new Vertex("D");
          Vertex v5 = new Vertex("E");
          Graph g = new Graph(5);
          g.addVertex(v1);
          g.addVertex(v2);
          g.addVertex(v3);
          g.addVertex(v4);
          g.addVertex(v5);
          
          //增加边
          g.addEdge("A", "C");
          g.addEdge("B", "C");
          g.addEdge("A", "B");
          g.addEdge("B", "D");
          g.addEdge("B", "E");
          
          for(int[] a:g.adjMat) {
        
             System.out.println(Arrays.toString(a));
          }
       }
    }

深度优先搜索算法

广度优先搜索算法

/**
     * 顶点类
     */
    public class Vertex {
        
    
        private String value;
        public boolean visited;
    
        public String getValue() {
        
            return value;
        }
    
        public void setValue(String value) {
        
            this.value = value;
        }
    
        public Vertex(String value) {
        
            super();
            this.value = value;
        }
    
        @Override
        public String toString() {
        
            return value;
        }
    
    }

/**
     * 图
     */
    public class Graph {
        
    
        private Vertex[] vertex;
        private int currentSize;
        public int[][] adjMat;
        private MyStack stack = new MyStack();
    
        //当前遍历的下标
        private int currentIndex;
    
        public Graph(int size) {
        
            vertex = new Vertex[size];
            adjMat = new int[size][size];
        }
    
        /**
        * 向图中加入一个顶点
        *
        * @param v
        */
        public void addVertex(Vertex v) {
        
            vertex[currentSize++] = v;
        }
    
        public void addEdge(String v1, String v2) {
        
            // 找出两个顶点的下标
            int index1 = 0;
            for (int i = 0; i < vertex.length; i++) {
        
                if (vertex[i].getValue().equals(v1)) {
        
                    index1 = i;
                    break;
                }
            }
            int index2 = 0;
            for (int i = 0; i < vertex.length; i++) {
        
                if (vertex[i].getValue().equals(v2)) {
        
                    index2 = i;
                    break;
                }
            }
            adjMat[index1][index2] = 1;
            adjMat[index2][index1] = 1;
        }
    
        /**
        * 深度优先搜索算法遍历图
        */
        public void dfs() {
        
            //把第0个顶点标记为已访问状态
            vertex[0].visited = true;
            //把第0个顶点的下标。
            stack.push(0);
            //打印顶点的值
            System.out.println(vertex[0].getValue());
            //遍历
            out:
            while (!stack.isEmpty()) {
        
                for (int i = currentIndex + 1; i < vertex.length; i++) {
        
                    //如果和下一个遍历的元素是通的
                    if (adjMat[currentIndex][i] == 1 && vertex[i].visited == false) {
        
                        //把下一个元素压入栈中
                        stack.push(i);
                        vertex[i].visited = true;
                        System.out.println(vertex[i].getValue());
                        continue out;
                    }
                }
                //弹出栈顶元素
                stack.pop();
                //修改当前位置为栈顶元素的位置
                if (!stack.isEmpty()) {
        
                    currentIndex = stack.peek();
                }
            }
        }
    }

public class TestGraph {
        
    
        public static void main(String[] args) {
        
            Vertex v1 = new Vertex("A");
            Vertex v2 = new Vertex("B");
            Vertex v3 = new Vertex("C");
            Vertex v4 = new Vertex("D");
            Vertex v5 = new Vertex("E");
            Graph g = new Graph(5);
            g.addVertex(v1);
            g.addVertex(v2);
            g.addVertex(v3);
            g.addVertex(v4);
            g.addVertex(v5);
    
            //增加边
            g.addEdge("A", "C");
            g.addEdge("B", "C");
            g.addEdge("A", "B");
            g.addEdge("B", "D");
            g.addEdge("B", "E");
    
            for(int[] a:g.adjMat) {
        
                System.out.println(Arrays.toString(a));
            }
            //深度优先遍历
            g.dfs();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70]: /images/20220828/e6e314b9556a48af8f60d304cf9bdf75.png
[20210713113823436.png]: /images/20220828/71f6fd0a90cb4797859b428f580e87ee.png
[20210713113936576.png]: /images/20220828/65a49f5decde40a38cb7e3d436dbb91c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70 1]: /images/20220828/932640ac9da2450cbdd140a29c16274f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70 2]: /images/20220828/b83a84f9388948a493c916da25b84806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1MjIzMTU5NTc0Mg_size_16_color_FFFFFF_t_70 3]: /images/20220828/02a5366bebc54442bbd7551fef43a884.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/418627a692eb416ab3487a2f00b9932d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8747eaad48ed405880c112bf34803161.png
[img]: /images/20220828/508708c04667470986d902f8aac39c48.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/b454adb2a28f46fe823f7175fbd407d3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/79ea14d030ca43489b98634ecadc023f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/b3752a25036f43eaa23c0667206a3660.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/3054f9371ce14d26a0612bbc7ab07799.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/d6d4016021174c9481d05b1d1aca1f64.png
[5ac23a6d191c48f1a55f8ec565a25cdb.png]: /images/20220828/7f4b0bf1afc042819c71f7375aaf9393.png
[6eaad7d2e2124fd6bad83ace62093fa0.png]: /images/20220828/40ecf76e4fd241038ce294aeb6163261.png
[fb74391074874d5ea4fd84d99a015b3e.png]: /images/20220828/05876f3a18b74a6781e6cedf4bcb9fe8.png
[bdaabcb7a94e4c8fb28edd7f9222b940.png]: /images/20220828/05ec2fd21ae2416e91ab630a74d911e0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/e750affa2d1d4ca8b1c0487d03a64194.png
[bd213810a4524bcfa11c19c073b62708.png]: /images/20220828/51c759e5e7064fbe9174256f3cda7924.png
[e520e22a523149d1ac545a23bb5eed72.png]: /images/20220828/79c5235bf29144ac99eff3629c4ff09f.png
[32394ecf158947ba8fca46020987ebac.png]: /images/20220828/6c7d414ab4724f5ab24f5bd978e86483.png
[34562ab96f6f4afa97f9c2f4b09dbfc4.png]: /images/20220828/ce15a5322e90480ba7d8f1c265d83ed2.png
[96971c0831794969a3c0329ba082b636.png]: /images/20220828/701c745456624684aed4a30cfd1789b0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/2a2335f639c5413d979e1990c741eac8.png
[bc3b4445a20b4bbebbb8663c648eea11.png]: /images/20220828/ee5c257c93b54550ae8e45c7348ad92f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/ab473802814a4058bce96ea2194f3e85.png
[50a25bab99d24005bbc3445f0fa9a29a.png]: /images/20220828/f49a682f26e84308a8a358554bb02c72.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6b6Z5a6HXw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/de1aaacc44534be089256461cb4f4d3e.png
[45560dde0335420fab2745901b1db4f5.png]: /images/20220828/9d58be5c9b4140d68f5ec30d76b5d231.png