关于java:Java基础篇数据结构及算法

数据结构

数据结构是计算机存储、组织数据的形式。数据结构是指相互之间存在一种或多种特定关系的数据元素的汇合。通常状况下，精心抉择的数据结构能够带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术无关。

一、定义

名词定义

数据结构是指相互之间存在着一种或多种关系的数据元素的汇合和该汇合中数据元素之间的关系组成。记为：

Data_Structure=(D,R)

其中 D 是数据元素的汇合，R 是该汇合中所有元素之间的关系的无限汇合。

其它定义

Sartaj Sahni 在他的《数据结构、算法与利用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实 例的数据元素之间的各种分割。这些分割能够通过定义相干的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的汇合”。

Clifford A.Shaffer 在《数据结构与算法剖析》一书中的定义是：“数据结构是 ADT（抽象数据类型 Abstract Data Type）的物理实现。”

Robert L.Kruse 在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成形象层、数据结构层和实现层。其中，形象层是指抽象数据类型层，它探讨数据的逻辑构造及其运算，数据结构层和实现层探讨一个数据结构的示意和在计算机内的存储细节以及运算的实现。

数据结构具体指同一类数据元素中，各元素之间的互相关系，包含三个组成成分，数据的逻辑构造，数据的存储构造和数据运算构造。

二、钻研对象

1、数据的逻辑构造：指反映数据 元素 之间的逻辑关系的 数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储地位无关。逻辑构造包含：

（1）汇合

数据结构中的元素之间除了“同属一个汇合”的互相关系外，别无其他关系；

（2）线性构造

数据结构中的元素存在一对一的互相关系；

（3）树形构造

数据结构中的元素存在一对多的互相关系；

（4）图形构造

数据结构中的元素存在多对多的互相关系。

2、数据的物理构造：指数据的 逻辑构造 在计算机存储空间的寄存模式。

数据的物理构造是数据结构在计算机中的示意（又称映像），它包含数据元素的机内示意和关系的机内示意。因为具体实现的办法有程序、链接、索引、散列等多种，所以，一种数据结构可示意成一种或多种存储构造。

数据元素的机内示意（映像办法）：用二进制位（bit）的位串示意数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因而，节点是数据元素的机内示意（或机内映像）。

关系的机内示意（映像办法）：数据元素之间的关系的机内示意能够分为程序映像和非程序映像，罕用两种存储构造：顺序存储构造和链式存储构造。程序映像借助元素在存储器中的绝对地位来示意数据元素之间的逻辑关系。非程序映像借助批示元素存储地位的指针（pointer）来示意数据元素之间的逻辑关系。

3、数据结构的运算。

三、重要意义

个别认为，一个数据结构是由数据元素根据某种逻辑联系组织起来的。对数据元素间逻辑关系的形容称为数据的逻辑构造；数据必须在计算机内存储，数据的存储构造是数据结构的实现模式，是其在计算机内的示意；此外探讨一个数据结构必须同时探讨在该类数据上执行的运算才有意义。一个逻辑数据结构能够有多种存储构造，且各种存储构造影响数据处理的效率。

在许多类型的程序的设计中，数据结构的抉择是一个根本的设计思考因素。许多大型零碎的结构教训表明，零碎实现的艰难水平和零碎结构的品质都重大的依赖于是否抉择了最优的数据结构。许多时候，确定了数据结构后，算法就容易失去了。有些时候事件也会反过来，咱们依据特定算法来抉择数据结构与之适应。不管哪种状况，抉择适合的数据结构都是十分重要的。

抉择了数据结构，算法也随之确定，是数据而不是算法是零碎结构的关键因素。这种洞见导致了许多种软件设计办法和程序设计语言的呈现，面向对象的程序设计语言就是其中之一。

四、钻研内容

在计算机科学中，数据结构是一门钻研非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保通过这些运算后所失去的新构造依然是原来的构造类型。

“数据结构”作为一门独立的课程在国外是从 1968 年才开始设立的。1968 年美国唐纳德·克努特（Donald Ervin Knuth）传授创始了数据结构的最后体系，他所著的《计算机程序设计艺术》第一卷《根本算法》是第一本较系统地论述数据的逻辑构造和存储构造及其操作的著述。“数据结构”在计算机科学中是一门综合性的业余基础课，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门外围课程。数据结构这一门课的内容不仅是个别程序设计（特地是非数值性程序设计）的根底，而且是设计和实现编译程序、操作系统、数据库系统及其他零碎程序的重要根底。

计算机科学是一门钻研用计算机进行信息示意和解决的迷信。这外面波及到两个问题：信息的示意，信息的解决。

而信息的示意和组织又间接关系到解决信息的程序的效率。随着计算机的遍及，信息量的减少，信息范畴的拓宽，使许多零碎程序和应用程序的规模很大，构造又相当简单。因而，为了编写出一个“好”的程序，必须剖析待处理的对象的特色及各对象之间存在的关系，这就是数据结构这门课所要钻研的问题。家喻户晓，计算机的程序是对信息进行加工解决。在大多数状况下，这些信息并不是没有组织，信息（数据）之间往往具备重要的构造关系，这就是数据结构的内容。数据的构造，间接影响算法的抉择和效率。

计算机解决一个具体问题时，大抵须要通过下列几个步骤：首先要从具体问题中形象出一个适当的数学模型，而后设计一个解此数学模型的算法（Algorithm），最初编出程序、进行测试、调整直至失去最终解答。

寻求数学模型的本质是剖析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，而后用数学的语言加以形容。当人们用计算机解决数值计算问题时，所用的数学模型是用数学方程形容。所波及的运算对象个别是简略的整形、实型和逻辑型数据，因而程序设计者的次要精力集中于程序设计技巧上，而不是数据的存储和组织上。然而，计算机利用的更多畛域是“非数值型计算问题”，它们的数学模型无奈用数学方程形容，而是用数据结构形容，解决此类问题的要害是设计出适合的数据结构，形容非数值型问题的数学模型是用线性表、树、图等构造来形容的。

计算机算法与数据的构造密切相关，算法无不依附于具体的数据结构，数据结构间接关系到算法的抉择和效率。运算是由计算机来实现，这就要设计相应的插入、删除和批改的算法。也就是说，数据结构还须要给出每种构造类型所定义的各种运算的算法。

数据是信息的载体，是能够被计算机辨认存储并加工解决的形容客观事物的信息符号的总称。所有能被输出计算机中，且能被计算机解决的符号的汇合，它是计算机程序加工解决的对象。客观事物包含数值、字符、声音、图形、图像等，它们自身并不是数据，只有通过编码变成能被计算机辨认、存储和解决的符号模式后才是数据。

数据元素是数据的根本单位，在计算机程序中通常作为一个整体思考。一个数据元素由若干个数据项组成。数据项是数据结构中探讨的最小单位。有两类数据元素：若数据元素可再分，则每一个独立的处理单元就是数据项，数据元素是数据项的汇合；若数据元素不可再分，则数据元素和数据项是同一概念，如：整数 ”5″，字符 “N” 等。例如形容一个学生的信息的数据元素可由下列 6 个数据项组成。其中的出生日期又能够由三个数据项：” 年 ”、” 月 ” 和 ” 日 ” 组成，则称 ” 出生日期 ” 为组合项，而其它不可分割的数据项为原子项。

关键字指的是能辨认一个或多个数据元素的数据项。若能起惟一辨认作用，则称之为 “ 主 ” 关键字，否则称之为 “ 次 ” 关键字。

数据对象是性质雷同的数据元素的汇合，是数据的一个子集。数据对象能够是无限的，也能够是有限的。

数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简略计算等的操作过程。在晚期，计算机次要用于迷信和工程计算，进入八十年代当前，计算机次要用于数据处理。据无关统计资料表明，计算机用于数据处理的工夫比例达到 80% 以上，随着工夫的推移和计算机利用的进一步遍及，计算机用于数据处理的工夫比例必将进一步增大。

五、构造分类

数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构别离为逻辑构造、存储构造（物理构造）和数据的运算。数据的逻辑构造是从具体问题形象进去的数学模型，是形容数据元素及其关系的数学个性的，有时就把逻辑构造简称为数据结构。逻辑构造是在计算机存储中的映像，模式地定义为（K，R）（或（D，S）），其中，K 是数据元素的无限集，R 是 K 上的关系的无限集。

依据数据元素间关系的不同个性，通常有下列四类根本的构造：⑴汇合构造。该构造的数据元素间的关系是“属于同一个汇合”。⑵线性构造。该构造的数据元素之间存在着一对一的关系。⑶树型构造。该构造的数据元素之间存在着一对多的关系。⑷图形构造。该构造的数据元素之间存在着多对多的关系，也称网状结构。从下面所介绍的数据结构的概念中能够晓得，一个数据结构有两个因素。一个是数据元素的汇合，另一个是关系的汇合。在模式上，数据结构通常能够采纳一个二元组来示意。

数据结构的模式定义为：数据结构是一个二元组：Data_Structure=（D，R），其中，D 是数据元素的无限集，R 是 D 上关系的无限集。线性构造的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是雷同的，或者说线性表是由同一类型的数据元素形成的线性构造。在理论问题中线性表的例子是很多的，如学生状况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。

线性表是最简略、最根本、也是最罕用的一种线性构造。线性表是具备雷同数据类型的 n(n>=0)个数据元素的无限序列，通常记为：(a1，a2，… ai-1，ai，ai+1，…an)，其中 n 为表长，n=0 时称为空表。它有两种存储办法：顺序存储和链式存储，它的次要基本操作是插入、删除和检索等。

数据结构在计算机中的示意（映像）称为数据的物理（存储）构造。它包含数据元素的示意和关系的示意。数据元素之间的关系有两种不同的示意办法：程序映象和非程序映象，并由此失去两种不同的存储构造：顺序存储构造和链式存储构造。

顺序存储办法：它是把逻辑上相邻的结点存储在物理地位相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此失去的存储示意称为顺序存储构造。顺序存储构造是一种最根本的存储示意办法，通常借助于程序设计语言中的数组来实现。

链接存储办法：它不要求逻辑上相邻的结点在物理地位上亦相邻，结点间的逻辑关系是由附加的指针字段示意的。由此失去的存储示意称为链式存储构造，链式存储构造通常借助于程序设计语言中的指针类型来实现。

索引存储办法：除建设存储结点信息外，还建设附加的索引表来标识结点的地址。

散列存储办法：就是依据结点的关键字间接计算出该结点的存储地址。

数据结构中，逻辑上（逻辑构造：数据元素之间的逻辑关系）能够把数据结构分成线性构造和非线性构造。线性构造的顺序存储构造是一种程序存取的存储构造，线性表的链式存储构造是一种随机存取的存储构造。线性表若采纳链式存储示意时所有结点之间的存储单元地址可间断可不间断。逻辑构造与数据元素自身的模式、内容、绝对地位、所含结点个数都无关。

六、构造算法

算法的设计取决于数据（逻辑）构造，而算法的实现依赖于采纳的存储构造。数据的存储构造本质上是它的逻辑构造在计算机存储器中的实现，为了全面的反映一个数据的逻辑构造，它在存储器中的映象包含两方面内容，即数据元素之间的信息和数据元素之间的关系。不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑构造上定义的操作算法，如检索、插入、删除、更新和排序等。

数据的运算是数据结构的一个重要方面，探讨任一种数据结构时都离不开对该构造上的数据运算及其实现算法的探讨。

数据结构不同于数据类型，也不同于数据对象，它不仅要形容数据类型的数据对象，而且要形容数据对象各元素之间的互相关系。

数据类型是一个值的汇合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、构造类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型显著或隐含地规定了数据的取值范畴、存储形式以及容许进行的运算。能够认为，数据类型是在程序设计中曾经实现了的数据结构。另一方面，在程序设计过程中，当须要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来形容数据的存储构造。

计算机中示意数据的最小单位是二进制数的一位，叫做位。咱们用一个由若干位组合起来造成的一个位串示意一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。元素或结点可看成是数据元素在计算机中的映象。

一个软件系统框架应建设在数据之上，而不是建设在操作之上。一个含抽象数据类型的软件模块应蕴含定义、示意、实现三个局部。

对每一个数据结构而言，必然存在与它密切相关的一组操作。若操作的品种和数目不同，即便逻辑构造雷同，数据结构能起的作用也不同。

不同的数据结构其操作集不同，但下列操作必不可缺：

（1）构造的生成；

（2）构造的销毁；

（3）在构造中查找满足规定条件的数据元素；

（4）在构造中插入新的数据元素；

（5）删除构造中曾经存在的数据元素；

（6）遍历。

抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑构造以及在此构造上的一组算法。抽象数据类型可用以下三元组示意：（D，S，P）。D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。ADT 的定义为：

ADT 抽象数据类型名：{数据对象：（数据元素汇合），数据关系：（数据关系二元组联合），基本操作：（操作函数的列举）}；ADT 抽象数据类型名; 抽象数据类型有两个重要个性：

数据抽象

用 ADT 形容程序处理的实体时，强调的是其本质的特色、其所能实现的性能以及它和内部用户的接口（即外界应用它的办法）。

数据封装

将实体的内部个性和其外部实现细节拆散，并且对外部用户暗藏其外部实现细节。

数据（Data）是信息的载体，它可能被计算机辨认、存储和加工解决。它是计算机程序加工的原料，利用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工解决的对象，它能够是数值数据，也能够是非数值数据。数值数据是一些整数、实数或复数，次要用于工程计算、科学计算和商务解决等；非数值数据包含字符、文字、图形、图像、语音等。数据元素（Data Element）是数据的根本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索零碎中学生信息表中的一个记录等，都被称为一个数据元素。

有时，一个数据元素可由若干个数据项（Data Item）组成，例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包含学生的学号、姓名、性别、籍贯、出生年月、问题等数据项。这些数据项能够分为两种：一种叫做高等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再宰割的最小单位；另一种叫做组合项，如学生的问题，它能够再划分为数学、物理、化学等更小的项。通常，在解决理论利用问题时是把每个学生记录当作一个根本单位进行拜访和解决的。

数据对象（Data Object）或数据元素类（Data Element Class）是具备雷同性质的数据元素的汇合。在某个具体问题中，数据元素都具备雷同的性质（元素值不肯定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通征询零碎的交通网中，所有的顶点是一个数据元素类，顶点 A 和顶点 B 各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值别离为 A 和 B。数据结构（Data Structure）是指相互之间存在着一种或多种关系的数据元素的汇合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为构造。

一、线性表

线性表是最罕用且最简略的一种数据结构，它是 n 个数据元素的无限序列。

实现线性表的形式个别有两种，一种是应用数组存储线性表的元素，即用一组间断的存储单元顺次存储线性表的数据元素。另一种是应用链表存储线性表的元素，即用一组任意的存储单元存储线性表的数据元素（存储单元能够是间断的，也能够是不间断的）。

数组实现

数组是一种大小固定的数据结构，对线性表的所有操作都能够通过数组来实现。尽管数组一旦创立之后，它的大小就无奈扭转了，然而当数组不能再存储线性表中的新元素时，咱们能够创立一个新的大的数组来替换以后数组。这样就能够应用数组实现动静的数据结构。

• 代码 1 创立一个更大的数组来替换以后数组

int[] oldArray = new int[10];

int[] newArray = new int[20];

for (int i = 0; i < oldArray.length; i++) {newArray[i] = oldArray[i];
}

// 也能够应用 System.arraycopy 办法来实现数组间的复制     
// System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);

oldArray = newArray;

• 代码 2 在数组地位 index 上增加元素 e

//oldArray 示意以后存储元素的数组
//size 示意以后元素个数
public void add(int index, int e) {if (index > size || index < 0) {System.out.println("地位不非法...");
    }

    // 如果数组曾经满了 就扩容
    if (size >= oldArray.length) {// 扩容函数可参考代码 1}

    for (int i = size - 1; i >= index; i--) {oldArray[i + 1] = oldArray[i];
    }

    // 将数组 elementData 从地位 index 的所有元素往后移一位
    // System.arraycopy(oldArray, index, oldArray, index + 1,size - index);

    oldArray[index] = e;

    size++;
}

下面简略写出了数组实现线性表的两个典型函数，具体咱们能够参考 Java 外面的 ArrayList 汇合类的源码。数组实现的线性表长处在于能够通过下标来拜访或者批改元素，比拟高效，次要毛病在于插入和删除的破费开销较大，比方当在第一个地位前插入一个元素，那么首先要把所有的元素往后挪动一个地位。为了进步在任意地位增加或者删除元素的效率，能够采纳链式构造来实现线性表。

链表

链表是一种物理存储单元上非间断、非程序的存储构造，数据元素的逻辑程序是通过链表中的指针链接秩序实现的。链表由一系列节点组成，这些节点不用在内存中相连。每个节点由数据局部 Data 和链局部 Next，Next 指向下一个节点，这样当增加或者删除时，只须要扭转相干节点的 Next 的指向，效率很高。

还有很多像获取指定元素，移除元素等操作大家能够本人实现，写这些代码的时候肯定要理清节点之间关系，这样才不容易出错。

链表的实现还有其它的形式，常见的有循环单链表，双向链表，循环双向链表。循环单链表  次要是链表的最初一个节点指向第一个节点，整体形成一个链环。 双向链表 次要是节点中蕴含两个指针局部，一个指向前驱元，一个指向后继元，JDK 中 LinkedList 汇合类的实现就是双向链表。 循环双向链表 是最初一个节点指向第一个节点。

二、栈与队列

栈和队列也是比拟常见的数据结构，它们是比拟非凡的线性表，因为对于栈来说，拜访、插入和删除元素只能在栈顶进行，对于队列来说，元素只能从队列尾插入，从队列头拜访和删除。

栈

栈是限度插入和删除只能在一个地位上进行的表，该地位是表的末端，叫作栈顶，对栈的基本操作有 push(进栈)和 pop(出栈)，前者相当于插入，后者相当于删除最初一个元素。栈有时又叫作 LIFO(Last In First Out)表，即后进先出。

因为栈也是一个表，所以任何实现表的办法都能实现栈。咱们关上 JDK 中的类 Stack 的源码，能够看到它就是继承类 Vector 的。当然，Stack 是 Java2 前的容器类，当初咱们能够应用 LinkedList 来进行栈的所有操作。

队列

队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

常见操作
q.push(item)
q.pop()
q.front()
q.back()
q.size()
q.empty()

• 实现队列类

# include<queue>

// 应用 push
queue<string> q;
q.push("Hello World");
q.push("hhh");

// 应用 size
q.size()   // 返回 2

// 应用 front
q.front() // 返回 "Hello World!''

一般的队列是一种先进先出的数据结构，而优先队列中，元素都被赋予优先级。当拜访元素的时候，具备最高优先级的元素最先被删除。优先队列在生活中的利用还是比拟多的，比方医院的急症室为病人赋予优先级，具备最高优先级的病人最先失去医治。在 Java 汇合框架中，类 PriorityQueue 就是优先队列的实现类，具体大家能够去浏览源码。

三、树与二叉树

树型构造是一类十分重要的非线性数据结构，其中以树和二叉树最为罕用。在介绍二叉树之前，咱们先简略理解一下树的相干内容。

树

树 是由 n（n>=1）个无限节点组成一个具备档次关系的汇合。它具备以下特点：每个节点有零个或多个子节点；没有父节点的节点称为  根  节点；每一个非根节点有且只有一个 父节点 ；除了根节点外，每个子节点能够分为多个不相交的子树。

二叉树基本概念

• 定义

二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

二叉树：是 N（N>=0）个结点的无限汇合，该汇合或为空集（空二叉树），或者由一个根结点和两颗互不相交的、别离称为根结点的左子树和右子树的二叉树组成。

满二叉树：所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上

齐全二叉树：对一棵具备 n 个结点的二叉树按层序编号，如果编号 i（1<= i <= n）的结点与同样深度的满二叉树中的编号 i 的结点在二叉树的地位完全相同，则这棵二叉树称为齐全二叉树

二叉树的特点：

1. 每个结点最多只有两颗子树
2. 左右子树是有程序的
3. 即便某结点只有一颗子树，也要辨别是右子树还是左子树

二叉树的性质：

1. 在二叉树的第 i 层上至少有 2 i − 1 2^{i-1}2i−1 个结点（i>=1）
2. 深度为 k 的二叉树至少有 2 k 2^{k}2k- 1 个结点(k>=1)
3. 对任何一棵二叉树 T，如果其终端结点数为 n 0 n_{0}n0​，此二叉树至少有 2 k 2^{k}2k- 1 个结点
4. 具备 n 个结点的齐全二叉树的深度为 [l o g 2 log_{2}log2​n]+1([x] 示意不大于 x 的最大整数）
5. n 个结点的齐全二叉树按层序编号（参考上图），对任意一个结点 i 有：
   a. 如果 i =1, 则 i 是二叉树的根，如果 i >1, 其双亲是[i/2]
   b. 如果 2i>n，则结点 i 无左孩子
   c. 如果 2i+1>n，则结点 i 无右孩子（否则其右孩子为 2i+1）

• 三种遍历办法

在二叉树的一些利用中，经常要求在树中查找具备某种特色的节点，或者对树中全副节点进行某种解决，这就波及到二叉树的遍历。二叉树次要是由 3 个根本单元组成，根节点、左子树和右子树。如果限定先左后右，那么依据这三个局部遍历的程序不同，能够分为先序遍历、中序遍历和后续遍历三种。

(1) 先序遍历  若二叉树为空，则空操作，否则先拜访根节点，再先序遍历左子树，最初先序遍历右子树。(2)  中序遍历  若二叉树为空，则空操作，否则先中序遍历左子树，再拜访根节点，最初中序遍历右子树。(3)  后序遍历 若二叉树为空，则空操作，否则先后序遍历左子树拜访根节点，再后序遍历右子树，最初拜访根节点。

• 树和二叉树的区别

(1) 二叉树每个节点最多有 2 个子节点，树则无限度。(2) 二叉树中节点的子树分为左子树和右子树，即便某节点只有一棵子树，也要指明该子树是左子树还是右子树，即二叉树是有序的。(3) 树决不能为空，它至多有一个节点，而一棵二叉树能够是空的。

下面咱们次要对二叉树的相干概念进行了介绍，上面咱们将从二叉查找树开始，介绍二叉树的几种常见类型，同时将之前的实践局部用代码实现进去。

二叉查找树

• 定义

二叉查找树就是二叉排序树，也叫二叉搜寻树。二叉查找树或者是一棵空树，或者是具备下列性质的二叉树：(1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2) 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3) 左、右子树也别离为二叉排序树；(4) 没有键值相等的结点。

• 性能剖析

对于二叉查找树来说，当给定值雷同但程序不同时，所构建的二叉查找树状态是不同的，上面看一个例子。

能够看到，含有 n 个节点的二叉查找树的均匀查找长度和树的状态无关。最坏状况下，当先后插入的关键字有序时，形成的二叉查找树变质为单支树，树的深度为 n，其均匀查找长度 (n+1)/2(和程序查找雷同），最好的状况是二叉查找树的状态和折半查找的断定树雷同，其均匀查找长度和 log2(n) 成正比。均匀状况下，二叉查找树的均匀查找长度和 logn 是等数量级的，所以为了取得更好的性能，通常在二叉查找树的构建过程须要进行“均衡化解决”，之后咱们将介绍均衡二叉树和红黑树，这些均能够使查找树的高度为 O(log(n))。

下面的代码 15 次要展现了一个本人实现的简略的二叉查找树，其中包含了几个常见的操作，当然更多的操作还是须要大家本人去实现。因为在二叉查找树中删除节点的操作比较复杂，所以上面我具体介绍一下这里。

• 二叉查找树中删除节点剖析

要在二叉查找树中删除一个元素，首先须要定位蕴含该元素的节点，以及它的父节点。假如 current 指向二叉查找树中蕴含该元素的节点，而 parent 指向 current 节点的父节点，current 节点可能是 parent 节点的左孩子，也可能是右孩子。这里须要思考两种状况：

1. current 节点没有左孩子，那么只须要将 patent 节点和 current 节点的右孩子相连。
2. current 节点有一个左孩子，假如 rightMost 指向蕴含 current 节点的左子树中最大元素的节点，而 parentOfRightMost 指向 rightMost 节点的父节点。那么先应用 rightMost 节点中的元素值替换 current 节点中的元素值，将 parentOfRightMost 节点和 rightMost 节点的左孩子相连，而后删除 rightMost 节点。

    // 二叉搜寻树删除节点
    public boolean delete(E e) {

        TreeNode<E> parent = null;
        TreeNode<E> current = root;

        // 找到要删除的节点的地位
        while (current != null) {if (e.compareTo(current.element) < 0) {
                parent = current;
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                parent = current;
                current = current.right;
            } else {break;}
        }

        // 没找到要删除的节点
        if (current == null) {return false;}

        // 思考第一种状况
        if (current.left == null) {if (parent == null) {root = current.right;} else {if (e.compareTo(parent.element) < 0) {parent.left = current.right;} else {parent.right = current.right;}
            }
        } else { // 思考第二种状况
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;
            // 找到左子树中最大的元素节点
            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }

            // 替换
            current.element = rightMost.element;

            // parentOfRightMost 和 rightMost 左孩子相连
            if (parentOfRightMost.right == rightMost) {parentOfRightMost.right = rightMost.left;} else {parentOfRightMost.left = rightMost.left;}
        }

        return true;
    }

均衡二叉树

均衡二叉树又称 AVL 树，它或者是一棵空树，或者是具备下列性质的二叉树：它的左子树和右子树都是均衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。

AVL 树是最先创造的自均衡二叉查找树算法。在 AVL 中任何节点的两个儿子子树的高度最大差异为 1，所以它也被称为高度均衡树，n 个结点的 AVL 树最大深度约 1.44log2n。查找、插入和删除在均匀和最坏状况下都是 O（log n）。减少和删除可能须要通过一次或屡次树旋转来从新均衡这个树。

红黑树

红黑树是均衡二叉树的一种，它保障在最坏状况下根本动静汇合操作的事件复杂度为 O(log n)。红黑树和均衡二叉树区别如下：(1) 红黑树放弃了谋求齐全均衡，谋求大抵均衡，在与均衡二叉树的工夫复杂度相差不大的状况下，保障每次插入最多只须要三次旋转就能达到均衡，实现起来也更为简略。(2) 均衡二叉树谋求相对均衡，条件比拟刻薄，实现起来比拟麻烦，每次插入新节点之后须要旋转的次数不能预知。

四、图

• 简介

图是一种较线性表和树更为简单的数据结构，在线性表中，数据元素之间仅有线性关系，在树形构造中，数据元素之间有着显著的档次关系，而在图形构造中，节点之间的关系能够是任意的，图中任意两个数据元素之间都可能相干。图的利用相当宽泛，特地是近年来的迅速倒退，曾经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其余分支中。

算法

算法（Algorithm）是指解题计划的精确而残缺的形容，是一系列解决问题的清晰指令，算法代表着用零碎的办法形容解决问题的策略机制。也就是说，可能对肯定标准的输出，在无限工夫内取得所要求的输入。如果一个算法有缺点，或不适宜于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的工夫、空间或效率来实现同样的工作。一个算法的优劣能够用空间复杂度与工夫复杂度来掂量。

算法中的指令形容的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输出开始，通过一系列无限而清晰定义的状态，最终产生输入并进行于一个终态。一个状态到另一个状态的转移不肯定是确定的。随机化算法在内的一些算法，蕴含了一些随机输出。

形式化算法的概念局部源自尝试解决希尔伯特提出的断定问题，并在其后尝试定义无效计算性或者无效办法中成形。这些尝试包含库尔特·哥德尔、Jacques Herbrand 和斯蒂芬·科尔·克莱尼别离于 1930 年、1934 年和 1935 年提出的递归函数，阿隆佐·邱奇于 1936 年提出的 λ 演算，1936 年 Emil Leon Post 的 Formulation 1 和艾伦·图灵 1937 年提出的图灵机。即便在以后，仍然常有直觉想法难以定义为形式化算法的状况。