Java数据结构与算法的示例分析

这篇文章给大家分享的是有关Java数据结构与算法的示例分析的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

十载的库尔勒网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都营销网站建设的优势是能够根据用户设备显示端的尺寸不同，自动调整库尔勒建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联从事“库尔勒网站设计”,“库尔勒网站推广”以来，每个客户项目都认真落实执行。

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

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

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

• 数据结构和算法的关系：

• 程序 = 数据结构 + 算法

• 数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位。

• 数据结构和算法学习大纲
  

1.2 数据结构概述

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

逻辑结构

• 集合结构：数据元素同属于一个集合，他们之间是并列关系，无其他的关系；可以理解为中学时期学习的集合，在一个范围之内，有很多的元素，元素间没有什么关系

• 线性结构：元素之间存在着一对一的关系；可以理解为每个学生对应着一个学号，学号与姓名就是线性结构

• 树形结构：元素之间存在着一对多的关系，可以简单理解为家庭族谱一样，一代接一代

• 图形结构：元素之间存在多对多的关系，每一个元素可能对应着多个元素，或被多个元素对应，网状图

存储结构

• 顺序存储结构：就是将数据进行连续的存储，我们可以将它比喻成学校食堂打饭排队一样，一个接着一个；

• 链式存储结构：不是按照顺序存储的，后一个进来的数只需要将他的地址告诉前一个节点，前一个节点中就存放了它后面那个数的地址，所以最后一个数的存储地址就是为null；可以将这种结构比喻成商场吃饭叫号，上面的号码比喻成是地址，你可以之后后面的地址是什么，上面的其他内容就是该节点的内容；

• 区别：

• 顺序存储的特点是查询快，插入或者删除慢

• 链式存储的特点是查询慢，插入或者删除快

1.3 算法概述

• 同一问题不同解决方法

• 通过时间和空间复杂度判断算法的优劣

• 算法没有最好的，只有最合适的，学习算法是为了积累学习思路，掌握学习思路，并不是为了解决某问题去记住某种算法；对于时间复杂度与空间复杂度，现在大多数开发情况下，我们都在使用以空间换时间，耗费更多的内存，来保证拥有更快的速度。

• 各排序算法复杂度及稳定性：
  

如何理解“大O记法”

对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为 3n^2 和 100n^2 属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n^2级。

时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多,它花费时间就多。算法中的语句执行次数称为语句频度或时间频度,记为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)

• 顺序结构，时间复杂度按加法进行计算

• 循环结构，时间复杂度按乘法进行计算

• 分支结构，时间复杂度取最大值

• 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略

• 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

常用时间复杂度：

• 注意：经常将log2n（以2为底的对数）简写成logn

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

• 所以时间消耗由小到大为：O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

案例1：

count = 0;				      (1)
	for(i = 0;i <= n;i++)	  (2)
		for(j = 0;j <= n;j++) (3)
			count++;          (4)

• 语句（1）执行1次

• 语句（2）执行n次

• 语句（3）执行n^2次

• 语句（4）执行n^2次

• 时间复杂度为：T(n) = 1+n+n^2+n^2 = O(n^2)

案例2：

a = 1; 						(1)
b = 2;						(2)
for(int i = 1;i <= n;i++) { (3)
	int s = a + b;			(4)
	b = a;					(5)
	a = s;					(6)
}	

• 语句（1）、（2）执行1次

• 语句（3）执行n次

• 语句（4）、（5）、（6）执行n次

• 时间复杂度为：T(n) = 1+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) = 0( f(n) )，其中 n 为输入规模，f(n)为语句关于 n 所占存储空间的函数

• 一个算法在计算机存储器上所占用的存储空间，包括三个方面

• 存储算法本身所占用的存储空间

• 算法的输入输出数据所占用的存储空间

• 算法在运行过程中临时占用的存储空间

案例：指定的数组进行反转，并返回反转的内容

解法一：

public static int[] reverse1(int[] arr) {
    int n = arr.length; //申请4个字节
    int temp; //申请4个字节
    for (int start = 0, end = n - 1; start <= end; start++, end--) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    return arr;}

• 空间复杂度为：S(n) = 4+4 = O(8) = O(1)

解法二：

public static int[] reverse2(int[] arr) {
    int n = arr.length; //申请4个字节
    int[] temp = new int[n]; //申请n*4个字节+数组自身头信息开销24个字节
    for (int i = n - 1; i >= 0; i--) {
        temp[n - 1 - i] = arr[i];
    }
    return temp;}

• 空间复杂度为：S(n) = 4+4n+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 无序数组

• 实现类：

public class MyArray {
	//声明一个数组
	private long[] arr;
	
	//有效数据的长度
	private int elements;
	
	//无参构造函数，默认长度为50
	public MyArray(){
		arr = new long[50];
	}
	
	public MyArray(int maxsize){
		arr = new long[maxsize];
	}
	
	
	//添加数据
	public void insert(long value){
		arr[elements] = value;
		elements++;
	}
	
	//显示数据
	public void display(){
		System.out.print("[");
		for(int i = 0;i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	//根据下标查找数据
	public long get(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	/**
	 * 根据值查询
	 * @param value 需要被查询的值
	 * @return 被查询值的下标
	 */
	public int search(int value){
		//声明一个变量i用来记录该数据的下标值
		int i ;
		for(i = 0;i < elements;i++){
			if(value == arr[i]){
				break;
			}
		}
		//如果查询到最后一个元素依然没有找到
		if(i == elements){
			return -1;
		}else{
			return i;
		}
	}
	
	//根据下标删除数据
	public void delete(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			//删除该元素后，后面所有元素前移一位
			for(int i = index; i < elements;i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
		
	}
	/**
	 * 替换数据
	 * @param index 被替换的下标
	 * @param newvalue 新的数据
	 */
	public void change(int index,int newvalue){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			arr[index] = newvalue;
		}
	} }

• 优点：插入快（时间复杂度为：O(1)）、如果知道下标，可以很快存储

• 缺点：查询慢（时间复杂度为：O(n)）、删除慢

2.3 有序数组

• 实现类：

public class MyOrderArray { 
	private long[] arr;
	
	private int elements;
	
	public MyOrderArray(){
		arr = new long[50];
	}
	
	public MyOrderArray(int maxsize){
		arr = new long[maxsize];
	}
	
	//添加数据
	public void insert(int value){
		int i;
		for(i = 0;i < elements;i++){
			if(arr[i] > value){
				break;
			}
		}
		for(int j = elements;j > i;j--){
			arr[j] = arr[j -1];
		}
		arr[i] = value;
		elements++;
	}
	
	
	//删除数据
	public void delete(int index){
		if(index >=elements || index <0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			for(int i = index;i < elements; i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
	}
	
	//修改数据
	public void change(int index,int value){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			arr[index] = value;
		}
	}
	
	//根据下标查询数据
	public long get(int index){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	//展示数据
	public void display(){
		System.out.print("[");
		for(int i = 0; i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	
	//二分法查找数据
	public int binarySearch(long value){
			//声明三个指针分别指向数组的头，尾，中间
			int low = 0;
			int pow = elements;
			int middle = 0;
			
			while(true){
				middle = (low + pow) / 2;
				//如果中指针所指的值等于带查询数
				if(arr[middle] == value){
					return middle;
				}else if(low > pow){
					return -1;
				}else{
					if(arr[middle] > value){
						//待查询的数在左边,右指针重新改变指向
						pow = middle-1;
					}else{
						//带查询的数在右边，左指针重新改变指向
						low = middle +1;
					}
				}
			}
	}}

• 优点：查询快（时间复杂度为：O(logn)）

• 缺点：增删慢（时间复杂度为：O(n)）

第三章 栈

3.1 栈概念

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出的原理运作。

栈可以用顺序表实现，也可以用链表实现。

3.2 栈的操作

• Stack() 创建一个新的空栈

• push(element) 添加一个新的元素element到栈顶

• pop() 取出栈顶元素

• peek() 返回栈顶元素

• is_empty() 判断栈是否为空

• size() 返回栈的元素个数

实现类：

package mystack;public class MyStack {

    //栈的底层使用数组来存储数据
    //private int[] elements;
    int[] elements; //测试时使用

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

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

    //取出栈顶元素
    public int pop() {
        //当栈中没有元素
        if (is_empty()) {
            throw new RuntimeException("栈空");
        }
        //取出数组的最后一个元素
        int element = elements[elements.length - 1];
        //创建一个新数组
        int[] newArr = new int[elements.length - 1];
        //原数组中除了最后一个元素其他元素放入新数组
        for (int i = 0; i < elements.length - 1; i++) {
            newArr[i] = elements[i];
        }
        elements = newArr;
        return element;
    }

    //查看栈顶元素
    public int peek() {
        return elements[elements.length - 1];
    }

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

    //查看栈的元素个数
    public int size() {
        return elements.length;
    }}

测试类：

package mystack;public class Demo {
    public static void main(String[] args) {
        MyStack ms = new MyStack();
        //添加元素
        ms.push(9);
        ms.push(8);
        ms.push(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
    }}

第4章 队列

4.1 队列概念

队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

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

4.2 队列的操作

• Queue() 创建一个空的队列

• enqueue(element) 往队列中添加一个element元素

• dequeue() 从队列头部删除一个元素

• is_empty() 判断一个队列是否为空

• size() 返回队列的大小

实现类：

public class MyQueue {

    int[] elements;

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

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

    //出队
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队空，无数据");
        }
        //把数组中第1个元素取出来
        int element = elements[0];
        //创建一个新数组
        int[] newArr = new int[elements.length - 1];
        //把原数组除了第一个数据，其他存入新数组
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i + 1];
        }
        //新数组替换旧数组
        elements = newArr;

        return element;
    }

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

    //获取队列长度
    public int size() {
        return elements.length;
    }}

测试类：

public class Demo {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue();

        //入队
        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
    }}

第5章 链表

5.1 单链表

单链表概念

单链表也叫单向链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

• 表元素域data用来存放具体的数据。

• 链接域next用来存放下一个节点的位置

单链表操作

• is_empty() 链表是否为空

• length() 链表长度

• travel() 遍历整个链表

• add(item) 链表头部添加元素

• append(item) 链表尾部添加元素

• insert(pos, item) 指定位置添加元素

• remove(item) 删除节点

• search(item) 查找节点是否存在

实现类：

//一个节点public class Node {

    //节点内容
    int data;
    //下一个节点
    Node next;

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

    //为节点追加节点
    public Node append(Node node) {
        //当前节点
        Node currentNode = this;
        //循环向后找
        while (true) {
            //取出下一个节点
            Node nextNode = currentNode.next();
            //如果下一个节点为null，当前节点已经是最后一个节点
            if (nextNode == null) {
                break;
            }
            //赋给当前节点，无线向后找
            currentNode = nextNode;
        }
        //把需要追加的节点，追加为找到的当前节点（最后一个节点）的下一个节点
        currentNode.next = node;
        return this;
    }

    //显示所有节点信息
    public void show() {
        Node currentNode = this;
        while (true) {
            System.out.print(currentNode.data + " ");
            //取出下一个节点
            currentNode = currentNode.next;
            //如果是最后一个节点
            if (currentNode == null) {
                break;
            }
        }
        System.out.println();
    }

    //插入一个节点作为当前节点的下一个节点
    public void after(Node node) {
        //取出下一个节点，作为下下一个节点
        Node nextNext = next;
        //把新节点作为当前节点的下一个节点
        this.next = node;
        //把下下一个节点设置为新节点的下一个节点
        node.next = nextNext;

    }

    //删除下一个节点
    public void removeNode() {
        //取出下下一个节点
        Node newNext = next.next;
        //把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }

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

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

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

测试类：

public class Demo {
    public static void main(String[] args) {
        //创建节点
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        //追加节点
        n1.append(n2).append(n3);
        //取出下一个节点数据
        System.out.println(n1.next().next().getData()); //3
        //判断节点是否为最后一个节点
        System.out.println(n1.isLast()); //false
        System.out.println(n1.next().next().isLast()); //true
        //显示所有节点信息
        n1.show(); //1 2 3
        //删除一个节点//        n1.next.removeNode();//        n1.show(); //1 2
        //插入一个新节点
        n1.next.after(new Node(0));
        n1.show(); //1 2 0 3
    }}

5.2 循环链表

循环链表概念

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

循环链表操作

实现类：

//表示一个节点public class LoopNode {

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

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

    //插入一个节点
    public void after(LoopNode node) {
        LoopNode afterNode = this.next;
        this.next = node;
        node.next = afterNode;
    }

    //删除一个节点
    public void removeNext() {
        LoopNode newNode = this.next.next;
        this.next = newNode;
    }

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

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

测试类：

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

        //增加节点
        n1.after(n2);
        n2.after(n3);
        n3.after(n4);
        System.out.println(n1.next().getData()); //2
        System.out.println(n2.next().getData()); //3
        System.out.println(n3.next().getData()); //4
        System.out.println(n4.next().getData()); //1
    }}

5.3 双向循环链表

双向循环链表概念

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

双向循环链表操作

实现类：

public class DoubleNode {
    //上一个节点
    DoubleNode pre = this;
    //下一个节点
    DoubleNode next = this;
    //节点数据
    int data;

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

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

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

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

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

测试类：

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

        //追加节点
        n1.after(n2);
        n2.after(n3);

        //查看上一个，自己，下一个节点内容
        System.out.println(n2.getPre().getData()); //1
        System.out.println(n2.getData()); //2
        System.out.println(n2.getNext().getData()); //3

        System.out.println(n1.getPre().getData()); //3
        System.out.println(n3.getNext().getData()); //1
    }}

第6章 树结构基础

6.1 为什么要使用树结构

线性结构中不论是数组还是链表，他们都存在着诟病；比如查找某个数必须从头开始查，消耗较多的时间。使用树结构，在插入和查找的性能上相对都会比线性结构要好

6.2 树结构基本概念

示意图

1、根节点：最顶上的唯一的一个；如：A

2、双亲节点：子节点的父节点就叫做双亲节点；如A是B、C、D的双亲节点，B是E、F的双亲节点

3、子节点：双亲节点所产生的节点就是子节点

4、路径：从根节点到目标节点所走的路程叫做路径；如A要访问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、树的高度：树的最大的层数：就是层数中的最大值

11、森林：多个树组成的集合

6.3 树的种类

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

• 二叉树：每个节点最多含有两个子树的树称为二叉树；

• 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

• 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

• 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；

• 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

• B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

6.4 树的存储与表示

顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

链式存储：

由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2

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

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

2、路由协议就是使用了树的算法

3、MySQL数据库索引

4、文件系统的目录结构

5、所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构

第7章 二叉树大全

7.1 二叉树的定义

任何一个节点的子节点数量不超过 2，那就是二叉树；二叉树的子节点分为左节点和右节点，不能颠倒位置

7.2 二叉树的性质(特性)

性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>0）

性质2：深度为k的二叉树至多有2^k - 1个结点（k>0）

性质3：对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;

性质4：具有n个结点的完全二叉树的深度必为 log2(n+1)

性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

7.3 满二叉树与完全二叉树

满二叉树： 所有叶子结点都集中在二叉树的最下面一层上，而且结点总数为：2^n-1 (n为层数 / 高度）

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

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

                网页题目：Java数据结构与算法的示例分析
                

                网页URL：https://www.cdcxhl.com/article22/gpecjc.html
            
            

                成都网站建设公司_创新互联，为您提供ChatGPT、手机网站建设、App开发、网站导航、云服务器、营销型网站建设            
            

                广告
                
            
            

                声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：
                创新互联