常见的四类基本数据结构有

数据结构 



数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 

集合   结构中的数据元素除了同属于一种类型外，别无其它关系。 

线性结构    结构中的数据元素之间存在一对一的关系。 

树型结构       结构中的数据元素之间存在一对多的关系。 

图状结构或网状结构   结构中的数据元素之间存在多对多的关系。

 

数据结构在计算机中有两种不同的存储方法：

顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 

链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。

时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

有时候，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同，如在冒泡排序中，输入数据有序而无序，其结果是不一样的。此时，我们计算平均值。

常见的算法的时间 复杂度之间的关系为：

O(1)<O(logn)<O(n)<O(nlog n)<O(n2)<O(2n)<O(n!)<O(nn) 

实例1

  sum=0；                         //（1）

     for(i=1;i<=n;i++)          //（2）

        for(j=1;j<=n;j++)       //（3）

         sum++；                  //（4）

语句（1）执行1次，

语句（2）执行n次

语句（3）执行n2次

语句（4）执行n2次

T(n) = 1+n+2n2= O(n2)

实例2

     a=0; b=1;                 //（1）

    for (i=1;i<=n;i++)      //（2）

    { 

       s=a+b;　　　　    //（3）

       b=a;　　　　　    //（4） 

       a=s;　　　　　    //（5）

    }



语句（1）执行1次，

语句（2）执行n次

语句（3）、（4）、（5）执行n次

T(n) = 1+4n =O(n)

实例3

    i=1;            //（1）

    while (i<=n)

       i=i*2;       //（2）



语句（1）的频度是1,

设语句2的频度是f(n)，则：2f(n)<=n;f(n)<=log2n   

取最大值f(n)= log2n,

T(n)=O(log2n )

 

空间复杂度

空间复杂度：算法所需存储空间的度量，记作： 

      S(n)=O( f(n) )           

其中 n 为问题的规模。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。如果额外空间相对于输入数据量来说是个常数，则称此算法是原地工作。

算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

 

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

　　通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

一个数据结构必须具有以下基本功能：

        ①、如何插入一条新的数据项

　　②、如何寻找某一特定的数据项

　　③、如何删除某一特定的数据项

　　④、如何迭代的访问各个数据项，以便进行显示或其他操作



算法简单来说就是解决问题的步骤。

　　在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。



　　一、算法的五个特征

　　①、有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。

　　②、确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

　　③、可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

　　④、有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

　　⑤、有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法功能　　



　    二、算法的设计原则

　　①、正确性：首先，算法应当满足以特定的“规则说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：

　　　　　　　　一、程序语法错误。

　　　　　　　　二、程序对于几组输入数据能够得出满足需要的结果。

　　　　　　　　三、程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。

　　　　　　　　四、程序对于一切合法的输入数据都能得到满足要求的结果。

　　　　　　　　PS：通常以第 三 层意义的正确性作为衡量一个算法是否合格的标准。

　　②、可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。

　　③、健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

　　④、高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

　　前面三点 正确性，可读性和健壮性相信都好理解。对于第四点算法的执行效率和存储量，我们知道比较算法的时候，可能会说“A算法比B算法快两倍”之类的话，但实际上这种说法没有任何意义。因为当数据项个数发生变化时，A算法和B算法的效率比例也会发生变化，比如数据项增加了50%，可能A算法比B算法快三倍，但是如果数据项减少了50%，可能A算法和B算法速度一样。所以描述算法的速度必须要和数据项的个数联系起来。也就是“大O”表示法，它是一种算法复杂度的相对表示方式，这里我简单介绍一下，后面会根据具体的算法来描述。

　　相对(relative)：你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是，比较2个算法所做的算术操作（一个做乘法，一个做加法）将会告诉你一些有意义的东西；

　　表示(representation)：大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如，排序算法之间的对比通常是基于比较操作(比较2个结点来决定这2个结点的相对顺序)。这里面就假设了比较操作的计算开销很大。但是，如果比较操作的计算开销不大，而交换操作的计算开销很大，又会怎么样呢？这就改变了先前的比较方式；

　　复杂度(complexity)：如果排序10,000个元素花费了我1秒，那么排序1百万个元素会花多少时间？在这个例子里，复杂度就是相对其他东西的度量结果。

　　然后我们在说说算法的存储量，包括：

　　程序本身所占空间；

　　输入数据所占空间；

　　辅助变量所占空间；

　　一个算法的效率越高越好，而存储量是越低越好。

 

数组

数组是用来存放同一种数据类型的集合（Object类型数组除外)。







用类的思想封装一个数组
package com.ys.array;
  2  
  3 public class MyArray {
  4     //定义一个数组
  5     private int [] intArray;
  6     //定义数组的实际有效长度
  7     private int elems;
  8     //定义数组的最大长度
  9     private int length;
 10      
 11     //默认构造一个长度为50的数组
 12     public MyArray(){
 13         elems = 0;
 14         length = 50;
 15         intArray = new int[length];
 16     }
 17     //构造函数，初始化一个长度为length 的数组
 18     public MyArray(int length){
 19         elems = 0;
 20         this.length = length;
 21         intArray = new int[length];
 22     }
 23      
 24     //获取数组的有效长度
 25     public int getSize(){
 26         return elems;
 27     }
 28      
 29     /**
 30      * 遍历显示元素
 31      */
 32     public void display(){
 33         for(int i = 0 ; i < elems ; i++){
 34             System.out.print(intArray[i]+" ");
 35         }
 36         System.out.println();
 37     }
 38      
 39     /**
 40      * 添加元素
 41      * @param value,假设操作人是不会添加重复元素的，如果有重复元素对于后面的操作都会有影响。
 42      * @return添加成功返回true,添加的元素超过范围了返回false
 43      */
 44     public boolean add(int value){
 45         if(elems == length){
 46             return false;
 47         }else{
 48             intArray[elems] = value;
 49             elems++;
 50         }
 51         return true;
 52     }
 53      
 54     /**
 55      * 根据下标获取元素
 56      * @param i
 57      * @return查找下标值在数组下标有效范围内，返回下标所表示的元素
 58      * 查找下标超出数组下标有效值，提示访问下标越界
 59      */
 60     public int get(int i){
 61         if(i<0 || i>elems){
 62             System.out.println("访问下标越界");
 63         }
 64         return intArray[i];
 65     }
 66     /**
 67      * 查找元素
 68      * @param searchValue
 69      * @return查找的元素如果存在则返回下标值，如果不存在，返回 -1
 70      */
 71     public int find(int searchValue){
 72         int i ;
 73         for(i = 0 ; i < elems ;i++){
 74             if(intArray[i] == searchValue){
 75                 break;
 76             }
 77         }
 78         if(i == elems){
 79             return -1;
 80         }
 81         return i;
 82     }
 83     /**
 84      * 删除元素
 85      * @param value
 86      * @return如果要删除的值不存在，直接返回 false;否则返回true，删除成功
 87      */
 88     public boolean delete(int value){
 89         int k = find(value);
 90         if(k == -1){
 91             return false;
 92         }else{
 93             if(k == elems-1){
 94                 elems--;
 95             }else{
 96                 for(int i = k; i< elems-1 ; i++){
 97                     intArray[i] = intArray[i+1];
 98                    
 99                 }
100                  elems--;
101             }
102             return true;
103         }
104     }
105     /**
106      * 修改数据
107      * @param oldValue原值
108      * @param newValue新值
109      * @return修改成功返回true，修改失败返回false
110      */
111     public boolean modify(int oldValue,int newValue){
112         int i = find(oldValue);
113         if(i == -1){
114             System.out.println("需要修改的数据不存在");
115             return false;
116         }else{
117             intArray[i] = newValue;
118             return true;
119         }
120     }
121  
122 }  

数组的局限性分析：

　　①、插入快，对于无序数组，上面我们实现的数组就是无序的，即元素没有按照从大到小或者某个特定的顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但是有序数组却不一定了，它需要在指定的位置插入。

　　②、查找慢，当然如果根据下标来查找是很快的。但是通常我们都是根据元素值来查找，给定一个元素值，对于无序数组，我们需要从数组第一个元素开始遍历，直到找到那个元素。有序数组通过特定的算法查找的速度会比无需数组快，后面我们会讲各种排序算法。

　　③、删除慢，根据元素值删除，我们要先找到该元素所处的位置，然后将元素后面的值整体向前面移动一个位置。也需要比较多的时间。

　　④、数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了。

　　很显然，数组更多的是用来进行数据的存储，纯粹用来存储数据的数据结构，数组虽然插入快，但是查找和删除都比较慢，而且扩展性差，所以我们一般不会用数组来存储数据，那有没有什么数据结构插入、查找、删除都很快，而且还能动态扩展存储个数大小呢，答案是有的，但是这是建立在很复杂的算法基础上。

栈（英语：stack）又称为堆栈或堆叠

        数组更多的是用来进行数据的存储，纯粹用来存储数据的数据结构，我们期望的是插入、删除和查找性能都比较好。对于无序数组，插入快，但是删除和查找都很慢，为了解决这些问题，后面我们会讲解比如二叉树、哈希表的数据结构。

　　而本篇博客讲解的数据结构和算法更多是用作程序员的工具，它们作为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比数据库类型的结构要短得多，在程序执行期间它们才被创建，通常用它们去执行某项特殊的业务，执行完成之后，它们就被销毁。这里的它们就是——栈和队列。本篇博客我们先介绍栈。

         栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

　　栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

　　由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。



利用栈的特性可以进行数据反转
//进行字符串反转
@Test
public void testStringReversal(){
    ArrayStack stack = new ArrayStack();
    String str = "how are you";
    char[] cha = str.toCharArray();
    for(char c : cha){
        stack.push(c);
    }
    while(!stack.isEmpty()){
        System.out.print(stack.pop());
    }
}
利用栈判断分隔符是否匹配　　 

　　写过xml标签或者html标签的，我们都知道<必须和最近的>进行匹配，[ 也必须和最近的 ] 进行匹配。

　　比如：<abc[123]abc>这是符号相匹配的，如果是 <abc[123>abc] 那就是不匹配的。

　　对于 12<a[b{c}]>，我们分析在栈中的数据：遇到匹配正确的就消除



最后栈中的内容为空则匹配成功，否则匹配失败！！！

//分隔符匹配
//遇到左边分隔符了就push进栈，遇到右边分隔符了就pop出栈，看出栈的分隔符是否和这个有分隔符匹配
@Test
public void testMatch(){
    ArrayStack stack = new ArrayStack(3);
    String str = "12<a[b{c}]>";
    char[] cha = str.toCharArray();
    for(char c : cha){
        switch (c) {
        case '{':
        case '[':
        case '<':
            stack.push(c);
            break;
        case '}':
        case ']':
        case '>':
            if(!stack.isEmpty()){
                char ch = stack.pop().toString().toCharArray()[0];
                if(c=='}' && ch != '{'
                    || c==']' && ch != '['
                    || c==')' && ch != '('){
                    System.out.println("Error:"+ch+"-"+c);
                }
            }
            break;
        default:
            break;
        }
    }
}

        根据栈后进先出的特性，我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具，具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop()，使得程序不容易出错。

　　对于栈的实现，我们稍微分析就知道，数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作，我们不要画蛇添足。　　

队列

　　队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

　　队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

        比如我们去电影院排队买票，第一个进入排队序列的都是第一个买到票离开队列的人，而最后进入排队序列排队的都是最后买到票的，再比如在计算机操作系统中，有各种队列在安静的工作着，比如打印机在打印列队中等待打印。

队列分为：

　　①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。

　　②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

　　③、优先级队列，优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小                 或最大等数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

首先是单向队列：







双向队列：

双端队列就是一个两端都是结尾或者开头的队列， 队列的每一端都可以进行插入数据项和移除数据项，这些方法可以叫做：

　　insertRight()、insertLeft()、removeLeft()、removeRight()

　　如果严格禁止调用insertLeft()和removeLeft()（或禁用右端操作），那么双端队列的功能就和前面讲的栈功能一样。

　　如果严格禁止调用insertLeft()和removeRight(或相反的另一对方法)，那么双端队列的功能就和单向队列一样了。

优先级队列（priority queue）是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

　　优先级队列 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有：

　　（1）查找

　　（2）插入一个新元素

　　（3）删除

　　一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素 。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

　　这里我们用数组实现优先级队列，这种方法插入比较慢，但是它比较简单，适用于数据量比较小并且不是特别注重插入速度的情况。

　　后面我们会讲解堆，用堆的数据结构来实现优先级队列，可以相当快的插入数据。

　　数组实现优先级队列，声明为int类型的数组，关键字是数组里面的元素，在插入的时候按照从大到小的顺序排列，也就是越小的元素优先级越高。

　insert() 方法，先检查队列中是否有数据项，如果没有，则直接插入到下标为0的单元里，否则，从数组顶部开始比较，找到比插入值小的位置进行插入，并把 nItems 加1.

　　remove 方法直接获取顶部元素。

　　优先级队列的插入操作需要 O(N)的时间，而删除操作则需要O(1) 的时间，后面会讲解如何通过 堆 来改进插入时间。

总结：

单向队列遵循先进先出的原则，而且一端只能插入，另一端只能删除。双向队列则两端都可插入和删除，如果限制双向队列的某一段的方法，则可以达到和单向队列同样的功能。最后优先级队列，则是在插入元素的时候进行了优先级别排序，在实际应用中单项队列和优先级队列使用的比较多。后面讲解了堆这种数据结构，我们会用堆来实现优先级队列，改善优先级队列插入元素的时间。

　　①、栈、队列（单向队列）、优先级队列通常是用来简化某些程序操作的数据结构，而不是主要作为存储数据的。

　　②、在这些数据结构中，只有一个数据项可以被访问。

　　③、栈允许在栈顶压入（插入）数据，在栈顶弹出（移除）数据，但是只能访问最后一个插入的数据项，也就是栈顶元素。

　　④、队列（单向队列）只能在队尾插入数据，对头删除数据，并且只能访问对头的数据。而且队列还可以实现循环队列，它基于数组，数组下标可以从数组末端绕回到数组的开始位置。

　　⑤、优先级队列是有序的插入数据，并且只能访问当前元素中优先级别最大（或最小）的元素。

　　⑥、这些数据结构都能由数组实现，但是可以用别的机制（后面讲的链表、堆等数据结构）实现。

 

java中的前缀、中缀、后缀表达式

1、人如何解析算术表达式



这个表达式，我们在看到3+4后都不能直接计算3+4的值，知道看到4后面的 - 号，因为减号的优先级和前面的加号一样，所以可以计算3+4的值了，如果4后面是 * 或者 /，那么就要在乘除过后才能做加法操作，比如：



2、计算机如何解析算术表达式

　　对于前面的表达式 3+4-5，我们人是有思维能力的，能根据操作符的位置，以及操作符的优先级别能算出该表达式的结果。但是计算机怎么算？

　　计算机必须要向前（从左到右）来读取操作数和操作符，等到读取足够的信息来执行一个运算时，找到两个操作数和一个操作符进行运算，有时候如果后面是更高级别的操作符或者括号时，就必须推迟运算，必须要解析到后面级别高的运算，然后回头来执行前面的运算。我们发现这个过程是极其繁琐的，而计算机是一个机器，只认识高低电平，想要完成一个简单表达式的计算，我们可能要设计出很复杂的逻辑电路来控制计算过程，那更不用说很复杂的算术表达式，所以这样来解析算术表达式是不合理的，那么我们应该采取什么办法呢？

　　请大家先看看什么是前缀表达式，中缀表达式，后缀表达式：这三种表达式其实就是算术表达式的三种写法，以 3+4-5为例

　　①、前缀表达式：操作符在操作数的前面，比如 +-543

　　②、中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式 3+4-5

　　③、后缀表达式：操作符在操作数的后面，比如 34+5-

　　上面我们讲的人是如何解析算术表达式的，也就是解析中缀表达式，这是人最容易识别的，但是计算机不容易识别，计算机容易识别的是前缀表达式和后缀表达式，将中缀表达式转换为前缀表达式或者后缀表达式之后，计算机能很快计算出表达式的值，那么中缀表达式是如何转换为前缀表达式和后缀表达式，以及计算机是如何解析前缀表达式和后缀表达式来得到结果的呢？

3、后缀表达式

　　后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

　　由于后缀表达式的运算符在两个操作数的后面，那么计算机在解析后缀表达式的时候，只需要从左向右扫描，也就是只需要向前扫描，而不用回头扫描，遇到运算符就将运算符放在前面两个操作符的中间（这里先不考虑乘方类似的单目运算），一直运算到最右边的运算符，那么就得出运算结果了。既然后缀表达式这么好，那么问题来了：



　　①、如何将中缀表达式转换为后缀表达式？

　　对于这个问题，转换的规则如下：







4、前缀表达式

　　前缀表达式，指的是不包含括号，运算符放在两个运算对象的前面，严格从右向左进行（不再考虑运算符的优先规则），所有的计算按运算符出现的顺序。

　　注意：后缀表达式是从左向右解析，而前缀表达式是从右向左解析。



　　①、如何将中缀表达式转换为前缀表达式？





 

链表

前面博客我们在讲解数组中，知道数组作为数据存储结构有一定的缺陷。在无序数组中，搜索性能差，在有序数组中，插入效率又很低，而且这两种数组的删除效率都很低，并且数组在创建后，其大小是固定了，设置的过大会造成内存的浪费，过小又不能满足数据量的存储。

　　本篇博客我们将讲解一种新型的数据结构——链表。我们知道数组是一种通用的数据结构，能用来实现栈、队列等很多数据结构。而链表也是一种使用广泛的通用数据结构，它也可以用来作为实现栈、队列等数据结构的基础，基本上除非需要频繁的通过下标来随机访问各个数据，否则很多使用数组的地方都可以用链表来代替。

　　但是我们需要说明的是，链表是不能解决数据存储的所有问题的，它也有它的优点和缺点。本篇博客我们介绍几种常见的链表，分别是单向链表、双端链表、有序链表、双向链表以及有迭代器的链表。并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述栈和队列，如何用链表代替数组来实现栈和队列。

1、链表（linked list ）

链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）

　　链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

　　使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

2、单向链表（single-linked list）

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。

　　单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。



3、双段链表（doublepoint-linked list）

对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。



4、抽象数据类型（ADT）

在介绍抽象数据类型的时候，我们先看看什么是数据类型，听到这个词，在Java中我们可能首先会想到像 int,double这样的词，这是Java中的基本数据类型，一个数据类型会涉及到两件事：

　　①、拥有特定特征的数据项

　　②、在数据上允许的操作

　　比如Java中的int数据类型，它表示整数，取值范围为：-2147483648~2147483647，还能使用各种操作符，+、-、*、/ 等对其操作。数据类型允许的操作是它本身不可分离的部分，理解类型包括理解什么样的操作可以应用在该类型上。

　　那么当年设计计算机语言的人，为什么会考虑到数据类型？

　　我们先看这样一个例子，比如，大家都需要住房子，也都希望房子越大越好。但显然，没有钱，考虑房子没有意义。于是就出现了各种各样的商品房，有别墅的、复式的、错层的、单间的……甚至只有两平米的胶囊房间。这样做的意义是满足不同人的需要。

　　同样，在计算机中，也存在相同的问题。计算1+1这样的表达式不需要开辟很大的存储空间，不需要适合小数甚至字符运算的内存空间。于是计算机的研究者们就考虑，要对数据进行分类，分出来多种数据类型。比如int，比如float。

　　虽然不同的计算机有不同的硬件系统，但实际上高级语言编写者才不管程序运行在什么计算机上，他们的目的就是为了实现整形数字的运算，比如a+b等。他们才不关心整数在计算机内部是如何表示的，也不管CPU是如何计算的。于是我们就考虑，无论什么计算机、什么语言都会面临类似的整数运算，我们可以考虑将其抽象出来。抽象是抽取出事物具有的普遍性本质，是对事物的一个概括，是一种思考问题的方式。

　　抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。它仅取决于其逻辑特征，而与计算机内部如何表示和实现无关。比如刚才说得整型，各个计算机，不管大型机、小型机、PC、平板电脑甚至智能手机，都有“整型”类型，也需要整形运算，那么整型其实就是一个抽象数据类型。 　

　　更广泛一点的，比如我们刚讲解的栈和队列这两种数据结构，我们分别使用了数组和链表来实现，比如栈，对于使用者只需要知道pop()和push()方法或其它方法的存在以及如何使用即可，使用者不需要知道我们是使用的数组或是链表来实现的。

　　ADT的思想可以作为我们设计工具的理念，比如我们需要存储数据，那么就从考虑需要在数据上实现的操作开始，需要存取最后一个数据项吗？还是第一个？还是特定值的项？还是特定位置的项？回答这些问题会引出ADT的定义，只有完整的定义了ADT后，才应该考虑实现的细节。

　　这在我们Java语言中的接口设计理念是想通的。

5、有序链表

前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。

　　在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

　　在有序链表中插入和删除某一项最多需要O(N)次比较，平均需要O(N/2)次，因为必须沿着链表上一步一步走才能找到正确的插入位置，然而可以最快速度删除最值，因为只需要删除表头即可，如果一个应用需要频繁的存取最小值，且不需要快速的插入，那么有序链表是一个比较好的选择方案。比如优先级队列可以使用有序链表来实现。

6、有序链表和无序数组组合排序

比如有一个无序数组需要排序，前面我们在讲解冒泡排序、选择排序、插入排序这三种简单的排序时，需要的时间级别都是O(N2)。

　　现在我们讲解了有序链表之后，对于一个无序数组，我们先将数组元素取出，一个一个的插入到有序链表中，然后将他们从有序链表中一个一个删除，重新放入数组，那么数组就会排好序了。和插入排序一样，如果插入了N个新数据，那么进行大概N2/4次比较。但是相对于插入排序，每个元素只进行了两次排序，一次从数组到链表，一次从链表到数组，大概需要2*N次移动，而插入排序则需要N2次移动，

　　效率肯定是比前面讲的简单排序要高，但是缺点就是需要开辟差不多两倍的空间，而且数组和链表必须在内存中同时存在，如果有现成的链表可以用，那么这种方法还是挺好的。

7、双向链表（twoway-linked list）



8、总结

上面我们讲了各种链表，每个链表都包括一个LinikedList对象和许多Node对象，LinkedList对象通常包含头和尾节点的引用，分别指向链表的第一个节点和最后一个节点。而每个节点对象通常包含数据部分data，以及对上一个节点的引用prev和下一个节点的引用next，只有下一个节点的引用称为单向链表，两个都有的称为双向链表。next值为null则说明是链表的结尾，如果想找到某个节点，我们必须从第一个节点开始遍历，不断通过next找到下一个节点，直到找到所需要的。栈和队列都是ADT，可以用数组来实现，也可以用链表实现。

 

递归的应用

记得小时候经常讲的一个故事：从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，一天，老和尚给小和尚讲了一个故事，故事内容是“从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，一天，老和尚给小和尚讲了一个故事，故事内容......”

　　什么是递归，上面的小故事就是一个明显的递归。以编程的角度来看，程序调用自身的编程技巧称为递归（ recursion）。

　　百度百科中的解释是这样的：递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

1、递归的定义

递归，就是在运行的过程中调用自己。

　　递归必须要有三个要素：

　　①、边界条件

　　②、递归前进段

　　③、递归返回段

　　当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2、例如求一个数的阶乘

/**
 * 0！=1  1！=1
 * 负数没有阶乘,如果输入负数返回-1
 * @param n
 * @return
 */
public static int getFactorial(int n){
    if(n >= 0){
        if(n==0){
            System.out.println(n+"!=1");
            return 1;
        }else{
            System.out.println(n);
            int temp = n*getFactorial(n-1);
            System.out.println(n+"!="+temp);
            return temp;
        }
    }
    return -1;
}



3、递归的二分查找法

注意：二分查找的数组一定是有序的！！！

　　在有序数组array[]中，不断将数组的中间值（mid）和被查找的值比较，如果被查找的值等于array[mid],就返回下标mid; 否则，就将查找范围缩小一半。如果被查找的值小于array[mid], 就继续在左半边查找;如果被查找的值大于array[mid],  就继续在右半边查找。 直到查找到该值或者查找范围为空时， 查找结束。



不用递归的二分查找法：
/**
 * 找到目标值返回数组下标，找不到返回-1
 * @param array
 * @param key
 * @return
 */
public static int findTwoPoint(int[] array,int key){
    int start = 0;
    int last = array.length-1;
    while(start <= last){
        int mid = (last-start)/2+start;//防止直接相加造成int范围溢出
        if(key == array[mid]){//查找值等于当前值，返回数组下标
            return mid;
        }
        if(key > array[mid]){//查找值比当前值大
            start = mid+1;
        }
        if(key < array[mid]){//查找值比当前值小
            last = mid-1;
        }
    }
    return -1;
}
二分查找用递归来改写，相信也很简单。边界条件是找到当前值，或者查找范围为空。否则每一次查找都将范围缩小一半。
public static int search(int[] array,int key,int low,int high){
    int mid = (high-low)/2+low;
    if(key == array[mid]){//查找值等于当前值，返回数组下标
        return mid;
    }else if(low > high){//找不到查找值，返回-1
        return -1;
    }else{
        if(key < array[mid]){//查找值比当前值小
            return search(array,key,low,mid-1);
        }
        if(key > array[mid]){//查找值比当前值大
            return search(array,key,mid+1,high);
        }
    }
    return -1;
}
递归的二分查找和非递归的二分查找效率都为O(logN)，递归的二分查找更加简洁，便于理解，但是速度会比非递归的慢。

4、分治算法

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

　　上面讲的递归的二分查找法就是一个分治算法的典型例子，分治算法常常是一个方法，在这个方法中含有两个对自身的递归调用，分别对应于问题的两个部分。

　　二分查找中，将查找范围分成比查找值大的一部分和比查找值小的一部分，每次递归调用只会有一个部分执行。

5、汉诺塔问题

汉诺塔问题是由很多放置在三个塔座上的盘子组成的一个古老的难题。如下图所示，所有盘子的直径是不同的，并且盘子中央都有一个洞使得它们刚好可以放在塔座上。所有的盘子刚开始都放置在A 塔座上。这个难题的目标是将所有的盘子都从塔座A移动到塔座C上，每次只可以移动一个盘子，并且任何一个盘子都不可以放置在比自己小的盘子之上。



试想一下，如果只有两个盘子，盘子从小到大我们以数字命名（也可以想象为直径），两个盘子上面就是盘子1，下面是盘子2，那么我们只需要将盘子1先移动到B塔座上，然后将盘子2移动到C塔座，最后将盘子1移动到C塔座上。即完成2个盘子从A到C的移动。

　　如果有三个盘子，那么我们将盘子1放到C塔座，盘子2放到B塔座，在将C塔座的盘子1放到B塔座上，然后将A塔座的盘子3放到C塔座上，然后将B塔座的盘子1放到A塔座，将B塔座的盘子2放到C塔座，最后将A塔座的盘子1放到C塔座上。

　　如果有四个，五个，N个盘子，那么我们应该怎么去做？这时候递归的思想就很好解决这样的问题了，当只有两个盘子的时候，我们只需要将B塔座作为中介，将盘子1先放到中介塔座B上，然后将盘子2放到目标塔座C上，最后将中介塔座B上的盘子放到目标塔座C上即可。

　　所以无论有多少个盘子，我们都将其看做只有两个盘子。假设有 N 个盘子在塔座A上，我们将其看为两个盘子，其中(N-1)~1个盘子看成是一个盘子，最下面第N个盘子看成是一个盘子，那么解决办法为：

　　①、先将A塔座的第(N-1)~1个盘子看成是一个盘子，放到中介塔座B上，然后将第N个盘子放到目标塔座C上。

　　②、然后A塔座为空，看成是中介塔座，B塔座这时候有N-1个盘子，将第(N-2)~1个盘子看成是一个盘子，放到中介塔座A上，然后将B塔座的第(N-1)号盘子放到目标塔座C上。

　　③、这时候A塔座上有(N-2)个盘子，B塔座为空，又将B塔座视为中介塔座，重复①，②步骤，直到所有盘子都放到目标塔座C上结束。

　　简单来说，跟把大象放进冰箱的步骤一样，递归算法为：

　　①、从初始塔座A上移动包含n-1个盘子到中介塔座B上。

　　②、将初始塔座A上剩余的一个盘子（最大的一个盘子）放到目标塔座C上。

　　③、将中介塔座B上n-1个盘子移动到目标塔座C上。

/**
 * 汉诺塔问题
 * @param dish 盘子个数(也表示名称)
 * @param from 初始塔座
 * @param temp 中介塔座
 * @param to   目标塔座
 */
public static void move(int dish,String from,String temp,String to){
    if(dish == 1){
        System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to);
    }else{
        move(dish-1,from,to,temp);//A为初始塔座，B为目标塔座，C为中介塔座
        System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to);
        move(dish-1,temp,from,to);//B为初始塔座，C为目标塔座，A为中介塔座
    }
}



5、归并排序



/**
 * 传入两个有序数组a和b，返回一个排好序的合并数组
 * @param a
 * @param b
 * @return
 */
public static int[] sort(int[] a,int[] b){
    int[] c = new int[a.length+b.length];
    int aNum = 0,bNum = 0,cNum=0;
    while(aNum<a.length && bNum < b.length){
        if(a[aNum] >= b[bNum]){//比较a数组和b数组的元素，谁更小将谁赋值到c数组
            c[cNum++] = b[bNum++];
        }else{
            c[cNum++] = a[aNum++];
        }
    }
    //如果a数组全部赋值到c数组了，但是b数组还有元素，则将b数组剩余元素按顺序全部复制到c数组
    while(aNum == a.length && bNum < b.length){
        c[cNum++] = b[bNum++];
    }
    //如果b数组全部赋值到c数组了，但是a数组还有元素，则将a数组剩余元素按顺序全部复制到c数组
    while(bNum == b.length && aNum < a.length){
        c[cNum++] = a[aNum++];
    }
    return c;
}



public static int[] mergeSort(int[] c,int start,int last){
    if(last > start){
        //也可以是(start+last)/2，这样写是为了防止数组长度很大造成两者相加超过int范围，导致溢出
        int mid = start + (last - start)/2;
        mergeSort(c,start,mid);//左边数组排序
        mergeSort(c,mid+1,last);//右边数组排序
        merge(c,start,mid,last);//合并左右数组
    }
    return c;
}
 
public static void merge(int[] c,int start,int mid,int last){
    int[] temp = new int[last-start+1];//定义临时数组
    int i = start;//定义左边数组的下标
    int j = mid + 1;//定义右边数组的下标
    int k = 0;
    while(i <= mid && j <= last){
        if(c[i] < c[j]){
            temp[k++] = c[i++];
        }else{
            temp[k++] = c[j++];
        }
    }
    //把左边剩余数组元素移入新数组中
    while(i <= mid){
        temp[k++] = c[i++];
    }
    //把右边剩余数组元素移入到新数组中
    while(j <= last){
        temp[k++] = c[j++];
    }
     
    //把新数组中的数覆盖到c数组中
    for(int k2 = 0 ; k2 < temp.length ; k2++){
        c[k2+start] = temp[k2];
    }
}

6、消除递归

　一个算法作为一个递归的方法通常通概念上很容易理解，但是递归的使用在方法的调用和返回都会有额外的开销，通常情况下，用递归能实现的，用循环都可以实现，而且循环的效率会更高，所以在实际应用中，把递归的算法转换为非递归的算法是非常有用的。这种转换通常会使用到栈。



　　递归和栈

　　递归和栈有这紧密的联系，而且大多数编译器都是用栈来实现递归的，当调用一个方法时，编译器会把这个方法的所有参数和返回地址都压入栈中，然后把控制转移给这个方法。当这个方法返回时，这些值退栈。参数消失了，并且控制权重新回到返回地址处。

　　调用一个方法时所发生的事：

　　一、当一个方法被调用时，它的参数和返回地址被压入一个栈中；

　　二、这个方法可以通过获取栈顶元素的值来访问它的参数；

　　三、当这个方法要返回时，它查看栈以获得返回地址，然后这个地址以及方法的所有参数退栈，并且销毁。

7、递归的一些应用

①、求一个数的乘方

　　一般稍微复杂一点的计算器上面都能求一个数的乘法，通常计算器上面的标志是 x^y 这样的按键，表示求 x 的 y 次方。一般情况下我们是如何求一个数的乘法的呢？

　　比如2^8,我们可以会求表达式2*2*2*2*2*2*2*2 的值，但是如果y的值很大，这个会显得表达式很冗长。那么由没有更快一点方法呢？

　　数学公式如下是成立的：

　　(Xa)b = Xa*b

　　如果如果求28次方，我们可以先假定22=a,于是28 = （22）4 ，那么就是a4 ；假定 a2 = b，那么 a4 = b2，而b2可以写成(b2)1。于是现在28就转换成：b*b

　　也就是说我们将乘方的运算转换为乘法的运算。

　　求xy的值，当y是偶数的时候，最后能转换成两个数相乘，当时当y是奇数的时候，最后我们必须要在返回值后面额外的乘以一个x。

x^y= (x^2)^(y/2)，定义a=x^2,b=y/2, 则得到形如： x^y= a^b;

public static int pow(int x,int y){
    if(x == 0 || x == 1){
        return x;
    }
    if(y > 1){
        int b = y/2;
        int a = x*x;
        if(y%2 == 1){//y为奇数
            return pow(a,b)*x;
        }else{//y为偶数
            return pow(a,b);
        }
    }else if(y == 0){
        return 1;
    }else{//y==1
        return x;
    }
}

②、背包问题

 　　背包问题也是计算机中的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到背包中，以使得背包最后达到指定的总重量。

　　比如：假设想要让背包精确地承重20磅，并且有 5 个可以放入的数据项，它们的重量分别是 11 磅，8 磅，7 磅，6 磅，5 磅。这个问题可能对于人类来说很简单，我们大概就可以计算出 8 磅+ 7 磅 + 5 磅 = 20 磅。但是如果让计算机来解决这个问题，就需要给计算机设定详细的指令了。

　　算法如下：

　　一、如果在这个过程的任何时刻，选择的数据项的总和符合目标重量，那么工作便完成了。

　　二、从选择的第一个数据项开始，剩余的数据项的加和必须符合背包的目标重量减去第一个数据项的重量，这是一个新的目标重量。

　　三、逐个的试每种剩余数据项组合的可能性，但是注意不要去试所有的组合，因为只要数据项的和大于目标重量的时候，就停止添加数据。

　　四、如果没有合适的组合，放弃第一个数据项，并且从第二个数据项开始再重复一遍整个过程。

　　五、继续从第三个数据项开始，如此下去直到你已经试验了所有的组合，这时才知道有没有解决方案。

　　具体实现过程：

package com.ys.recursion;
 
public class Knapsack {
    private int[] weights; //可供选择的重量
    private boolean[] selects; //记录是否被选择
     
    public Knapsack(int[] weights){
        this.weights = weights;
        selects = new boolean[weights.length];
    }
     
    /**
     * 找出符合承重重量的组合
     * @param total 总重量
     * @param index 可供选择的重量下标
     */
    public void knapsack(int total,int index){
        if(total < 0 || total > 0 && index >= weights.length){
            return;//没找到解决办法，直接返回
        }
        if(total == 0){//总重量为0，则找到解决办法了
            for(int i = 0 ; i < index ; i++){
                if(selects[i] == true){
                    System.out.println(weights[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        selects[index] = true;
        knapsack(total-weights[index], index+1);
        selects[index] = false;
        knapsack(total, index+1);
    }
     
    public static void main(String[] args) {
        int array[] = {11,9,7,6,5};
        int total = 20;
        Knapsack k = new Knapsack(array);
        k.knapsack(total, 0);
    }
 
}

　③、组合：选择一支队伍

　　在数学中，组合是对事物的一种选择，而不考虑他们的顺序。

　　比如有5个登山队员，名称为 A,B,C,D和E。想要从这五个队员中选择三个队员去登峰，这时候如何列出所有的队员组合。（不考虑顺序）

　　还是以递归的思想来解决：首先这五个人的组合选择三个人分成两个部分，第一部分包含A队员，第二部分不包含A队员。假设把从 5 个人中选出 3 个人的组合简写为（5,3），规定 n 是这群人的大小，并且 k 是组队的大小。那么根据法则可以有：

　　(n,k) = (n-1,k-1) + (n-1,k)

 　　对于从 5 个人中选择 3 个人，有：

　　(5,3) = (4,2)+(4,3)

　　(4,2)表示已经有A队员了，然后从剩下的4个队员中选择2个队员，(4,3)表示从5个人中剔除A队员，从剩下的4个队员中选择3个队员，这两种情况相加就是从5个队员中选择3个队员。

　　现在已经把一个大问题转换为两个小问题了。从4个人的人群中做两次选择（一次选择2个，一次选择3个），而不是从5个人的人群中选择3个。

　　从4个人的人群中选择2个人，又可以表示为：(4,2) = (3,1) + (3,2)，以此类推，很容易想到递归的思想。

//具体代码实现
package com.ys.recursion;
 
public class Combination {
    private char[] persons;//组中所有可供选择的人员
    private boolean[] selects;//标记成员是否被选中，选中为true
     
    public Combination(char[] persons){
        this.persons = persons;
        selects = new boolean[persons.length];
    }
    public void showTeams(int teamNumber){
        combination(teamNumber,0);
    }
    /**
     *
     * @param teamNumber 需要选择的队员数
     * @param index 从第几个队员开始选择
     */
    public void combination(int teamNumber,int index){
        if(teamNumber == 0){//当teamNumber=0时，找到一组
            for(int i = 0 ; i < selects.length ; i++){
                if(selects[i] == true){
                    System.out.print(persons[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        //index超过组中人员总数，表示未找到
        if(index >= persons.length ){
            return;
        }
        selects[index] = true;
        combination(teamNumber-1, index+1);
        selects[index] = false;
        combination(teamNumber, index+1);
    }
 
    public static void main(String[] args) {
        char[] persons = {'A','B','C','D','E'};
        Combination cb = new Combination(persons);
        cb.showTeams(3);
    }
}

8、总结

一个递归方法每次都是用不同的参数值反复调用自己，当某种参数值使得递归的方法返回，而不再调用自身，这种情况称为边界值，也叫基值。当递归方法返回时，递归过程通过逐渐完成各层方法实例的未执行部分，而从最内层返回到最外层的原始调用处。

　　阶乘、汉诺塔、归并排序等都可以用递归来实现，但是要注意任何可以用递归完成的算法用栈都能实现。当我们发现递归的方法效率比较低时，可以考虑用循环或者栈来代替它。

 

树（二叉树、霍夫曼树、AVL树、2-3树、2-3-4树、B树、B+树、B*树、红黑树、）

前面我们介绍数组的数据结构，我们知道对于有序数组，查找很快，并介绍可以通过二分法查找，但是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据项全部向后移动一位，来给新数据腾出空间，平均来讲要移动N/2次，这是很费时的。同理，删除数据也是。

　　然后我们介绍了另外一种数据结构——链表，链表的插入和删除很快，我们只需要改变一些引用值就行了，但是查找数据却很慢了，因为不管我们查找什么数据，都需要从链表的第一个数据项开始，遍历到找到所需数据项为止，这个查找也是平均需要比较N/2次。

　　那么我们就希望一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是 树 诞生了。

1、树

树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。



　   ①、节点：上图的圆圈，比如A,B,C等都是表示节点。节点一般代表一些实体，在java面向对象编程中，节点一般代表对象。

　　②、边：连接节点的线称为边，边表示节点的关联关系。一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java当中通常表示引用。

　　树有很多种，向上面的一个节点有多余两个的子节点的树，称为多路树，后面会讲解2-3-4树和外部存储都是多路树的例子。而每个节点最多只能有两个子节点的一种形式称为二叉树



　　树的常用术语



        ①、路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。

　　②、根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。

　　③、父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；B是D的父节点。

　　④、子节点：一个节点含有的子树的根节点称为该节点的子节点；D是B的子节点。

　　⑤、兄弟节点：具有相同父节点的节点互称为兄弟节点；比如上图的D和E就互称为兄弟节点。

　　⑥、叶节点：没有子节点的节点称为叶节点，也叫叶子节点，比如上图的H、E、F、G都是叶子节点。

　　⑦、子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。

　　⑧、节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。

　　⑨、深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；

　　⑩、高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；





2、二叉树

二叉树：树的每个节点最多只能有两个子节点

　　上图的第一幅图B节点有DEF三个子节点，就不是二叉树，称为多路树；而第二幅图每个节点最多只有两个节点，是二叉树，并且二叉树的子节点称为“左子节点”和“右子节点”。上图的D,E分别是B的左子节点和右子节点。

　　如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。

　　二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； 它的左、右子树也分别为二叉排序树。



二叉搜索树作为一种数据结构，那么它是如何工作的呢？它查找一个节点，插入一个新节点，以及删除一个节
点，遍历树等工作效率如何，下面我们来一一介绍。

一、二叉树的节点类：
package com.ys.tree;
 
public class Node {
    private Object data;    //节点数据
    private Node leftChild; //左子节点的引用
    private Node rightChild; //右子节点的引用
    //打印节点内容
    public void display(){
        System.out.println(data);
    }
 
}
二、二叉树的具体方法
package com.ys.tree;
 
public interface Tree {
    //查找节点
    public Node find(Object key);
    //插入新节点
    public boolean insert(Object key);
    //删除节点
    public boolean delete(Object key);
    //Other Method......
}
三、查找节点
查找某个节点，我们必须从根节点开始遍历。

　　①、查找值比当前节点值大，则搜索右子树；

　　②、查找值等于当前节点值，停止搜索（终止条件）；

　　③、查找值小于当前节点值，则搜索左子树；

//查找节点
public Node find(int key) {
    Node current = root;
    while(current != null){
        if(current.data > key){//当前值比查找值大，搜索左子树
            current = current.leftChild;
        }else if(current.data < key){//当前值比查找值小，搜索右子树
            current = current.rightChild;
        }else{
            return current;
        }
    }
    return null;//遍历完整个树没找到，返回null
}
　用变量current来保存当前查找的节点，参数key是要查找的值，刚开始查找将根节点赋值到current。接在
在while循环中，将要查找的值和current保存的节点进行对比。如果key小于当前节点，则搜索当前节点的左
子节点，如果大于，则搜索右子节点，如果等于，则直接返回节点信息。当整个树遍历完全，即current == 
null，那么说明没找到查找值，返回null。

　　树的效率：查找节点的时间取决于这个节点所在的层数，每一层最多有2n-1个节点，总共N层共有2n-1个
节点，那么时间复杂度为O(logn),底数为2。

四、插入节点
要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节
点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则
插入到相应为空的位置，在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右
子树，才能插入到正确的位置。
//插入节点
public boolean insert(int data) {
    Node newNode = new Node(data);
    if(root == null){//当前树为空树，没有任何节点
        root = newNode;
        return true;
    }else{
        Node current = root;
        Node parentNode = null;
        while(current != null){
            parentNode = current;
            if(current.data > data){//当前值比插入值大，搜索左子节点
                current = current.leftChild;
                if(current == null){//左子节点为空，直接将新值插入到该节点
                    parentNode.leftChild = newNode;
                    return true;
                }
            }else{
                current = current.rightChild;
                if(current == null){//右子节点为空，直接将新值插入到该节点
                    parentNode.rightChild = newNode;
                    return true;
                }
            }
        }
    }
    return false;
}

五、树的遍历
　遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜
索树最常用的是中序遍历。

　　①、中序遍历:左子树——》根节点——》右子树

　　②、前序遍历:根节点——》左子树——》右子树

　　③、后序遍历:左子树——》右子树——》根节点
//中序遍历
public void infixOrder(Node current){
    if(current != null){
        infixOrder(current.leftChild);
        System.out.print(current.data+" ");
        infixOrder(current.rightChild);
    }
}
 
//前序遍历
public void preOrder(Node current){
    if(current != null){
        System.out.print(current.data+" ");
        preOrder(current.leftChild);
        preOrder(current.rightChild);
    }
}
 
//后序遍历
public void postOrder(Node current){
    if(current != null){
        postOrder(current.leftChild);
        postOrder(current.rightChild);
        System.out.print(current.data+" ");
    }
}

六、查找最大值和最小值
这没什么好说的，要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节
点，那么这个节点就是最小值。同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。

//找到最大值
public Node findMax(){
    Node current = root;
    Node maxNode = current;
    while(current != null){
        maxNode = current;
        current = current.rightChild;
    }
    return maxNode;
}
//找到最小值
public Node findMin(){
    Node current = root;
    Node minNode = current;
    while(current != null){
        minNode = current;
        current = current.leftChild;
    }
    return minNode;
}


七、删除节点
删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。

　　1、该节点是叶节点（没有子节点）

　　2、该节点有一个子节点

　　3、该节点有两个子节点

　　下面我们分别对这三种情况进行讲解。

　　①、删除没有子节点的节点

　　要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。要删除的节点依
然存在，但是它已经不是树的一部分了，由于Java语言的垃圾回收机制，我们不需要非得把节点本身删掉，一旦
Java意识到程序不在与该节点有关联，就会自动把它清理出存储器。



@Override
public boolean delete(int key) {
    Node current = root;
    Node parent = root;
    boolean isLeftChild = false;
    //查找删除值，找不到直接返回false
    while(current.data != key){
        parent = current;
        if(current.data > key){
            isLeftChild = true;
            current = current.leftChild;
        }else{
            isLeftChild = false;
            current = current.rightChild;
        }
        if(current == null){
            return false;
        }
    }
    //如果当前节点没有子节点
    if(current.leftChild == null && current.rightChild == null){
        if(current == root){
            root = null;
        }else if(isLeftChild){
            parent.leftChild = null;
        }else{
            parent.rightChild = null;
        }
        return true;
    }
    return false;
}
删除节点，我们要先找到该节点，并记录该节点的父节点。在检查该节点是否有子节点。如果没有子节点，接着
检查其是否是根节点，如果是根节点，只需要将其设置为null即可。如果不是根节点，是叶节点，那么断开父
节点和其的关系即可。

②、删除有一个子节点的节点
　 删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。




//当前节点有一个子节点
if(current.leftChild == null && current.rightChild != null){
    if(current == root){
        root = current.rightChild;
    }else if(isLeftChild){
        parent.leftChild = current.rightChild;
    }else{
        parent.rightChild = current.rightChild;
    }
    return true;
}else{
    //current.leftChild != null && current.rightChild == null
    if(current == root){
        root = current.leftChild;
    }else if(isLeftChild){
        parent.leftChild = current.leftChild;
    }else{
        parent.rightChild = current.leftChild;
    }
    return true;
}











public Node getSuccessor(Node delNode){
    Node successorParent = delNode;
    Node successor = delNode;
    Node current = delNode.rightChild;
    while(current != null){
        successorParent = successor;
        successor = current;
        current = current.leftChild;
    }
    //将后继节点替换删除节点
    if(successor != delNode.rightChild){
        successorParent.leftChild = successor.rightChild;
        successor.rightChild = delNode.rightChild;
    }
     
    return successor;
}
④、删除有必要吗？

 　　通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只
需要在Node类中增加一个标识字段isDelete，当该字段为true时，表示该节点已经删除，反正没有删除。那
么我们在做比如find()等操作的时候，要先判断isDelete字段是否为true。这样删除的节点并不会改变树的
结构。
public class Node {
    int data;   //节点数据
    Node leftChild; //左子节点的引用
    Node rightChild; //右子节点的引用
    boolean isDelete;//表示节点是否被删除
}

二叉树的效率

从前面的大部分对树的操作来看，都需要从根节点到下一层一层的查找。

　　一颗满树，每层节点数大概为2n-1，那么最底层的节点个数比树的其它节点数多1，因此，查找、插入或删除节点的操作大约有一半都需要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。

　　总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。

　　在有1000000 个数据项的无序数组和链表中，查找数据项平均会比较500000 次，但是在有1000000个节点的二叉树中，只需要20次或更少的比较即可。

　　有序数组可以很快的找到数据项，但是插入数据项的平均需要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项需要20次或更少比较，在加上很短的时间来连接数据项。

　　同样，从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只需要20次或更少的次数来找到他，然后在花一点时间来找到它的后继节点，一点时间来断开节点以及连接后继节点。

　　所以，树对所有常用数据结构的操作都有很高的效率。

　　遍历可能不如其他操作快，但是在大型数据库中，遍历是很少使用的操作，它更常用于程序中的辅助算法来解析算术或其它表达式。



 

3、哈夫曼树（霍夫曼树）又称为最优二叉树.

计算机里每个字符在没有压缩的文本文件中都由一个字节（如ASCII码）或两个字节（如Unicode码）表示。这些方案中，每个字符需要相同的位数

下表列出了字母对应的ASCII码

字母            十进制                二进制

A                  65                 01000001

B                  66                 01000010

C                  67                 01000011

……

X                  88                 01011000

Y                  89                 01011001

Z                  90                 01011010

在英文中，字母E的使用频率最高，而字母Z的使用频率最低，但是，无论使用频率高低，我们一律使用相同位数的编码来存储，是不是有些浪费空间呢？试想，如果我们对使用频率高的字母用较少的位数来存储，而对使用频率低的字母用较多的位数来存储，会大大提升存储效率

霍夫曼编码就是根据以上的设想来处理数据压缩的

例如，我们要发送一句消息：

SUSIE SAYS IT IS EASY

统计所有符号出现的频率：

换行符        1次

T                  1次

U                  1次

A                  2次

E                  2次

Y                  2次

I                   3次

空格            4次

S                  6次

S出现的频率最多，我们可以将它的编码设为10，其次是空格，我们将它设置为00，接下来的编码必须增加位数了。三位码我们有八种选择：000,001,010,011,100,101,110,111。但是，以10或00开头的是不能使用的，只能从010,011,110,111中选择。因为如果我们用101表示I，用010表示Y，101010既可以分解为101,010两个有意义的编码，也能分解为10,10,10三个有意义的编码，这显然是不允许的。我们必须保证，任何信息编码之后，解码时都不会出现歧义。借助霍夫曼树就能便捷的实现编码

二叉树中有一种特别的树——哈夫曼树（最优二叉树），其通过某种规则（权值）来构造出一哈夫曼二叉树，在这个二叉树中，只有叶子节点才是有效的数据节点（很重要），其他的非叶子节点是为了构造出哈夫曼而引入的！

哈夫曼编码是一个通过哈夫曼树进行的一种编码，一般情况下，以字符：‘0’与‘1’表示。编码的实现过程很简单，只要实现哈夫曼树，通过遍历哈夫曼树，规定向左子树遍历一个节点编码为“0”，向右遍历一个节点编码为“1”，结束条件就是遍历到叶子节点！因为上面说过：哈夫曼树叶子节点才是有效数据节点！

首先就需要构建一个霍夫曼树，一般利用优先级队列来构建霍夫曼树

以上面的消息为例，我们先来分析一下构建霍夫曼树的过程，下图中，if代表换行符，sp代表空格


首先，将字符按照频率插入一个优先级队列，频率越低越靠近队头，然后循环执行下面的操作：

1、取出队头的两个树

2、以它们为左右子节点构建一棵新树，新树的权值是两者之和

3、将这棵新树插入队列

直到队列中只有一棵树时，这棵树就是我们需要的霍夫曼树

接下来我们用java来实现上面的过程，代码如下：
//节点类
public class Node{
      private String key;           //树节点存储的关键字，如果是非叶子节点为空
      private int frequency;        //关键字词频
      private Node left;            //左子节点
      private Node right;           //右子节点
      private Node next;            //优先级队列中指向下一个节点的引用
     
      public Node(int fre,String str){  //构造方法1
             frequency = fre;
             key = str;
      }
      public Node(int fre){  //构造方法2
             frequency = fre;
      }
     
      public String getKey() {
             return key;
      }
      public void setKey(String key) {
             this.key = key;
      }
      public Node getLeft() {
             return left;
      }
      public void setLeft(Node left) {
             this.left = left;
      }
      public Node getRight() {
             return right;
      }
      public void setRight(Node right) {
             this.right = right;
      }
      public Node getNext() {
             return next;
      }
      public void setNext(Node next) {
             this.next = next;
      }
      public int getFrequency() {
             return frequency;
      }
      public void setFrequency(int frequency) {
             this.frequency = frequency;
      }
}


//用于辅助创建霍夫曼树的优先级队列
public class PriorityQueue{
      private Node first;
      private int length;
     
      public PriorityQueue(){
             length = 0;
             first = null;
      }
     
      //插入节点
      public void insert(Node node){
             if(first == null){  //队列为空
                    first = node;
             }else{
                    Node cur = first;
                    Node previous = null;
                    while(cur.getFrequency()< node.getFrequency()){  //定位要插入位置的前一个节点和后一个节点
                           previous = cur;
                           if(cur.getNext() ==null){  //已到达队尾
                                  cur = null;
                                  break;
                           }else{
                                  cur =cur.getNext();
                           }
                          
                    }
                    if(previous == null){  //要插入第一个节点之前
                           node.setNext(first);
                           first = node;
                    }else if(cur == null){  //要插入最后一个节点之后
                           previous.setNext(node);
                    }else{  //插入到两个节点之间
                           previous.setNext(node);
                           node.setNext(cur);
                    }
             }
             length++;
      }
     
      //删除队头元素
      public Node delete(){
             Node temp = first;
             first = first.getNext();
             length--;
             return temp;
      }
     
      //获取队列长度
      public int getLength(){
             return length;
      }
     
      //按顺序打印队列
      public void display(){
             Node cur = first;
             System.out.print("优先级队列：\t");
             while(cur != null){
                    System.out.print(cur.getKey()+":"+cur.getFrequency()+"\t");
                    cur = cur.getNext();
             }
             System.out.println();
      }
     
      //构造霍夫曼树
      public HuffmanTree buildHuffmanTree(){
             while(length > 1){
                    Node hLeft = delete();  //取出队列的第一个节点作为新节点的左子节点
                    Node hRight = delete(); //取出队列的第二个节点作为新节点的右子节点
                    //新节点的权值等于左右子节点的权值之和
                    Node hRoot = new Node(hLeft.getFrequency()+hRight.getFrequency());
                    hRoot.setLeft(hLeft);
                    hRoot.setRight(hRight);
                    insert(hRoot);
             }
             //最后队列中只剩一个节点，即为霍夫曼树的根节点
             return new HuffmanTree(first);
      }
     
}
 

import java.util.HashMap;
import java.util.Map;
//霍夫曼树类
public class HuffmanTree {
      private Node root;
      private Map codeSet = new HashMap();  //该霍夫曼树对应的字符编码集
     
      public HuffmanTree(Node root){
             this.root = root;
             buildCodeSet(root,"");  //初始化编码集
      }
     
      //生成编码集的私有方法，运用了迭代的思想
      //参数currentNode表示当前节点，参数currentCode代表当前节点对应的代码
      private void buildCodeSet(NodecurrentNode,String currentCode){
             if(currentNode.getKey() != null){
                    //霍夫曼树中，如果当前节点包含关键字，则该节点肯定是叶子节点，将该关键字和代码放入代码集
                    codeSet.put(currentNode.getKey(),currentCode);
             }else{//如果不是叶子节点，必定同时包含左右子节点，这种节点没有对应关键字
                    //转向左子节点需要将当前代码追加0
                    buildCodeSet(currentNode.getLeft(),currentCode+"0");
                    //转向右子节点需要将当前代码追加1
                    buildCodeSet(currentNode.getRight(),currentCode+"1");
             }
      }
     
      //获取编码集
      public Map getCodeSet(){
             return codeSet;
      }
     
}
//测试类
public static void main(String[] args) throws Exception{
             PriorityQueue queue = new PriorityQueue();
             Node n1 = new Node(1,"if");
             Node n2 = new Node(1,"U");
             Node n3 = new Node(1,"T");
             Node n4 = new Node(2,"Y");
             Node n5 = new Node(2,"E");
             Node n6 = new Node(2,"A");
             Node n7 = new Node(3,"I");
             Node n8 = new Node(4,"sp");
             Node n9 = new Node(5,"S");
             queue.insert(n3);
             queue.insert(n2);
             queue.insert(n1);
             queue.insert(n6);
             queue.insert(n5);
             queue.insert(n4);
             queue.insert(n7);
             queue.insert(n8);
             queue.insert(n9);
             queue.display();
            
             HuffmanTree tree =queue.buildHuffmanTree();
             Map map = tree.getCodeSet();
             Iterator it =map.entrySet().iterator();
             System.out.println("霍夫曼编码结果：");
             while(it.hasNext()){
                    Entry<String,String>entry = (Entry)it.next();
                    System.out.println(entry.getKey()+"——>"+entry.getValue());
             }
      }



可见，达到了预期的效果

秉承没有最好，只有更好的精神，我们不应该就此止步。现在我们做到的只是得到某个字符对应的霍夫曼编码，但是这个字符的词频仍然需要我们手工去统计、输入，更深入的思考一下，能不能更智能化一点，只要我们输入完整的一段消息，就能给出对应的霍夫曼编码，而且能对编码进行解码呢？

显然是可以的，先面就让我们用神奇的java语言来对上面的底层操作进行更高级的封装，来达到预期的功能

就是说，我们要利用上面已经写出的代码来封装一个编码类，这个类的一个方法接受一个字符串消息，返回霍夫曼编码，此外，还有一个解码类，接受一段完整的霍夫曼编码，返回解码后的消息内容。这实际上就是压缩与解压的模拟过程

 

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
 
//霍夫曼编码器
public class HuffmanEncoder {
      private PriorityQueue queue;       //辅助建立霍夫曼树的优先级队列
      private HuffmanTree tree;         //霍夫曼树
      private String [] message;            //以数组的形式存储消息文本
      private Map keyMap;                            //存储字符以及词频的对应关系
      private Map codeSet;                     //存储字符以及代码的对应关系
     
      public HuffmanEncoder(){
             queue = new PriorityQueue();
             keyMap = new HashMap<String,Integer>();
      }
     
      //获取指定字符串的霍夫曼编码
      public String encode(String msg){
             resolveMassage(msg);
             buildCodeSet();
             String code = "";
             for(inti=0;i<message.length;i++){//将消息文本的逐个字符翻译成霍夫曼编码
                    code =code+codeSet.get(message[i]);
             }
             return code;
      }
     
      //将一段字符串消息解析成单个字符与该字符词频的对应关系，存入Map
      private void resolveMassage(String msg){
            
             char [] chars =msg.toCharArray();  //将消息转换成字符数组
             message = new String[chars.length];
             for(int i =0;i<chars.length;i++){
                    String key = "";
                    key =chars[i]+"";  //将当前字符转换成字符串
                   
                    message [i] =  key;
                    if(keyMap.containsKey(key)){//如果Map中已存在该字符，则词频加一
                           keyMap.put(key,(Integer)keyMap.get(key)+1);
                    }else{//如果Map中没有该字符，加入Map
                           keyMap.put(key,1);
                    }
             }
      }
     
      //建立对应某段消息的代码集
      private void buildCodeSet(){
             Iterator it =keyMap.entrySet().iterator();
             while(it.hasNext()){
                    Entry entry =(Entry)it.next();
                    //用该字符和该字符的词频为参数，建立一个新的节点，插入优先级队列
                    queue.insert(new Node((Integer)entry.getValue(),(String)entry.getKey()));
             }
             queue.display();
             tree =queue.buildHuffmanTree();  //利用优先级队列生成霍夫曼树
             codeSet = tree.getCodeSet();   //获取霍夫曼树对应的代码集
      }
     
      //打印该段消息的代码集
      public void printCodeSet(){
             Iterator it =codeSet.entrySet().iterator();
             System.out.println("代码集：");
             while(it.hasNext()){
                    Entry entry =(Entry)it.next();
                    System.out.println(entry.getKey()+"——>"+entry.getValue());
             }
             System.out.println();
      }
     
      //获取该段消息的代码集
      public Map getCodeSet(){
             return codeSet;
      }
}

 
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
 
//霍夫曼解码器
public class HuffmanDecoder {
      private Map codeSet;  //代码段对应的代码集
     
      public HuffmanDecoder(Map map){
             codeSet = map;
      }
     
      //将代码段解析成消息文本
      public String decode(String code){
             String message = "";
             String key = "";
             char [] chars = code.toCharArray();
             for(int i=0;i<chars.length;i++){
                    key += chars[i];
                    if(codeSet.containsValue(key)){  //代码集中存在该段代码
                           Iterator it =codeSet.entrySet().iterator();
                           while(it.hasNext()){
                                  Entry entry = (Entry)it.next();
                                  if(entry.getValue().equals(key)){
                                         message+= entry.getKey();  //获取该段代码对应的
键值，即消息字符
                                  }
                           }
                           key ="";  //代码段变量置为0
                    }else{
                           continue;  //该段代码不能解析为文本消息，继续循环
                    }
             }
             return message;
      }
}

 
//测试类
public static void main(String[] args){
            
             String message = "chen long fei is hero !";
             HuffmanEncoder encoder = new HuffmanEncoder();
             String code =encoder.encode(message);
            
             encoder.printCodeSet();
             System.out.print("编码结果：");
             System.out.println(code);
            
             HuffmanDecoder decoder = new HuffmanDecoder(encoder.getCodeSet());
             String message2 =decoder.decode(code);
             System.out.print("解码结果：");
             System.out.println(message);
      }



树是由边和节点构成，根节点是树最顶端的节点，它没有父节点；二叉树中，最多有两个子节点；某个节点的左子树每个节点都比该节点的关键字值小，右子树的每个节点都比该节点的关键字值大，那么这种树称为二叉搜索树，其查找、插入、删除的时间复杂度都为logN；可以通过前序遍历、中序遍历、后序遍历来遍历树，前序是根节点-左子树-右子树，中序是左子树-根节点-右子树，后序是左子树-右子树-根节点；删除一个节点只需要断开指向它的引用即可；哈夫曼树是二叉树，用于数据压缩算法，最经常出现的字符编码位数最少，很少出现的字符编码位数多一些。

 

4、AVL树

AVL树由两位科学家在1962年发表的论文《An algorithm for the organization of information》当中提出，其命名来自于它的发明者G.M. Adelson-Velsky和E.M. Landis的名字缩写。

AVL树是最先发明的自平衡二叉查找树，也被称为高度平衡树。相比于二叉查找树，它的特点是：任何节点的两个子树的最大高度差为1。


上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2（以2为根节点的树的高度是3，而以8为根节点的树的高度是1）。

对于一般的二叉搜索树，其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

例如：我们按顺序将一组数据1,2,3,4,5,6分别插入到一颗空二叉查找树和AVL树中，插入的结果如下图：














java代码实现
/**
 * @author chenlongfei
 */
public class AVLTree {

	private AVLTreeNode root; // 根结点
	
	/**
	 * 插入操作的入口
	 * @author chenlongfei
	 * @param insertValue
	 */
	public void insert(long insertValue) {
		root = insert(root, insertValue);
	}

	/**
	 * 插入的地递归实现
	 * @author chenlongfei
	 * @param subTree
	 * @param insertValue
	 * @return
	 */
	private AVLTreeNode insert(AVLTreeNode subTree, long insertValue) {
		if (subTree == null) {
			return new AVLTreeNode(insertValue, null, null);
		}

		if (insertValue < subTree.value) { // 插入左子树

			subTree.left = insert(subTree.left, insertValue);
			if (unbalanceTest(subTree)) { // 插入后造成失衡
				if (insertValue < subTree.left.value) { // LL型失衡
					subTree = leftLeftRotation(subTree);
				} else { // LR型失衡
					subTree = leftRightRotation(subTree);
				}
			}

		} else if (insertValue > subTree.value) { // 插入右子树

			subTree.right = insert(subTree.right, insertValue);
			if (unbalanceTest(subTree)) { // 插入后造成失衡
				if (insertValue < subTree.right.value) { // RL型失衡
					subTree = rightLeftRotation(subTree);
				} else { // RR型失衡
					subTree = rightRightRotation(subTree);
				}
			}

		} else {
			throw new RuntimeException("duplicate value: " + insertValue);
		}

		return subTree;
	}

	/**
	 * RL型旋转
	 * @author chenlongfei
	 * @param k1 子树根节点
	 * @return
	 */
	private AVLTreeNode rightLeftRotation(AVLTreeNode k1) {
		k1.right = leftLeftRotation(k1.right);

		return rightRightRotation(k1);
	}

	/**
	 * RR型旋转
	 * @author chenlongfei
	 * @param k1 k1 子树根节点
	 * @return
	 */
	private AVLTreeNode rightRightRotation(AVLTreeNode k1) {
		AVLTreeNode k2;

		k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;

		return k2;
	}

	/**
	 * LR型旋转
	 * @author chenlongfei
	 * @param k3
	 * @return
	 */
	private AVLTreeNode leftRightRotation(AVLTreeNode k3) {
		k3.left = rightRightRotation(k3.left);

		return leftLeftRotation(k3);
	}

	/**
	 * LL型旋转
	 * @author chenlongfei
	 * @param k2
	 * @return
	 */
	private AVLTreeNode leftLeftRotation(AVLTreeNode k2) {
		AVLTreeNode k1;

		k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;

		return k1;
	}

	/**
	 * 获取树的深度
	 * @author chenlongfei
	 * @param treeRoot 根节点
	 * @param initDeep 初始深度
	 * @return
	 */
	private static int getDepth(AVLTreeNode treeRoot, int initDeep) {
		if (treeRoot == null) {
			return initDeep;
		}
		int leftDeep = initDeep;
		int rightDeep = initDeep;
		if (treeRoot.left != null) {
			leftDeep = getDepth(treeRoot.left, initDeep++);
		}
		if (treeRoot.right != null) {
			rightDeep = getDepth(treeRoot.right, initDeep++);
		}

		return Math.max(leftDeep, rightDeep);
	}

	/**
	 * 判断是否失衡
	 * @author chenlongfei
	 * @param treeRoot
	 * @return
	 */
	private boolean unbalanceTest(AVLTreeNode treeRoot) {
		int leftHeight = getDepth(treeRoot.left, 1);
		int righHeight = getDepth(treeRoot.right, 1);
		int diff = Math.abs(leftHeight - righHeight);
		return diff > 1;
	}
	
	/**
	 * 删除操作的入口
	 * @param value
	 */
	public void remove(long value) {
		root = remove(root, value);
	}
	
	/**
	 * 删除操作的递归实现
	 * @param tree
	 * @param value
	 * @return
	 */
	private AVLTreeNode remove(AVLTreeNode tree, long value) {
		if (tree == null) {
			return tree;
		}
		
		if (value < tree.value) { //要删除的节点在左子树
			
			tree.left = remove(tree.left, value);
			
		} else if (value > tree.value){  //要删除的节点在右子树
			
			tree.right = remove(tree.right, value);
			
		} else if (tree.value == value) {  //要删除的节点就是本身

			if (tree.left != null && tree.right != null) { // 左右子树都存在
				
				if (getDepth(tree.left, 1) > getDepth(tree.right, 1)) {
					/**
					 * 如果tree的左子树比右子树高: 
					 * 1. 找出tree的左子树中的最大节点 
					 * 2. 将该最大节点的值赋值给tree。 
					 * 3. 删除该最大节点。
					 * 这类似于用"tree的左子树中最大节点"做"tree"的替身 
					 * 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平
衡的
					 */
					AVLTreeNode max = getMaxNode(tree.left);
	                tree.value = max.value;
	                tree.left = remove(tree.left, max.value);
				} else {
					/**
					 * 如果tree的左子树不高于右子树: 
					 * 1. 找出tree的右子树中的最小节点 
					 * 2. 将该最小节点的值赋值给tree。 
					 * 3. 删除该最小节点。
					 * 这类似于用"tree的右子树中最小节点"做"tree"的替身
					 * 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平
衡的
					 */
					AVLTreeNode min = getMinNode(tree.right);
	                tree.value = min.value;
	                tree.right = remove(tree.right, min.value);

				}

			} else {

				tree = tree.left == null ? tree.right : tree.left;

			}
		} else {
			System.out.println("no node matched value: " + value);
		}

		return tree;
	}
	
	
	/**
	 * 获取值最大的节点
	 * @param node
	 * @return
	 */
	private AVLTreeNode getMaxNode(AVLTreeNode node) {
		if (node == null) {
			return null;
		}

		if (node.right != null) {
			return getMaxNode(node.right);
		} else {
			return node;
		}
	}
	
	/**
	 * 获取值最小的节点
	 * @param node
	 * @return
	 */
	private AVLTreeNode getMinNode(AVLTreeNode node) {
		if (node == null) {
			return null;
		}

		if (node.left != null) {
			return getMinNode(node.left);
		} else {
			return node;
		}
	}
	
	// AVL树的节点
	class AVLTreeNode {
		long value; // 节点存储的数值
		AVLTreeNode left; // 左孩子
		AVLTreeNode right; // 右孩子

		public AVLTreeNode(long value, AVLTreeNode left, AVLTreeNode right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}

		public long getValue() {
			return this.value;
		}

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

		public AVLTreeNode getLeft() {
			return this.left;
		}

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

		public AVLTreeNode getRight() {
			return this.right;
		}

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

测试代码：

		/**
	 * 前序遍历
	 * @param currentRoot
	 */
	public static void preorder(AVLTreeNode currentRoot) {
		if (currentRoot != null) {
			System.out.print(currentRoot.value + "\t");
			preorder(currentRoot.left);
			preorder(currentRoot.right);
		}
	}
	
	public static void main(String [] args) {
		AVLTree tree = new AVLTree();
		int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
		for (int a : arr) {
			tree.insert(a);
			
		}
		preorder(tree.root);
		
	}

打印结果如下：

3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9


5、2-3-4树

通过前面的介绍，我们知道在二叉树中，每个节点只有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。2-3-4树就是一种阶为4的多叉树，它像红黑树一样是平衡树，可以保证在O(lgn)的时间内完成查找、插入和删除操作，容易实现，但是效率比红黑树稍差。它是一种多叉树，它的每个节点最多有四个子节点和三个数据项。

它有如下特点：

每个节点可以保存一个、两个或者三个数据项。
	底层的六个节点都是叶节点，所有的叶节点都是在一层上的。
	非叶子节点的子节点总数总是比它含有的数据项大1
2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况：

　　①、有一个数据项的节点总是有两个子节点；

　　②、有二个数据项的节点总是有三个子节点；

　　③、有三个数据项的节点总是有四个子节点；

　　简而言之，非叶节点的子节点数总是比它含有的数据项多1。如果子节点个数为L，数据项个数为D，那么：L = D + 1



　　叶节点（上图最下面的一排）是没有子节点的，然而它可能含有一个、两个或三个数据项。空节点是不会存在的。

　　树结构中很重要的一点就是节点之间关键字值大小的关系。在二叉树中，所有关键字值比某个节点值小的节点都在这个节点左子节点为根的子树上；所有关键字值比某个节点值大的节点都在这个节点右子节点为根的子树上。2-3-4 树规则也是一样，并且还加上以下几点：

　　为了方便描述，用从0到2的数字给数据项编号，用0到3的数字给子节点编号，如下图：

  



查找特定关键字值的数据项和在二叉树中的搜索类似。从根节点开始搜索，除非查找的关键字值就是根，否则选择关键字值所在的合适范围，转向那个方向，直到找到为止。

　　比如对于下面这幅图，我们需要查找关键字值为 64 的数据项。



首先从根节点开始，根节点只有一个数据项50，没有找到，而且因为64比50大，那么转到根节点的子节点child1。60|70|80 也没有找到，而且60<64<70，所以我们还是找该节点的child1,62|64|66，我们发现其第二个数据项正好是64，于是找到了。

　　新的数据项一般要插在叶节点里，在树的最底层。如果你插入到有子节点的节点里，那么子节点的编号就要发生变化来维持树的结构，因为在2-3-4树中节点的子节点要比数据项多1。

　　插入操作有时比较简单，有时却很复杂。

　　①、当插入没有满数据项的节点时是很简单的，找到合适的位置，只需要把新数据项插入就可以了，插入可能会涉及到在一个节点中移动一个或其他两个数据项，这样在新的数据项插入后关键字值仍保持正确的顺序。如下图：



②、如果往下寻找插入位置的途中，节点已经满了，那么插入就变得复杂了。发生这种情况时，节点必须分裂，分裂能保证2-3-4树的平衡。

　　ps：这里讨论的是自顶向下的2-3-4树，因为是在向下找到插入点的路途中节点发生了分裂。把要分裂的数据项设为A,B,C，下面是节点分裂的情况（假设分裂的节点不是根节点）：

 

　　1、节点分裂

　　一、创建一个新的空节点，它是要分裂节点的兄弟，在要分裂节点的右边；

　　二、数据项C移到新节点中；

　　三、数据项B移到要分裂节点的父节点中；

　　四、数据项A保留在原来的位置；

　　五、最右边的两个子节点从要分裂处断开，连到新节点上。



上图描述了节点分裂的例子，另一种描述节点分裂的说法是4-节点变成了两个 2- 节点。节点分裂是把数据向上和向右移动，从而保持了数的平衡。一般插入只需要分裂一个节点，除非插入路径上存在不止一个满节点时，这种情况就需要多重分裂。



　　2、根的分裂

　　如果一开始查找插入节点时就碰到满的根节点，那么插入过程更复杂：

　　①、创建新的根节点，它是要分裂节点的父节点。

　　②、创建第二个新的节点，它是要分裂节点的兄弟节点；

　　③、数据项C移到新的兄弟节点中；

　　④、数据项B移到新的根节点中；

　　⑤、数据项A保留在原来的位置；

　　⑥、要分裂节点最右边的两个子节点断开连接，连到新的兄弟节点中。



注意：插入时，碰到没有满的节点时，要继续向下寻找其子节点进行插入。如果直接插入该节点，那么还要进行子节点的增加，因为在2-3-4树中节点的子节点个数要比数据项多1；如果插入的节点满了，那么就要进行节点分裂。下图是一系列插入过程，有4个节点分裂了，两个是根，两个是叶节点：



完整源码实现
分为节点类Node,表示每个节点的数据项类DataItem,以及最后的2-3-4树类Tree234.class
package com.ys.tree.twothreefour;
 
public class Tree234 {
    private Node root = new Node() ;
    /*public Tree234(){
        root = new Node();
    }*/
    //查找关键字值
    public int find(long key){
        Node curNode = root;
        int childNumber ;
        while(true){
            if((childNumber = curNode.findItem(key))!=-1){
                return childNumber;
            }else if(curNode.isLeaf()){//节点是叶节点
                return -1;
            }else{
                curNode = getNextChild(curNode,key);
            }
        }
    }
     
    public Node getNextChild(Node theNode,long theValue){
        int j;
        int numItems = theNode.getNumItems();
        for(j = 0 ; j < numItems ; j++){
            if(theValue < theNode.getItem(j).dData){
                return theNode.getChild(j);
            }
        }
        return theNode.getChild(j);
    }
     
    //插入数据项
    public void insert(long dValue){
        Node curNode = root;
        DataItem tempItem = new DataItem(dValue);
        while(true){
            if(curNode.isFull()){//如果节点满数据项了，则分裂节点
                split(curNode);
                curNode = curNode.getParent();
                curNode = getNextChild(curNode, dValue);
            }else if(curNode.isLeaf()){//当前节点是叶节点
                break;
            }else{
                curNode = getNextChild(curNode, dValue);
            }
        }//end while
        curNode.insertItem(tempItem);
    }
     
    public void split(Node thisNode){
        DataItem itemB,itemC;
        Node parent,child2,child3;
        int itemIndex;
        itemC = thisNode.removeItem();
        itemB = thisNode.removeItem();
        child2 = thisNode.disconnectChild(2);
        child3 = thisNode.disconnectChild(3);
        Node newRight = new Node();
        if(thisNode == root){//如果当前节点是根节点，执行根分裂
            root = new Node();
            parent = root;
            root.connectChild(0, thisNode);
        }else{
            parent = thisNode.getParent();
        }
        //处理父节点
        itemIndex = parent.insertItem(itemB);
        int n = parent.getNumItems();
        for(int j = n-1; j > itemIndex ; j--){
            Node temp = parent.disconnectChild(j);
            parent.connectChild(j+1, temp);
        }
        parent.connectChild(itemIndex+1, newRight);
         
        //处理新建的右节点
        newRight.insertItem(itemC);
        newRight.connectChild(0, child2);
        newRight.connectChild(1, child3);
    }
     
    //打印树节点
    public void displayTree(){
        recDisplayTree(root,0,0);
    }
    private void recDisplayTree(Node thisNode,int level,int childNumber){
        System.out.println("levle="+level+" child="+childNumber+" ");
        thisNode.displayNode();
        int numItems = thisNode.getNumItems();
        for(int j = 0; j < numItems+1 ; j++){
            Node nextNode = thisNode.getChild(j);
            if(nextNode != null){
                recDisplayTree(nextNode, level+1, j);
            }else{
                return;
            }
        }
    }
 
    //数据项
    class DataItem{
        public long dData;
        public DataItem(long dData){
            this.dData = dData;
        }
        public void displayItem(){
            System.out.println("/"+dData);
        }
    }
     
    //节点
    class Node{
        private static final int ORDER = 4;
        private int numItems;//表示该节点有多少个数据项
        private Node parent;//父节点
        private Node childArray[] = new Node[ORDER];//存储子节点的数组，最多有4个子节点
        private DataItem itemArray[] = new DataItem[ORDER-1];//存放数据项的数组，一个节点最多有三个数据项
         
        //连接子节点
        public void connectChild(int childNum,Node child){
            childArray[childNum] = child;
            if(child != null){
                child.parent = this;
            }
        }
        //断开与子节点的连接，并返回该子节点
        public Node disconnectChild(int childNum){
            Node tempNode = childArray[childNum];
            childArray[childNum] = null;
            return tempNode;
        }
        //得到节点的某个子节点
        public Node getChild(int childNum){
            return childArray[childNum];
        }
        //得到父节点
        public Node getParent(){
            return parent;
        }
        //判断是否是叶节点
        public boolean isLeaf(){
            return (childArray[0] == null)?true:false;
        }
        //得到节点数据项的个数
        public int getNumItems(){
            return numItems;
        }
        //得到节点的某个数据项
        public DataItem getItem(int index){
            return itemArray[index];
        }
        //判断节点的数据项是否满了（最多3个）
        public boolean isFull(){
            return (numItems == ORDER-1) ? true:false;
        }
         
        //找到数据项在节点中的位置
        public int findItem(long key){
            for(int j = 0 ; j < ORDER-1 ; j++){
                if(itemArray[j]==null){
                    break;
                }else if(itemArray[j].dData == key){
                    return j;
                }
            }
            return -1;
        }
         
        //将数据项插入到节点
        public int insertItem(DataItem newItem){
            numItems++;
            long newKey = newItem.dData;
            for(int j = ORDER-2 ; j >= 0 ; j--){
                if(itemArray[j] == null){//如果为空，继续向前循环
                    continue;
                }else{
                    long itsKey = itemArray[j].dData;//保存节点某个位置的数据项
                    if(newKey < itsKey){//如果比新插入的数据项大
                        itemArray[j+1] = itemArray[j];//将大数据项向后移动一位
                    }else{
                        itemArray[j+1] = newItem;//如果比新插入的数据项小，则直接插入
                        return j+1;
                    }
                }
            }
            //如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置
            itemArray[0] = newItem;
            return 0;
        }
        //移除节点的数据项
        public DataItem removeItem(){
            DataItem temp = itemArray[numItems-1];
            itemArray[numItems-1] = null;
            numItems--;
            return temp;
        }
        //打印节点的所有数据项
        public void displayNode(){
            for(int j = 0 ; j < numItems ; j++){
                itemArray[j].displayItem();
            }
            System.out.println("/");
        }
    }
 
     
}

1.1 插入

如果2-3-4树中已存在当前插入的key，则插入失败，否则最终一定是在叶子节点中进行插入操作

如果待插入的节点不是4-节点，那么直接在该节点插入

如果待插入的节点是个4-节点，那么应该先分裂该节点然后再插入。一个4-节点可以分裂成一个根节点和两个子节点（这三个节点各含一个key）然后在子节点中插入，我们把分裂形成的根节点中的key看成向上层插入的key，然后重复第2步和第3步。

如果是在4-节点中进行插入，每次插入会多出一个分支，如果插入操作导致根节点分裂，则2-3-4树会生长一层。




 





1.2 带预分裂的插入

上面的插入操作在某些情况需要不断回溯来调整树的结构以达到平衡。为了消除回溯过程，在插入操作过程中我们可以采取预分裂的操作，即我们在插入的搜索路径中，遇到4-节点就分裂（分裂后形成的根节点的key要上移，与父节点中的key合并）这样可以保证找到需要插入节点时可以直接插入（即该节点一定不是4节点）。








1.3 删除

如果2-3-4树中不存在当前需要删除的key，则删除失败。

如果当前需要删除的key不位于叶子节点上，则用后继key覆盖，然后在它后继key所在的子支中删除该后继key。

如果当前需要删除的key位于叶子节点上:

3.1 该节点不是2-节点，删除key，结束

3.2 该节点是2-节点，删除该节点：

3.2.1 如果兄弟节点不是2-节点，则父节点中的key下移到该节点，兄弟节点中的一个key上移

3.2.2 如果兄弟节点是2-节点，父节点是个3-节点或4-节点，父节点中的key与兄弟节点合并

3.2.3 如果兄弟节点是2-节点，父节点是个2-节点，父节点中的key与兄弟节点中的key合并，形成一个3-节点，把此节点看成当前节点（此节点实际上是下一层的节点），重复步骤3.2.1到3.2.3

如果是在2节点（叶子节点）中进行删除，每次删除会减少一个分支，如果删除操作导致根节点参与合并，则2-3-4树会降低一层。










1.4 带有预合并的删除

在删除过程中，我们同样可以采取预合并的操作，即我们在删除的搜索路径中（除根节点，因为根节点没有兄弟节点和父节点），遇到当前节点是2节点，如果兄弟节点也是2节点就合并（该节点的父节点中的key下移，与自身和兄弟节点合并）；如果兄弟节点不是2节点，则父节点的key下移，兄弟节点中的key上移。这样可以保证，找到需要删除的key所在的节点时可以直接删除（即要删除的key所在的节点一定不是2节点）。








 

6、2-3树



2.1 插入

如果2-3树中已存在当前插入的key，则插入失败，否则最终一定是在叶子节点中进行插入操作

如果待插入的节点只有1个key，则直接插入即可；

如果待插入的节点有2个key，则对节点进行分裂，即2个key加上待插入的key，这3个key分裂成1个key跟两个子节点，然后将分裂之后的3个key中的父节点看作向上层插入的key，然后重复第2步、第3步，直到满足2-3树的定义性质。








2.2 删除 

2-3树有4种节点：

仅1个key的叶子节点

有 2个key的叶子节点

仅1个key的非叶子节点

有2个key的非叶子节点

即 1个key与2个key的节点 和 是否为叶子节点 的组合。下面就从简单到复杂的情况开始分析：

当删除的节点是2个key的叶子节点，则将要删除的目标key删除即可，此时原来待删除的2个key的叶子节点，变成1个key的叶子节点，但是符合2-3树；

当删除的节点是2个key的非叶子节点，则此时使用中序遍历找到待删除节点的后继节点，然后将后继节点与待删除节点位置互换，此时就将问题转化为删除节点为叶子节点（平衡树的非叶子节点中序遍历后继节点肯定是叶子节点），如果该叶子是2个key，则跟情况1一样，如果该节点是只有1个key，则跟后面的情况4一样；

当删除的节点是1个key的非叶子节点，实际上操作跟情况（2）是一样的，即使用中序遍历找到待删除节点的后继节点，然后将后继节点与待删除节点位置互换，此时问题转化为删除节点为叶子节点；

当删除的节点是1个key的叶子节点，则将节点删除，此时树肯定不满足2-3树的性质，也即肯定需要调整，但要分情况来进行调整，而总结起来就是当前待删除节点的兄弟节点与父节点，分别是1个key还是2个key，即：

1).    当父节点是1个key（即此时仅有一个兄弟节点），兄弟节点是2个key，则将兄弟节点的一个key上移成父

节点，而父节点下移成子节点，也即跟2个key中插入新节点类似，拆成一父两子，此时树满足2-3树，完成调

整。

当父节点是1个key，兄弟节点也是1个key，则此时将父节点与兄弟节点合并，将合并后的节点看成当前节

点，然后重复4的判断，即判断合并后的当前节点的兄弟节点与父节点的情况，然后走对应的1)、2）、3）处

理，直到满足2-3树，完成调整。

当父节点是2个key，即此时有两个兄弟节点，而兄弟节点又可能有多种情况，穷举起来有：删除节点的位

置左中右3个，以及另外两个兄弟节点是否为1个key或2个key的4种情况，总共3*4=12种。即，

i.    若删除的是左或右节点，且中间节点只有1个key，则此时父节点的一个key下移，与中间节点合并，此    

时父节点为1个key，两个子节点，树满足2-3树，完成调整；

ii.    若删除的是左或右节点，且中间节点有2个key，则此时父节点的一个key下移，中间节点的一个key上

移与父节点合并，此时父节点为2个key，3个子节点，树满足2-3树，完成调整；

iii.    若删除的是中间节点，且右节点只有1个key，则此时父节点的一个key下移，与右节点合并，此时父节

点为1个key，两个子节点，树满足2-3树，完成调整；

iv.    若删除的是中间节点，且右节点有2个key，则此时父节点的一个key下移，右节点的一个key上移与父

节点合并，此时父节点为2个key，3个子节点，树满足2-3树，完成调整。

综述：i与ii删除左或右节点两种情况，中间节点1个key或2个key两种情况，兄弟节点1个key或2个key两种情况，总共 2x2x2=8 种；删除中间节点一种情况，iii与iv右节点1个key或2个key两种情况，左节点1个或2个key两种情况，总共 1x2x2=4 种； 4+8=12 种全齐，虽然场景有12种，但是处理的方式只有2种，一种是父节点下移与子节点合并，另一种是父节点下移成单独一个子节点，然后2个key的子节点上移一个key与父节点合并。

最简单的删除情况1，待删除的节点是2个key，直接对节点的key “5” 删除即可