大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

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

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

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

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

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

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

  • 数据结构和算法的关系

    • 程序 = 数据结构 + 算法

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

  • 数据结构和算法学习大纲
    Java数据结构与算法的示例分析

1.2 数据结构概述

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

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

逻辑结构

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

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

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

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

存储结构

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

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

  • 区别

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

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

1.3 算法概述

  • 同一问题不同解决方法

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

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

  • 各排序算法复杂度及稳定性
    Java数据结构与算法的示例分析

如何理解“大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)

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

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

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

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

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

常用时间复杂度
Java数据结构与算法的示例分析

  • 注意:经常将log2n(以2为底的对数)简写成logn

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

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

  • 所以时间消耗由小到大为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
  • 语句(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)的运算。没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。

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

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

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

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开始,而插入时,总是在队列最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后。

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

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

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 单链表

单链表概念

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

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

  • 表元素域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,而是指向链表的头节点。
Java数据结构与算法的示例分析

循环链表操作

实现类

//表示一个节点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指针
Java数据结构与算法的示例分析

双向循环链表操作

实现类

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 树结构基本概念

示意图
Java数据结构与算法的示例分析
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 树的存储与表示

顺序存储:将数据结构存储在固定的数组中,然在遍历速度上有一定的优势,但因所占空间比较大,是非主流二叉树。二叉树通常以链式存储。
Java数据结构与算法的示例分析
链式存储
Java数据结构与算法的示例分析
由于对节点的个数无法掌握,常见树的存储表示都转换成二叉树进行处理,子节点个数最多为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为层数 / 高度)

完全二叉树: 所有的叶子节点都在最后一层或者倒数第二层,且最后一层叶子节点在左边连续,倒数第二层在右边连续(满二叉树也是属于完全二叉树)(从上往下,从左往右能挨着数满)
Java数据结构与算法的示例分析

7.4 链式存储的二叉树

创建二叉树:首先需要一个树的类,还需要另一个类用来存放节点,设置节点;将节点放入树中,就形成了二叉树;(节点中需要权值,左子树,右子树,并且都能对他们的值进行设置)。

树的遍历

  • 先序遍历:根节点,左节点,右节点(如果节点有子树,先从左往右遍历子树,再遍历兄弟节点)
    先序遍历结果为:A B D H I E J C F K G

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

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

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

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

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

  • 层次遍历:从上往下,从左往右
    层次遍历结果:A B C D E F G H I J K
    Java数据结构与算法的示例分析

查找节点:先对树进行一次遍历,然后找出要找的那个数;因为有三种排序方法,所以查找节点也分为先序查找,中序查找,后序查找;

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

代码实现
Java数据结构与算法的示例分析

  • 树类

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:http://dzwzjz.com/article/gpecjc.html
在线咨询
服务热线
服务热线:028-86922220
TOP