数据结构与算法 java,Java数据结构算法

　　本文为大家带来一些java的知识，包括java代码实现、注释分析、算法分析等相关问题。希望对你有帮助。

　　如何解决写爬虫IP受阻的问题？立即使用。

第1章 数据结构与算法基础概述

1.1 数据结构和算法的重要性

　　算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算

　　数据结构和算法的关系:

　　程序=数据结构算法数据结构是算法的基础。换句话说，要想学好算法，就需要适当学习数据结构。数据结构和算法学习大纲

1.2 数据结构概述

　　数据结构可以简单理解为数据之间的一些关系。数据结构可以分为数据存储结构和数据逻辑结构。

逻辑结构

　　集合结构:数据元素属于同一个集合，并且是平行关系，没有其他关系；可以理解为中学学习的集合。在一个范围内，有许多元素，它们之间没有关系。线性结构:元素之间是一一对应的关系；可以理解为每个学生对应一个学号，学号和姓名是线性结构树形结构:元素之间是一对多的关系，可以简单理解为同一个家谱，代与代之间是多对多的关系图形结构:每个元素可以对应或者可以对应多个元素。网络图

存储结构

　　010-10顺序存储结构:没有按顺序存储。最后一个进来的号码只需要把它的地址告诉前一个节点，后面的号码的地址存储在前一个节点，所以最后一个号码的存储地址为空；这个结构可以比喻成商场叫饭，上面的数字可以比喻成地址。后面可以说地址是什么，上面其他内容都是节点的内容；链式存储结构:顺序存储的特点是快速查询，慢链存储的特点是慢速查询和快速插入或删除

1.3 算法概述

　　同一个问题的不同解法以时间和空间复杂度来判断算法的优劣。没有最好的算法，只有最合适的。学习算法是积累学习思路，掌握学习思路，而不是为了解决一个问题去死记硬背某些算法；至于时间复杂度和空间复杂度，在大多数开发情况下，我们现在都是用空间换时间，消耗更多的内存来保证更快的速度。区别:

如何理解“大O记法”

　　虽然详细分析算法是好的，但在实践中的实用价值有限。对于算法的时空属性，最重要的是它的大小和趋势，这是分析算法效率的主要部分。然而，测量算法的基本操作数的尺度函数中的那些常数因子可以忽略。例如，可以认为3n^2和100n^2属于同一数量级。如果两种算法处理相同规模实例的代价分别是这两个函数，则认为它们的效率“差不多”，都是n 2。

时间复杂度

　　算法花费的时间与算法中语句的执行时间成正比。哪个算法的语句多，需要的时间就多。算法中执行的语句数称为语句频率或时间频率，记为T(n)。n称为问题的尺度，当n不断变化时，时间频率T(n)也会不断变化。但有时我们想知道它变化时表现出什么规律。因此，我们引入各排序算法复杂度及稳定性的概念。

　　算法中基本运算重复的次数一般是问题规模n的函数，用T(n)表示。如果有一个辅助函数f(n)使得T(n)/f(n)的极限值在n接近最大值时是一个不等于零的常数，那么称f(n)为T(n)的时间复杂度0。设T(n)=O(f(n))，调用算法的O(f(n))同数量级函数，简称渐进时间复杂度。

　　有时，算法中基本运算的重复次数会随着问题的输入数据集而变化。比如冒泡排序，输入数据有序和无序，结果都不一样。此时，我们计算平均值。

　　时间复杂度:

　　运算是基本的，即只有常数项，其时间复杂度被认为是O(1)序列结构。时间复杂度按照时间复杂度基本计算规则循环结构计算，时间复杂度按照加法分支结构计算，时间复杂度为乘法。在判断一个算法的效率时，往往只需要关注运算次数最高的一项，其他的二级项和常数项可以忽略。除非另有说明，否则可以忽略。

　　注意：log2n(以2为底的对数)通常缩写为logn取最大值:

　　最坏时间复杂度:o(1)o(log n)o(n)o(nlog n)o(n^2)o(2^n)o(n！)O(n^n)常用时间复杂度:

　　count=0；(1)

　　for(I=0；I=n；(2)

　　for(j=0；j=n；j ) (3)

　　数数；(4)语句(1)执行一条语句(2)执行n条语句(3)执行n ^ 2条语句(4)执行n ^ 2次常见时间复杂度之间的关系:t(n)=1n ^ 2n ^ 2=o(n ^ 2)所以时间消耗由小到大为:

　　a=1；(1)

　　b=2；(2)

　　for(int I=1；I=n；我){ (3)

　　int s=a b；(4)

　　b=a；(5)

　　a=s；(6)

　　}语句(1)、(2)执行语句一次(3)执行语句n次(4)、(5)、(6)执行语句n次案例1:t(n)=14n=o(n)时间复杂度为:

　　I=1；(1)while(在){

　　I=I * 2；(2)}语句(1)的频率为1。设语句(2)的频率为f(n)，则2f(n)=n；F(n)=log2n，取最大值F(n)=log2n案例2:t(n)=o(log2n)

空间复杂度

　　算法空间复杂度的计算公式：S(n)=0( f(n))，其中n为输入尺度，f(n)

　　一个算法在计算机内存中占用的存储空间包括三个方面。

　　算法本身占用的存储空间算法输入输出数据占用的存储空间算法运行时占用的临时存储空间时间复杂度为:对指定数组进行反转，返回反转后的内容。

　　解决方案1:

　　public static int[]reverse 1(int[]arr){

　　int n=arr.length//申请4个字节

　　内部温度；//申请4个字节

　　for (int start=0，end=n-1；开始=结束；开始，结束- ) {

　　temp=arr[start]；

　　arr[start]=arr[end]；

　　arr[end]=temp；

　　}

　　返回arr}案例3: S (n)=4 4=O (8)=O (1)解2:

　　public static int[]reverse 2(int[]arr){

　　int n=arr.length//申请4个字节

　　int[]temp=new int[n]；//应用程序n*4字节数组本身的头信息需要24个字节。

　　for(int I=n-1；I=0；我- ) {

　　temp[n-1-I]=arr[I]；

　　}

　　返回温度；}时间复杂度为:S(n)=44n 24=O(n ^ 28)=O(n)根据大O求导法则，第一种算法的空间复杂度为0(1)，第二种算法的空间复杂度为0(n)，因此第一种算法在空间占用上优于第二种算法。

　　因为java中有垃圾收集机制，jvm对程序的内存占用进行了优化(比如即时编译)，所以我们无法准确评估一个java程序的内存占用情况，但是知道java的基本内存占用情况使我们能够估计java程序的内存占用情况。

　　由于现在的电脑设备内存普遍较大，基本上个人电脑都是4G起步，大的能达到32G，所以内存占用一般不是我们算法的瓶颈，案例。

　　但是如果你做的程序是嵌入式开发，尤其是一些传感器设备上的内置程序，因为这些设备的内存很小，一般也就几kb，此时对算法的空间复杂度就有要求。但是一般java开发基本都是服务器开发，一般不存在这个问题。

第2章 数组

2.1 数组概念

　　数组是空间复杂度为的一种。它使用空间复杂度为来存储一组普通情况下直接说复杂度，默认为算法的时间复杂度的数组。这里我们要提取与数组相关的三个关键词：线性表、连续内存空间、相同数据类型；数组有连续的内存空间，存储相同类型的数据。正是这个特性使得数组有了一个特性：随机存取。但是，有利也有弊。虽然这个特性使得访问数组的边缘变得非常容易，但是它也使得插入和删除数组的操作非常低效。为了保证插入和删除数据后的连续性，需要做大量的数据迁移工作。

　　线性表数据结构:

　　线性查找：线性查找就是简单的查找数组中的元素二分法查找：二分法查找要求目标数组必须是有序的

2.2 无序数组

　　一组连续的内存空间:公共类缅甸{

　　//声明一个数组

　　private long[]arr；

　　//有效数据的长度

　　私有（同Internationalorganizations）国际组织元素；

　　//无参构造函数，默认长度为50

　　公共缅甸(){

　　arr=new long[50]；

　　}

　　public MyArray(int maxsize){

　　arr=new long[maxsize]；

　　}

　　//添加数据

　　公共空插入（长值){

　　arr[elements]=值；

　　元素；

　　}

　　//显示数据

　　公共空的显示(){

　　系统。出去。打印([)；

　　for(int I=0；一。要素；i ){

　　系统。出去。print(arr[I] )；

　　}

　　系统。出去。println(])；

　　}

　　//根据下标查找数据

　　public long get(int index){

　　if(index=elements index 0){

　　抛出新的ArrayIndexOutOfBoundsException()；

　　}否则{

　　return arr[index]；

　　}

　　}

　　/**

　　* 根据值查询

　　* @param值需要被查询的值

　　* @返回被查询值的下标

　　*/

　　公共（同Internationalorganizations）国际组织搜索(int值){

　　//声明一个变量我用来记录该数据的下标值

　　int I；

　　for(I=0；一。要素；i ){

　　if(value==arr[i]){

　　打破；

　　}

　　}

　　//如果查询到最后一个元素依然没有找到

　　if(i==elements){

　　return-1；

　　}否则{

　　返回我；

　　}

　　}

　　//根据下标删除数据

　　public void delete(int index){

　　if(index=elements index 0){

　　抛出新的ArrayIndexOutOfBoundsException()；

　　}否则{

　　//删除该元素后，后面所有元素前移一位

　　for(int I=index；一。要素；i ){

　　arr[I]=arr[I 1]；

　　}

　　元素-;

　　}

　　}

　　/**

　　* 替换数据

　　* @param索引被替换的下标

　　* @param newvalue新的数据

　　*/

　　public void change(int index，int newvalue){

　　if(index=elements index 0){

　　抛出新的ArrayIndexOutOfBoundsException()；

　　}否则{

　　arr[index]=新值；

　　}

　　} }相同类型的数据:插入快（时间复杂度为：O(1))、如果知道下标，可以很快存储查找数组中的方法有两种:查询慢（时间复杂度为：O(n))、删除慢

2.3 有序数组

　　实现类:公共类MyOrderArray {

　　private long[]arr；

　　私有（同Internationalorganizations）国际组织元素；

　　公共MyOrderArray(){

　　arr=new long[50]；

　　}

　　public MyOrderArray(int maxsize){

　　arr=new long[maxsize]；

　　}

　　//添加数据

　　public void insert(int value){

　　int I；

　　for(I=0；一。要素；i ){

　　if(arr[i] value){

　　打破；

　　}

　　}

　　for(int j=元素；j I；j - ){

　　arr[j]=arr[j-1]；

　　}

　　arr[i]=值；

　　元素；

　　}

　　//删除数据

　　public void delete(int index){

　　if(index=elements index 0){

　　抛出新的ArrayIndexOutOfBoundsException()；

　　}否则{

　　for(int I=index；一。要素；i ){

　　arr[I]=arr[I 1]；

　　}

　　元素-;

　　}

　　}

　　//修改数据

　　public void change(int index，int value){

　　if(index=elements index 0){

　　抛出新的IndexOutOfBoundsException()；

　　}否则{

　　arr[index]=值；

　　}

　　}

　　//根据下标查询数据

　　public long get(int index){

　　if(index=elements index 0){

　　抛出新的IndexOutOfBoundsException()；

　　}否则{

　　return arr[index]；

　　}

　　}

　　//展示数据

　　公共空的显示(){

　　系统。出去。打印([)；

　　for(int I=0；一。要素；i ){

　　系统。出去。print(arr[I] )；

　　}

　　系统。出去。println(])；

　　}

　　//二分法查找数据

　　公共int二分搜索法(长值){

　　//声明三个指针分别指向数组的头，尾，中间

　　int low=0；

　　int pow=元素

　　int middle=0；

　　while(true){

　　中间=(低功率)/2;

　　//如果中指针所指的值等于带查询数

　　if(arr[middle]==value){

　　返回中间；

　　}else if(低功率){

　　return-1；

　　}否则{

　　if(arr[middle] value){

　　//待查询的数在左边，右指针重新改变指向

　　pow=middle-1；

　　}否则{

　　//带查询的数在右边，左指针重新改变指向

　　低=中1;

　　}

　　}

　　}

　　}}优点:快速查询(时间复杂度：O(logn))缺点:慢速增删(时间复杂度：O(n))

第三章 栈

　　010-1实现类(stack)，有些地方叫stack。没有位置的概念，可以随时访问和删除的元素就是之前存储的最后一个元素，确定一个默认的访问顺序。

　　因为栈数据结构只允许一端操作，所以按照LIFO的原理操作。

　　堆栈可以通过顺序表或链表来实现。

3.1 栈概念

　　 Stack()创建一个新的空栈push(element)在栈顶添加一个新元素pop()取出栈顶元素peek()返回栈顶元素is_empty()确定栈是否为空size()返回栈中的元素个数优点:

　　打包mystack公共类MyStack {

　　//堆栈的底层使用数组来存储数据

　　//private int[]元素；

　　int[]元素；//测试时使用

　　public MyStack() {

　　elements=new int[0]；

　　}

　　//添加元素

　　公共void push(int元素){

　　//创建一个新数组

　　int[]new arr=new int[elements . length 1]；

　　//将原始数组中的元素复制到新数组中

　　for(int I=0；I .元素.长度；i ) {

　　new arr[I]=elements[I]；

　　}

　　//将添加的元素放入新数组

　　new arr[elements . length]=element；

　　//用新数组替换旧数组

　　elements=newArr

　　}

　　//取出堆栈的顶部元素

　　public int pop() {

　　//当堆栈中没有元素时

　　if (is_empty()) {

　　引发新的runtime exception(“stack empty”)；

　　}

　　//取出数组的最后一个元素

　　int element=elements[elements . length-1]；

　　//创建一个新数组

　　int[]new arr=new int[elements . length-1]；

　　//原数组中除最后一个以外的其他元素放入新数组。

　　for(int I=0；长度-1；i ) {

　　new arr[I]=elements[I]；

　　}

　　elements=newArr

　　返回元素；

　　}

　　//查看堆栈的顶部元素

　　public int peek() {

　　返回元素[elements . length-1]；

　　}

　　//确定堆栈是否为空

　　公共布尔值is_empty() {

　　返回elements . length==0；

　　}

　　//检查堆栈中元素的数量

　　public int size() {

　　返回elements.length

　　}}缺点:

　　打包mystack公开课演示{

　　公共静态void main(String[] args) {

　　my stack ms=new my stack()；

　　//添加元素

　　普什女士(9)；

　　普什女士(8)；

　　普什女士(7)；

　　//取出顶层元素//system . out . println(ms . pop())；//7//system . out . println(ms . pop())；//8//system . out . println(ms . pop())；//9

　　//查看堆栈的顶部元素

　　system . out . println(ms . peek())；//7

　　system . out . println(ms . peek())；//7

　　//检查堆栈中元素的数量

　　system . out . println(ms . size())；//3

　　} }

3.2 栈的操作

第4章 队列

　　栈(Queue)是线性表，只允许一端插入，另一端删除。

　　队列是一种先进先出的线性表，简称FIFO。允许插入的末端是队列的末端，允许删除的末端是队列的头部。队列中间不允许操作！假设队列是q=(a1，a2，…，…，an)，那么a1是队列的头元素，an是尾元素。这样，我们在删除的时候总是可以从a1开始，在插入的时候总是可以在队列中结束。这也符合我们平时的习惯。第一个在前，最后一个在后。

　　和栈一样，队列也可以用顺序表或链表来实现。

4.1 队列概念

　　 Queue()创建一个空队列enqueue(element)向队列添加一个元素dequeue()从队列头删除一个元素is_empty()判断队列是否为空size()返回队列的大小实现类:

　　公共类MyQueue {

　　int[]元素；

　　公共MyQueue() {

　　elements=new int[0]；

　　}

　　//加入团队

　　公共void排队(int元素){

　　//创建一个新数组

　　int[]new arr=new int[elements . length 1]；

　　//将原始数组中的元素复制到新数组中

　　for(int I=0；I .元素.长度；i ) {

　　new arr[I]=elements[I]；

　　}

　　//将添加的元素放入新数组

　　new arr[elements . length]=element；

　　//用新数组替换旧数组

　　elements=newArr

　　}

　　//出列

　　public int dequeue() {

　　if (isEmpty()) {

　　抛出new RuntimeException(队列为空，无数据)；

　　}

　　//取出数组中的第一个元素

　　int element=elements[0]；

　　//创建一个新数组

　　int[]new arr=new int[elements . length-1]；

　　//将除第一个数据以外的原始数组保存到新数组中。

　　for(int I=0；I .元素.长度；i ) {

　　new arr[I]=elements[I 1]；

　　}

　　//新数组替换旧数组

　　elements=newArr

　　返回元素；

　　}

　　//确定团队是否为空。

　　public boolean isEmpty() {

　　返回elements . length==0；

　　}

　　//获取队列长度

　　public int size() {

　　返回elements.length

　　}}测试类:

　　公开课演示{

　　公共静态void main(String[] args) {

　　my queue MQ=new my queue()；

　　//加入团队

　　MQ . enqueue(1)；

　　MQ . enqueue(2)；

　　MQ . enqueue(3)；

　　//出列

　　system . out . println(MQ . dequeue())；//1

　　system . out . println(MQ . dequeue())；//2

　　system . out . println(MQ . dequeue())；//3

　　} }

4.2 队列的操作

第5章 链表

5.1 单链表

　　队列也叫单向链表，是链表最简单的形式。它的每个节点包含两个域，一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接字段指向一个空值。

　　元素字段数据用于存储特定数据。链接next用于存储下一个节点的位置

单链表概念

　　 is_empty()链表是否为空length()链表长度travel()遍历整个链表添加元素append(item)在链表头部添加元素insert(pos，item)在链表尾部添加元素remove(item)在指定位置删除节点search(item)查找节点是否存在

　　//节点公共类节点{

　　//节点内容

　　int数据；

　　//下一个节点

　　下一个节点；

　　公共节点(整数数据){

　　this.data=data

　　}

　　//为节点追加节点

　　公共节点追加(节点节点){

　　//当前节点

　　Node currentNode=this

　　//循环返回

　　while (true) {

　　//取出下一个节点

　　node next node=current node . next()；

　　//如果下一个节点为空，则当前节点已经是最后一个节点

　　if (nextNode==null) {

　　打破；

　　}

　　//赋给当前节点，无线向后看。

　　currentNode=nextNode

　　}

　　//将要追加的节点追加为找到的当前节点的下一个节点(最后一个节点)

　　currentNode.next=node

　　还这个；

　　}

　　//显示所有节点信息

　　公共void show() {

　　Node currentNode=this

　　while (true) {

　　system . out . print(current node . data )；

　　//取出下一个节点

　　current node=current node . next；

　　//如果是最后一个节点

　　if (currentNode==null) {

　　打破；

　　}

　　}

　　system . out . println()；

　　}

　　//插入一个节点作为当前节点的下一个节点

　　(节点node) {

　　//取出下一个节点作为下一个节点

　　节点nextNext=下一个

　　//把新节点作为当前节点的下一个节点

　　this.next=node

　　//把下下一个节点设置为新节点的下一个节点

　　node.next=nextNext

　　}

　　//删除下一个节点

　　公共void removeNode() {

　　//取出下下一个节点

　　节点newNext=next.next

　　//把下下一个节点设置为当前节点的下一个节点

　　this.next=newNext

　　}

　　//获取下一个节点

　　公共节点下一个(){

　　返回这个.下一个

　　}

　　//获取节点中的数据

　　public int getData() {

　　返回这.数据

　　}

　　//判断节点是否为最后一个节点

　　public boolean isLast() {

　　return next==null

　　}}实现类:

　　公开课演示{

　　公共静态void main(String[] args) {

　　//创建节点

　　节点n1=新节点(1);

　　节点n2=新节点(2);

　　节点n3=新节点(3);

　　//追加节点

　　n1.append(n2).追加(n3)；

　　//取出下一个节点数据

　　System.out.println(n1.next().下一个()。get data())；//3

　　//判断节点是否为最后一个节点

　　系统。出去。println(n1。是last())；//假

　　System.out.println(n1.next().下一个()。isLast())；//真

　　//显示所有节点信息

　　n1。show()；//1 2 3

　　//删除一个节点//n1。下一个。删除节点()；//n1。show()；//1 2

　　//插入一个新节点

　　n1 .接下来.之后(新节点(0));

　　n1。show()；//1 2 0 3

　　}}

单链表操作

5.2 循环链表

　　 单链表的一个变形是单向循环链表，链表中最后一个节点的然后域不再为没有，而是指向链表的头节点。

循环链表概念

　　测试类:

　　//表示一个节点公共类LoopNode {

　　//节点内容

　　（同Internationalorganizations）国际组织数据；

　　//下一个节点

　　LoopNode next=this//与单链表的区别，追加了一个这个，当只有一个节点时指向自己

　　公共循环节点（整数数据){

　　this.data=数据

　　}

　　//插入一个节点

　　public void after(LoopNode node) {

　　一个节点接一个节点循环=this。接下来；

　　this.next=node

　　node.next=afterNode

　　}

　　//删除一个节点

　　public void removeNext() {

　　循环节点新节点=this。下一个。接下来；

　　this.next=newNode

　　}

　　//获取下一个节点

　　公共LoopNode next() {

　　返回这个.下一个

　　}

　　//获取节点中的数据

　　public int getData() {

　　返回这.数据

　　}}单链表:

　　公开课演示{

　　公共静态void main(String[] args) {

　　//创建节点

　　循环节点n1=新循环节点(1)；

　　循环节点n2=新循环节点(2)；

　　循环节点n3=新循环节点(3)；

　　循环节点n4=新循环节点(4)；

　　//增加节点

　　n1。(N2)之后；

　　n2。在(n3)之后；

　　n3。(n4)之后；

　　System.out.println(n1.next().get data())；//2

　　System.out.println(n2.next().get data())；//3

　　System.out.println(n3.next().get data())；//4

　　System.out.println(n4.next().get data())；//1

　　}}

循环链表操作

5.3 双向循环链表

　　 在双向链表中有两个指针域，一个是指向前驱结点的上一页，一个是指向后继结点的然后指针

双向循环链表概念

　　实现类:

　　公共类双重节点{

　　//上一个节点

　　双节点前置=this

　　//下一个节点

　　DoubleNode next=this

　　//节点数据

　　（同Internationalorganizations）国际组织数据；

　　public DoubleNode(int data) {

　　this.data=数据

　　}

　　//增加节点

　　(双节点节点)之后的公共空的

　　//原来的下一个节点

　　双节点nextNext=下一个

　　//新节点作为当前节点的下一个节点

　　this.next=node

　　//当前节点作为新节点的前一个节点

　　node.pre=this

　　//原来的下一个节点作为新节点的下一个节点

　　node.next=nextNext

　　//原来的下一个节点的上一个节点为新节点

　　nextNext.pre=node

　　}

　　//获取下一个节点

　　public DoubleNode getNext() {

　　返回这个.下一个

　　}

　　//获取上一个节点

　　public DoubleNode getPre() {

　　返回this.pre

　　}

　　//获取数据

　　public int getData() {

　　返回this.data

　　}}测试类:

　　公开课演示{

　　公共静态void main(String[] args) {

　　//创建一个节点

　　DoubleNode n1=新double node(1)；

　　DoubleNode n2=新double node(2)；

　　double node n3=new double node(3)；

　　//追加节点

　　n1 . after(N2)；

　　n2 .在(n3)之后；

　　//查看上一个、自身、下一个节点内容

　　System.out.println(n2.getPre()。get data())；//1

　　system . out . println(N2 . get data())；//2

　　System.out.println(n2.getNext()。get data())；//3

　　System.out.println(n1.getPre()。get data())；//3

　　System.out.println(n3.getNext()。get data())；//1

　　}}

双向循环链表操作

第6章 树结构基础

　　线性结构中的数组和链表都是被诟病的；比如要找到某个数字，就必须从头开始，这样消耗的时间比较多。使用树结构，实现类和测试类的性能优于线性结构。

6.1 为什么要使用树结构

　　实现类

　　1、测试类:顶部唯一；例如：a

　　2、插入:子节点的父节点称为父节点；如果A是B，C，D的父节点，B就是E，f的父节点。

　　3、查找:父节点生成的节点是子节点。

　　4、示意图:根节点到目标节点的距离称为路径；要访问F，路径是A-B-F.

　　5、根节点:有多少个子节点就有多少度(最低度必须是0，所以是叶节点)

　　6，双亲节点:存储在节点中的数字

　　7、子节点:没有孩子的节点是没有下一代的节点；e，f，c和g。

　　8、路径:在整棵树中，一个部分被认为是一棵树，即使只有一个节点，它也是一棵树，但这棵树属于整棵树，并且包含关系。

　　9、节点的度:表示家谱有多少代；比如A是1，B，C，D是2，E，F，G是3。

　　10，节点的权:一棵树的最大层数：最大层数。

　　1，叶子节点:多棵树的集合

6.2 树结构基本概念

　　子树:树中任何节点的子节点之间都没有顺序关系。这种树叫无序树，也叫自由树；

　　层:树中任意节点的子节点之间存在顺序关系。这种树称为有序树；

　　树的高度:每个节点最多有两个子树的树称为二叉树；森林:对于二叉树，假设其深度为d(d1)。除了D层，其他层的节点数都达到了最大，D层的所有节点都是从左到右连续紧密排列的。这样的二叉树称为完全二叉树，其中完全二叉树定义为所有叶子节点都在底部的完全二叉树；无序树(AVL树):二叉树当且仅当任意节点的两个子树的高度差不大于1；有序树(二叉查找树(英语：二叉查找树)，又名二叉查找树和有序二叉树)；二叉树(用于信息编码):加权路径最短的二叉树称为霍夫曼树或最优二叉树；完全二叉树:优化读写操作的自平衡二叉查找树，可以保持数据有序，有两个以上的子树。

6.3 树的种类

　　平衡二叉树:将数据结构存储在固定数组中，在遍历速度上有一定优势，但由于空间较大，是非主流的二叉树。二叉树通常以链的形式存储。排序二叉树:

　　因为节点数无法掌握，所以常见树的存储表示都转换成二叉树进行处理，子节点数最多为2。

6.4 树的存储与表示

　　 1、xml、html等。那么在写这些东西的解析器的时候，就不可避免的要用到树。

　　2.路由协议是一种使用树的算法。

　　3.mysql数据库索引

　　4.文件系统的目录结构

　　5.这么多经典的AI算法其实都是树搜索，机器学习中的决策树也是树结构。

6.5 常见的一些树的应用场景

第7章 二叉树大全

　　任意节点的子节点数不超过霍夫曼树，为二叉树；二叉树的子节点分为左节点和右节点，不能颠倒。

7.1 二叉树的定义

　　B树:二叉树的第I层最多有2 (i-1)个节点(i0)。

　　顺序存储:深度为k的二叉树最多有(k0)个2^k-1节点

　　链式存储:对于任意二叉树，如果叶节点数为N0，度为2的节点总数为N2，则N0=N2 1；

　　2:具有n个节点的完整二叉树的深度必须是log2(n-1)

　　性质1:对于一棵完全二叉树，如果从上到下从左到右编号，编号为I的节点必有其左子编号2i和右子编号2i+1；父代的个数必须是I/2 (I=1是根，除外)

7.2 二叉树的性质(特性)

　　性质2:所有的叶子节点都集中在二叉树的最底层，节点总数为：2^n-1 (n n为层数/高度)。

　　strong>完全二叉树： 所有的叶子节点都在最后一层或者倒数第二层，且最后一层叶子节点在左边连续，倒数第二层在右边连续（满二叉树也是属于完全二叉树）（从上往下，从左往右能挨着数满）

7.4 链式存储的二叉树

　　树的遍历：

　　先序遍历：根节点，左节点，右节点（如果节点有子树，先从左往右遍历子树，再遍历兄弟节点）先序遍历结果为：A B D H I E J C F K G

　　中序遍历：左节点，根节点，右节点（中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数）中遍历结果为：H D I B E J A F K C G

　　后序遍历：左节点，右节点，根节点后序遍历结果：H I D J E B K F G C A

　　层次遍历：从上往下，从左往右层次遍历结果：A B C D E F G H I J K查找节点：先对树进行一次遍历，然后找出要找的那个数；因为有三种排序方法，所以查找节点也分为先序查找，中序查找，后序查找；

　　删除节点：由于链式存储，不能找到要删的数直接删除，需要找到他的父节点，然后将指向该数设置为null；所以需要一个变量来指向父节点，找到数后，再断开连接。

　　代码实现：

　　树类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 middleShow() {

　　 if (root != null) {

　　 root.middleShow();

　　 }

　　 }

　　 //后序遍历

　　 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.print(value + " ");

　　 //左节点

　　 if (leftNode != null) {

　　 leftNode.frontShow(); //递归思想

　　 }

　　 //右节点

　　 if (rightNode != null) {

　　 rightNode.frontShow();

　　 }

　　 }

　　 //中序遍历

　　 public void middleShow() {

　　 //左节点

　　 if (leftNode != null) {

　　 leftNode.middleShow(); //递归思想

　　 }

　　 //先遍历当前节点的值

　　 System.out.print(value + " ");

　　 //右节点

　　 if (rightNode != null) {

　　 rightNode.middleShow();

　　 }

　　 }

　　 //后续遍历

　　 public void afterShow() {

　　 //左节点

　　 if (leftNode != null) {

　　 leftNode.afterShow(); //递归思想

　　 }

　　 //右节点

　　 if (rightNode != null) {

　　 rightNode.afterShow();

　　 }

　　 //先遍历当前节点的值

　　 System.out.print(value + " ");

　　 }

　　 //先序查找

　　 public TreeNode frontSearch(int i) {

　　 TreeNode target = null;

　　 //对比当前节点的值

　　 if (this.value == i) {

　　 return this;

　　 //当前节点不是要查找的节点

　　 } else {

　　 //查找左儿子

　　 if (leftNode != null) {

　　 //查找的话t赋值给target，查不到target还是null

　　 target = leftNode.frontSearch(i);

　　 }

　　 //如果target不为空，说明在左儿子中已经找到

　　 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 Demo {

　　 public static void main(String[] args) {

　　 //创建一棵树

　　 BinaryTree binaryTree = new BinaryTree();

　　 //创建一个根节点

　　 TreeNode root = new TreeNode(1);

　　 //把根节点赋给树

　　 binaryTree.setRoot(root);

　　 //创建左,右节点

　　 TreeNode rootLeft = new TreeNode(2);

　　 TreeNode rootRight = new TreeNode(3);

　　 //把新建的节点设置为根节点的子节点

　　 root.setLeftNode(rootLeft);

　　 root.setRightNode(rootRight);

　　 //为第二层的左节点创建两个子节点

　　 rootLeft.setLeftNode(new TreeNode(4));

　　 rootLeft.setRightNode(new TreeNode(5));

　　 //为第二层的右节点创建两个子节点

　　 rootRight.setLeftNode(new TreeNode(6));

　　 rootRight.setRightNode(new TreeNode(7));

　　 //先序遍历

　　 binaryTree.frontShow(); //1 2 4 5 3 6 7

　　 System.out.println();

　　 //中序遍历

　　 binaryTree.middleShow(); //4 2 5 1 6 3 7

　　 System.out.println();

　　 //后序遍历

　　 binaryTree.afterShow(); //4 5 2 6 7 3 1

　　 System.out.println();

　　 //先序查找

　　 TreeNode result = binaryTree.frontSearch(5);

　　 System.out.println(result); //binarytree.TreeNode@1b6d3586

　　 //删除一个子树

　　 binaryTree.delete(2);

　　 binaryTree.frontShow(); //1 3 6 7 ，2和他的子节点被删除了

　　 }}

7.5 顺序存储的二叉树

　　概述：顺序存储使用数组的形式实现；由于非完全二叉树会导致数组中出现空缺，有的位置不能填上数字，所以顺序存储二叉树通常情况下只考虑完全二叉树

　　原理： 顺序存储在数组中是按照第一层第二层一次往下存储的，遍历方式也有先序遍历、中序遍历、后续遍历

　　性质：

　　第n个元素的左子节点是：2*n+1；第n个元素的右子节点是：2*n+2；第n个元素的父节点是：（n-1)/2代码实现：

　　树类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.print(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 Demo {

　　 public static void main(String[] args) {

　　 int[] data = {1,2,3,4,5,6,7};

　　 ArrayBinaryTree tree = new ArrayBinaryTree(data);

　　 //先序遍历

　　 tree.frontShow(); //1 2 4 5 3 6 7

　　 }}

7.6 线索二叉树(Threaded BinaryTree)

　　当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点

　　原理：n个结点的二叉链表中含有n+1(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针。

　　例如：某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继（这种附加的指针称为"线索"）代码实现：

　　树类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 void threadIterate() {

　　 //用于临时存储当前遍历节点

　　 ThreadedNode node = root;

　　 while (node != null) {

　　 //循环找到最开始的节点

　　 while (node.leftType == 0) {

　　 node = node.leftNode;

　　 }

　　 //打印当前节点的值

　　 System.out.print(node.value + " ");

　　 //如果当前节点的右指针指向的是后继节点，可能后继节点还有后继节点

　　 while (node.rightType == 1) {

　　 node = node.rightNode;

　　 System.out.print(node.value + " ");

　　 }

　　 //替换遍历的节点

　　 node = node.rightNode;

　　 }

　　 }

　　 //获取根节点

　　 public ThreadedNode getRoot() {

　　 return root;

　　 }

　　 //先序遍历

　　 public void frontShow() {

　　 if (root != null) {

　　 root.frontShow();

　　 }

　　 }

　　 //中序遍历

　　 public void middleShow() {

　　 if (root != null) {

　　 root.middleShow();

　　 }

　　 }

　　 //后序遍历

　　 public void afterShow() {

　　 if (root != null) {

　　 root.afterShow();

　　 }

　　 }

　　 //先序查找

　　 public ThreadedNode frontSearch(int i) {

　　 return root.frontSearch(i);

　　 }

　　 //删除一个子树

　　 public void delete(int i) {

　　 if (root.value == i) {

　　 root = null;

　　 } else {

　　 root.delete(i);

　　 }

　　 }}节点类public class ThreadedNode {

　　 //节点的权

　　 int value;

　　 //左儿子

　　 ThreadedNode leftNode;

　　 //右儿子

　　 ThreadedNode rightNode;

　　 //标识指针类型,1表示指向上一个节。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。