【Java数据结构】复习笔记-4.8w字全

教材

Data Structures and Algorithm Analysis Edition 3.2 (Java Version) . Clifford A. Shaffer
有中文版，可自行寻找。推荐有时间的同学看一遍，确实写的不错，不过如果是期末速通的可以移步了，来不及看的。

题型

考点

• 1 数据结构基本概念
  • 1.1 掌握数据、数据元素、数据项之间的关系
  • 1.2 掌握数据结构的定义
  • 1.3 掌握数据结构的三要素
  • 1.4 掌握数据类型、抽象数据类型和数据结构之间的关系
• 2 算法分析
  • 2.1 了解衡量算法在资源上的两个方面
  • 2.2 掌握O标记法，理解大O标记法的意义
  • 2.3 掌握Ω标记法，理解大Ω标记法的意义
  • 2.4 掌握Θ标记法，理解大Θ标记法的意义
  • 2.5 了解时空权衡原则
• 3 线性表、栈、队列
  • 3.1 掌握线性表的逻辑结构以及基本操作
  • 3.2 掌握用顺序存储结构对线性表基本操作的实现
  • 3.3 掌握链式存储结构的实现技术，比如单向链表以及带头节点的链表
  • 3.4 掌握链式存储结构对线性表基本结构的实现
  • 3.5 具有在实际中选取不同存储结构的判断能力
  • 3.6 掌握栈、队列的逻辑结构以及基本操作
  • 3.7 掌握顺序存储结构对栈和队列基本操作的实现
  • 3.8 掌握链式存储结构对栈和队列基本操作的实现
  • 3.9 掌握顺序存储结构中实现循环队列的具体要求
  • 3.10 理解递归调用和栈之间的关系
  • 3.11 掌握栈和队列的经典应用
• 4 二叉树、树和森林
  • 4.1 掌握二叉树、树和森林的定义以及它们之间的异同点
  • 4.2 掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力
  • 4.3 理解二叉树采用顺序存储结构和链式存储结构的差异性
  • 4.4 掌握二叉检索树、Huffman编码以及堆的实现
  • 4.5 掌握树、森林采用的各种存储方式的差异性
  • 4.6 掌握树和森林与二叉树的转换
  • 4.7 掌握树、森林在遍历方面和二叉树的不同以及相关性
  • 4.8 理解并查集的意义，掌握并查集两个基本操作的实现并掌握重量权衡平衡原则和路径压缩
    -5 图
  • 5.1 掌握图的定义，包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点
  • 5.2 掌握图采用邻接矩阵和邻接表进行存储的差异性
  • 5.3 掌握广度优先遍历和深度优先遍历
  • 5.4掌握最小支撑树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法）、拓扑排序的实现过程
• 6 查找
  • 6.1 理解查找的定义
  • 6.2 掌握对查找算法进行衡量的一些指标：平均查找长度、成功查找的查找长度、查找不成功的查找长度
  • 6.3 掌握顺序查找和折半查找法，理解二者之间的异同点
  • 6.4 掌握散列技术，包括散列函数、散列表、散列冲突的发生及其解决方法、负载因子
• 7 排序
  • 7.1 掌握排序的稳定性
  • 7.2 对直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序、基数排序这些算法，掌握具体的排序过程集排序特点，并掌握时间复杂度、空间复杂度以及是否稳定等方面的特点
  • 7.3 具有在不同的应用需求下，能够根据各种排序算法特点选择合适排序算法的能力

具体复习笔记在同专栏里。基于这些考点进行了总结。

1 数据结构基本概念

1.1 掌握数据、数据元素、数据项之间的关系

数据（Data） 数据是对客观事物的符号表示，是计算机中能输入、输出并进行操作的信息的载体。数据可以是数字、文字、图形等形式。
数据元素（Data Element） 数据元素是数据的最小单位，在计算机中通常是一个数据项。一个数据元素可以由一个或多个数据项组成。
数据项（Data Item） 数据项是构成数据元素的基本单位，它是数据的不可分割的最小单位。数据项可以是一个单一的值，也可以是多个值的组合

                数据
                 |
          _______|______
         |             |
   数据元素        数据元素
   |   |   |       |   |
数据项 数据项 数据项 数据项

1.2 掌握数据结构的定义

是指相互之间存在一种或多种特定关系的数据元素的集合，以及定义在这个集合上的一组操作。

1.3 掌握数据结构的三要素

数据结构的三要素是指数据的逻辑结构、数据的存储结构和对数据的操作。下面详细解释这三要素：

数据的逻辑结构： 描述数据元素之间的逻辑关系，包括线性结构、树形结构、图形结构等。逻辑结构关注的是数据元素之间的相对位置关系，而不考虑在计算机内部的实际存储情况。

数据的存储结构： 描述数据元素在计算机内部的存储方式，包括顺序存储结构和链式存储结构等。存储结构关注的是数据元素在计算机内部的物理存储组织形式。

对数据的操作： 描述在数据上能够进行的操作，包括插入、删除、查找等。这些操作定义了对数据进行的一系列操作集合，也称为数据的运算。

1.4 掌握数据类型、抽象数据类型和数据结构之间的关系

1. 数据类型（Data Type）： 数据类型是一组值的集合和定义在这组值上的一组操作。它定义了数据的性质以及对该类数据进行的操作。数据类型可以是原始数据类型（如整数、浮点数、字符等），也可以是用户自定义的数据类型。

2. 抽象数据类型（Abstract Data Type，ADT）： 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。它关注的是数据的逻辑结构和操作，而不关心具体的实现方式。ADT 提供了一种抽象的视角，使用户可以通过接口而非实现的方式来使用数据。

3. 数据结构（Data Structure）： 数据结构是指在计算机中组织和存储数据的方式，包括数据的逻辑结构和存储结构。数据结构实际上是对数据在计算机内存中的组织形式进行了物理上的定义和描述。

关系如下：

数据类型和数据结构： 数据结构是在数据类型的基础上进行的，数据结构定义了数据在计算机内部的存储方式，可以看作是数据类型的实现。

抽象数据类型和数据结构： 抽象数据类型提供了对数据的抽象描述，而数据结构则是在这种抽象基础上进行具体的实现。ADT 主要关注逻辑结构和操作，而数据结构关注存储结构。

总体来说，数据类型是一种抽象概念，抽象数据类型提供了对数据的抽象描述，而数据结构是在这些抽象的基础上进行实际的物理存储和操作的具体实现。在程序设计中，数据类型和抽象数据类型的选择会影响到程序的设计和实现，而数据结构则负责具体的数据组织和操作实现。

2 算法分析

23-24学年我校数据结构与算法Ⅲ的期末试卷考察了算法分析的含义，且在设计题里需要利用数学归纳法证明大O表示法。

2.1 了解衡量算法在资源上的两个方面

在算法分析中，我们通常关注算法在资源上的两个主要方面：时间复杂度和空间复杂度。这两个方面用于衡量算法在执行过程中对计算机资源的利用情况。

1. 时间复杂度（Time Complexity）： 时间复杂度是衡量算法运行时间长短的度量，它表示算法执行所需的时间与问题规模之间的关系。通常以大 O 记法（O(n)）表示，其中 n 代表输入数据的规模。时间复杂度描述的是算法运行时间的增长趋势，即随着输入规模的增大，算法运行时间如何增长。

   常见的时间复杂度包括：

   • O(1): 常数时间复杂度，表示算法的执行时间是固定的，不随输入规模变化。
   • O(log n): 对数时间复杂度，通常出现在分治算法或二分查找等对问题规模进行对半缩小的情况。
   • O(n): 线性时间复杂度，算法的执行时间与输入规模成线性关系。
   • O(n^2): 平方时间复杂度，通常出现在嵌套循环的算法中。

2. 空间复杂度（Space Complexity）： 空间复杂度是衡量算法在执行过程中对计算机内存空间的利用情况。它表示算法所需的额外空间与输入规模之间的关系。同样以大 O 记法表示。

   常见的空间复杂度包括：

   • O(1): 常数空间复杂度，表示算法的额外空间占用是固定的，不随输入规模变化。
   • O(n): 线性空间复杂度，额外空间占用与输入规模成线性关系。
   • O(n^2): 平方空间复杂度，额外空间占用与输入规模的平方成正比。

在实际分析中，我们通常关注最坏情况下的时间复杂度和空间复杂度，因为它们能够给出算法执行所需资源的上限。理论上，时间和空间复杂度越低，算法越高效。然而，在实际应用中，有时需要权衡时间和空间，选择适当的算法来满足特定的需求。

2.2 掌握O标记法，理解大O标记法的意义

大 O 标记法是一种用于描述算法时间复杂度的表示方法，它表示算法执行时间随着输入规模的增大而变化的上限。具体而言，大 O 标记法描述的是算法的渐近复杂度（asymptotic complexity）。
在大 O 标记法中，我们用 O(f(n)) 来表示一个算法的时间复杂度，其中 f(n) 是关于输入规模 n 的一个函数。O(f(n)) 表示的是算法执行时间的上限，即最坏情况下的时间复杂度。大 O 表示法主要关注随着输入规模 n 的增长，算法执行时间的增长趋势。

一些常见的大 O 复杂度：

• O(1): 常数时间复杂度，表示算法的执行时间是常数，与输入规模无关。
• O(log n): 对数时间复杂度，通常出现在分治算法或二分查找等对问题规模进行对半缩小的情况。
• O(n): 线性时间复杂度，算法的执行时间与输入规模成线性关系。
• O(n^2): 平方时间复杂度，通常出现在嵌套循环的算法中。

2.3 掌握Ω标记法，理解大Ω标记法的意义

大Ω标记法（Omega Notation）是一种用于描述算法的渐近下界的符号表示方法。与大O标记法类似，大Ω标记法描述的是算法执行时间的增长趋势，但它关注的是最低界限，即算法在最好情况下的执行时间。

具体而言，如果一个算法在输入规模为n时，在最好情况下的执行时间以Ω(f(n))形式表示，其中f(n)是一个函数，那么这表示在足够大的n时，算法的执行时间至少以f(n)的速度增长。

大Ω标记法的意义在于提供了一个对算法在最好情况下性能的一种衡量方式。通过使用大Ω标记法，我们可以了解算法在最好情况下的性能表现，并更好地理解算法在不同输入情况下的行为。

举个例子，如果一个算法在最好情况下的执行时间是Ω(n)，那么这表示在最理想的情况下，算法的执行时间至少以线性的速度增长。在实际应用中，我们不仅关注算法在最坏情况下的性能，还关注在最好情况下的性能，因为这有助于更全面地评估算法的优劣。

需要注意的是，大Ω标记法并不总是提供和大O标记法相同的简便性。在实际使用中，我们通常更关注大O标记法，因为它提供了算法的上界，而对于最好情况下的性能，我们可能更关注实际的执行情况。

2.4 掌握Θ标记法，理解大Θ标记法的意义

大Θ标记法（Theta Notation）是一种用于描述算法的紧确界限的符号表示方法。与大O标记法和大Ω标记法不同，大Θ标记法同时表示算法的上界和下界，它给出了算法运行时间的确切增长情况。

具体而言，如果一个算法在输入规模为n时，在最坏情况下的执行时间以Θ(f(n))形式表示，其中f(n)是一个函数，那么这表示在足够大的n时，算法的执行时间以f(n)的速度增长，并且存在正常数c?和c?，使得对于足够大的n，c? * f(n) <= T(n) <= c? * f(n)。

简而言之，大Θ标记法提供了对算法运行时间增长的紧确界限，即算法的运行时间在上界和下界之间。

举个例子，如果一个算法在最坏情况下的执行时间是Θ(n)，那么这表示在足够大的n时，算法的执行时间以线性的速度增长，同时存在常数c?和c?，使得 c? * n <= T(n) <= c? * n。

大Θ标记法对于表示算法的平均性能是很有用的，因为它同时提供了上界和下界，给出了算法执行时间的紧确范围。然而，在实际使用中，大O标记法更为常见，因为它通常足够描述算法的性能特征，而且更容易计算。

2.5 了解时空权衡原则

时空权衡原则是在算法和数据结构设计中经常遇到的一个原则，它强调了在时间复杂度和空间复杂度之间需要做出权衡的概念。该原则指出，在提高算法执行速度的同时，可能会增加空间使用，反之亦然。通常来说，为了达到更好的性能，我们需要在时间和空间之间做出合理的权衡。

一些常见的时空权衡的例子包括：

1. 缓存（Caching）： 使用缓存可以显著提高某些操作的执行速度。但是，缓存需要占用额外的内存空间，因此需要权衡是否使用更多的内存以换取更快的执行速度。

2. 索引结构（Indexing Structures）： 在数据库或搜索引擎中，使用索引结构可以加速数据的检索操作。然而，建立索引会占用额外的存储空间，而且维护索引也可能增加更新操作的时间复杂度。

3. 压缩算法（Compression Algorithms）： 压缩算法可以减小数据的存储空间，但在访问数据时可能需要更多的时间来解压缩。这是一种时空权衡，需要根据具体的应用场景来选择合适的压缩算法。

4. 动态规划中的表格存储： 在动态规划算法中，为了避免重复计算，我们通常使用表格来存储已经计算过的中间结果。这会占用额外的空间，但可以在一定程度上提高算法的执行速度。

在设计算法和数据结构时，根据实际需求和问题特性，选择合适的时空权衡策略是非常重要的。在某些情况下，更注重时间性能可能更为关键，而在其他情况下，节省空间可能更为重要。因此，时空权衡原则提醒我们要在时间和空间之间找到一个平衡，以满足实际应用的需求。

在卷子里考察的会拿红色着重注明。

3 线性表、栈、队列

3.1 掌握线性表的逻辑结构以及基本操作

23-24学年数据结构与算法Ⅲ的期末卷考察点

1. 选择题 考察了链表相对于数组的优点（一般不会队满）
2. 填空题 考察了单链表中头节点的意义（在插入在表头或者删除第一个结点时不用考虑特殊情况，使空表和非空表的处理统一起来）
3. 算法设计题 利用链表类（使用Node）设计程序。

线性表的逻辑结构：

线性表是由n个数据元素构成的有限序列，其中元素之间存在唯一的前驱和后继关系。线性表可以为空表，也可以包含一个或多个元素。线性表有两种常见的实现方式：顺序表和链表。

线性表的基本操作

1. 插入（Insert）： 在线性表的指定位置插入一个新的元素。

   void insert(ElementType item, int position);
   

2. 删除（Delete）： 删除线性表中指定位置的元素。

   void delete(int position);
   

3. 查找（Search）： 在线性表中查找指定元素的位置。

   int search(ElementType item);
   

4. 遍历（Traverse）： 依次访问线性表中的每个元素。

   void traverse();
   

以上的基本操作适用于顺序表和链表两种实现方式。在顺序表中，元素在内存中是连续存储的；而在链表中，元素通过 节点 和 指针 的方式连接在一起，可以是连续的，也可以是分散的。

在实际应用中，选择顺序表还是链表取决于具体的需求。顺序表适用于对元素的随机访问较多的情况，而链表适用于频繁插入和删除操作的情况。

下面是一个简单的链表实现的 Java 代码示例，包括插入、删除和遍历操作：

class Node {
    int data;
    Node next;

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

public class LinkedList {
    Node head;

    // 插入操作
    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

    // 删除操作
    void delete(int data) {
        if (head == null) {
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node temp = head;
        while (temp.next != null && temp.next.data != data) {
            temp = temp.next;
        }

        if (temp.next != null) {
            temp.next = temp.next.next;
        }
    }

    // 遍历操作
    void traverse() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);

        System.out.println("Original List:");
        list.traverse();

        list.delete(2);

        System.out.println("List after deleting element 2:");
        list.traverse();
    }
}

3.2 掌握用顺序存储结构对线性表基本操作的实现

当使用顺序存储结构（数组）实现线性表时，我们可以通过数组来存储元素，并通过数组的索引来表示元素在线性表中的位置。

顺序存储结构下线性表的基本操作：

1. 插入（Insert）： 在指定位置插入一个新的元素。

   void insert(int[] array, int size, int position, int element) {
       if (position < 0 || position > size) {
           System.out.println("Invalid position");
           return;
       }
   
       // 将插入位置后的元素向后移动一位
       for (int i = size - 1; i >= position; i--) {
           array[i + 1] = array[i];
       }
   
       // 在插入位置插入新元素
       array[position] = element;
   }
   

2. 删除（Delete）： 删除指定位置的元素。

   void delete(int[] array, int size, int position) {
       if (position < 0 || position >= size) {
           System.out.println("Invalid position");
           return;
       }
   
       // 将删除位置后的元素向前移动一位
       for (int i = position; i < size - 1; i++) {
           array[i] = array[i + 1];
       }
   }
   

3. 查找（Search）： 查找指定元素的位置。

   int search(int[] array, int size, int element) {
       for (int i = 0; i < size; i++) {
           if (array[i] == element) {
               return i; // 返回元素的位置
           }
       }
       return -1; // 元素不存在
   }
   

4. 遍历（Traverse）： 遍历整个线性表。

   void traverse(int[] array, int size) {
       for (int i = 0; i < size; i++) {
           System.out.print(array[i] + " ");
       }
       System.out.println();
   }
   

3.3 掌握链式存储结构的实现技术，比如单向链表以及带头节点的链表

当使用链式存储结构（链表）实现线性表时，我们可以通过节点之间的指针关系来表示元素的逻辑顺序。链表的基本操作包括插入、删除、查找和遍历。

单向链表的基本操作：

单向链表中，每个节点包含一个数据域和一个指向下一个节点的指针。

1. 插入（Insert）： 在指定位置插入一个新的节点。

   class Node {
       int data;
       Node next;
   
       public Node(int data) {
           this.data = data;
           this.next = null;
       }
   }
   
   void insert(Node head, int position, int element) {
       Node newNode = new Node(element);
   
       // 找到插入位置的前一个节点
       Node temp = head;
       for (int i = 0; i < position - 1 && temp != null; i++) {
           temp = temp.next;
       }
   
       if (temp == null) {
           System.out.println("Invalid position");
           return;
       }
   
       // 插入新节点
       newNode.next = temp.next;
       temp.next = newNode;
   }
   

2. 删除（Delete）： 删除指定位置的节点。

   void delete(Node head, int position) {
       // 找到删除位置的前一个节点
       Node temp = head;
       for (int i = 0; i < position - 1 && temp != null; i++) {
           temp = temp.next;
       }
   
       if (temp == null || temp.next == null) {
           System.out.println("Invalid position");
           return;
       }
   
       // 删除节点
       temp.next = temp.next.next;
   }
   

3. 查找（Search）： 查找指定元素的位置。

   int search(Node head, int element) {
       Node temp = head;
       int position = 0;
       while (temp != null && temp.data != element) {
           temp = temp.next;
           position++;
       }
   
       if (temp == null) {
           return -1; // 元素不存在
       } else {
           return position; // 返回元素的位置
       }
   }
   

4. 遍历（Traverse）： 遍历整个链表。

   void traverse(Node head) {
       Node temp = head;
       while (temp != null) {
           System.out.print(temp.data + " ");
           temp = temp.next;
       }
       System.out.println();
   }
   

带头节点的链表的基本操作：

带头节点的链表中，头节点不存储实际的数据，仅用于标识链表的起始位置。初始化：

package linklist;

public class ListNode {
    public int id;
    //数据域
    public String data;
    //指针域
    public ListNode next;

    public ListNode(int id,String data){
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "id=" + id +
                ", data='" + data + '\'' +
                '}';
    }
}

3.4 掌握链式存储结构对线性表基本结构的实现

具体实现：

package linklist;

public class SingleLinkList {
    //先初始化一个头节点，头节点不存放具体数据
    private ListNode head;

    public void initSingLinkList() {
        head = new ListNode(0, "");
    }

    //添加节点
    public void insertNode(ListNode listNode) {
        //使用temp指针进行遍历
        ListNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = listNode;
    }

    //打印链表
    public void showSingleLinkList() {
        if (isEmpty()) {
            return;
        }
        ListNode temp = head.next;
        while (true) {
            if (temp == null) {
                return;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //判断链表是否为空
    public boolean isEmpty() {
        if (head.next == null) {
            System.out.println("链表为空");
            return true;
        }
        return false;
    }

    //按照id顺序添加节点
    public void insertByOrder(ListNode listNode) {
        ListNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id > listNode.id) {
                break;
            } else if (temp.next.id == listNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == true) {
            System.out.println("准备插入的数据编号已存在，无法添加");
        } else {
            listNode.next = temp.next;
            temp.next = listNode;
            System.out.println("插入成功");
        }
    }

    //修改节点数据
    public void updateNode(ListNode listNode) {
        ListNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {

                break;
            }
            if (temp.id == listNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.data = listNode.data;
        } else {
            System.out.println("没有找到要修改的节点");
        }
    }

    //删除节点
    public void delNode(int id) {
        ListNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;

        } else {
            System.out.println("要删除的节点不存在");
        }
    }

    //获取头节点
    public void getHeadNode() {
        ListNode temp = head;
        if (temp.next == null && temp.id == 0) {
            System.out.println("该链表为空无法获取头节点");
        } else {
            temp = temp.next;
            System.out.println("头节点为：" + temp);
        }
    }

    //获取尾节点
    public void getTailNode() {
        ListNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null && temp.id == 0) {
                System.out.println("该链表为空无法获取尾节点");
                break;
            }
            if (temp.next == null) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("尾节点为：" + temp);
        } else {
            System.out.println("无法找到该节点");
        }

    }

    //清空链表
    public void clearLinkList() {
        ListNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null && temp.id == 0) {
                System.out.println("该链表为空无法清空");
                break;
            }
            temp = temp.next;
            temp.data = "";
            if (temp.next == null) {
                flag = true;
                break;
            }
        }
        if (flag) {
            System.out.println("清空完成");
        }
    }

    //获取长度
    public void getLength() {
        ListNode temp = head;
        int length = 0;
        while (true) {
            if (temp.next == null && temp.id == 0) {
                System.out.println("该链表为空长度为"+length);
                break;
            }
            temp = temp.next;
            length++;
            if (temp.next == null) {
                System.out.println("该链表为空长度为"+length);
                break;
            }
        }
    }
}

3.5 具有在实际中选取不同存储结构的判断能力

一些在选择存储结构时需要考虑的因素：

1. 访问方式：

   • 如果需要频繁按照索引或位置进行随机访问，数组（顺序存储结构）可能更为合适，因为数组的元素在内存中是连续存储的，可以通过索引直接访问。
   • 如果主要进行插入、删除等操作，链表（链式存储结构）可能更为适用，因为链表在插入和删除时不需要移动大量元素，操作相对灵活。

2. 元素的动态性：

   • 如果元素的数量变化不大且已知，使用数组可能更为简便，因为数组的大小是固定的。
   • 如果元素的数量变化较大或者无法预知，使用链表更具弹性，可以根据需要动态分配内存。

3. 内存空间效率：

   • 数组通常对内存的利用更为高效，因为它们是连续存储的，不需要额外的指针信息。
   • 链表可能会占用更多的内存，因为每个节点需要额外的指针空间。

4. 插入和删除的复杂性：

   • 插入和删除操作对于链表而言通常更为高效，因为它们不需要移动大量元素。
   • 数组中的插入和删除可能需要移动大量元素，因此这些操作的复杂度可能较高。

5. 存储元素类型的灵活性：

   • 如果元素类型不固定或者元素类型的变化较大，使用链表更为灵活，因为它可以容纳不同类型的节点。
   • 数组在创建时需要指定元素的类型，并且所有元素的类型必须相同。

6. 对缓存的利用：

   • 数组在内存中是连续存储的，这有助于更好地利用缓存，因为缓存通常以块的形式读取数据。
   • 链表的节点在内存中可能不是连续存储的，这可能导致缓存效率降低。

7. 对算法的要求：

   • 不同算法对数据的存储结构有不同的要求。例如，某些排序算法可能对数组更加友好，而某些图算法可能对链表更加适用。

在实际选择存储结构时，需要综合考虑这些因素，并根据具体问题的性质权衡它们。在某些情况下，也可以考虑使用一些高级的数据结构，如哈希表、树等，以满足更复杂的需求。

3.6 掌握栈、队列的逻辑结构以及基本操作

栈（Stack）

• 定义： 栈是一种具有后进先出（Last In First Out，LIFO）特性的线性数据结构，即最后进入的元素最先被访问。
• 逻辑结构： 栈可以看作是一种受限的线性表，只能在表的一端（称为栈顶）进行插入和删除操作。
• 基本操作：
  1. 入栈（Push）： 将元素添加到栈的顶部。
  2. 出栈（Pop）： 从栈的顶部移除元素。
  3. 获取栈顶元素（Top）： 查看栈顶元素，但不对栈进行修改。
  4. 判空（isEmpty）： 判断栈是否为空。
  5. 获取栈的大小（Size）： 统计栈中元素的个数。

队列（Queue）

• 定义： 队列是一种具有先进先出（First In First Out，FIFO）特性的线性数据结构，即最先进入的元素最先被访问。
• 逻辑结构： 队列可以看作是一种受限的线性表，只能在表的一端（称为队尾）进行插入操作，在另一端（称为队头）进行删除操作。
• 基本操作：
  1. 入队（Enqueue）： 将元素添加到队列的尾部。
  2. 出队（Dequeue）： 从队列的头部移除元素。
  3. 获取队头元素（Front）： 查看队列头部的元素，但不对队列进行修改。
  4. 判空（isEmpty）： 判断队列是否为空。
  5. 获取队列大小（Size）： 统计队列中元素的个数。

栈和队列的比较

• 栈适合解决需要后进先出的问题，如递归、表达式求值等。
• 队列适合解决需要先进先出的问题，如任务调度、广度优先搜索等。
• 在某些场景中，还可以使用双端队列（Deque）来结合队列和栈的特性，提供更灵活的操作。

下面是基于Java的简单实现：

import java.util.LinkedList;

// 栈的实现
class Stack {
    private LinkedList<Integer> stack;

    public Stack() {
        stack = new LinkedList<>();
    }

    public void push(int element) {
        stack.addLast(element);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.removeLast();
    }

    public int top() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.getLast();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int size() {
        return stack.size();
    }
}

// 队列的实现
class Queue {
    private LinkedList<Integer> queue;

    public Queue() {
        queue = new LinkedList<>();
    }

    public void enqueue(int element) {
        queue.addLast(element);
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue.removeFirst();
    }

    public int front() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue.getFirst();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public int size() {
        return queue.size();
    }
}

3.7 掌握顺序存储结构对栈和队列基本操作的实现

顺序存储结构对栈的基本操作

class ArrayStack {
    private int[] stack;
    private int top; // 栈顶指针

    public ArrayStack(int capacity) {
        stack = new int[capacity];
        top = -1;
    }

    public void push(int element) {
        if (top == stack.length - 1) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = element;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public int top() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }
}

顺序存储结构对队列的基本操作

class ArrayQueue {
    private int[] queue;
    private int front; // 队头指针
    private int rear;  // 队尾指针

    public ArrayQueue(int capacity) {
        queue = new int[capacity];
        front = rear = -1;
    }

    public void enqueue(int element) {
        if (isEmpty()) {
            front = rear = 0;
        } else if (rear == queue.length - 1) {
            throw new RuntimeException("Queue is full");
        } else {
            rear++;
        }
        queue[rear] = element;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int element = queue[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
        return element;
    }

    public int front() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }

    public boolean isEmpty() {
        return front == -1 && rear == -1;
    }

    public int size() {
        if (isEmpty()) {
            return 0;
        }
        return rear - front + 1;
    }
}

这里的栈和队列基于数组实现，通过维护相应的指针来模拟栈和队列的特性。这种实现方式在一些场景中可能更为直观，但需要注意数组容量的限制。如果数组容量不足，需要进行扩容操作。

3.8 掌握链式存储结构对栈和队列基本操作的实现

链式存储结构对栈和队列的实现同样可以通过指针和节点的方式完成。下面分别是链式存储结构对栈和队列的基本操作实现：

链式存储结构对栈的基本操作

// 节点类
class Node {
    int data;
    Node next;

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

// 链式栈的实现
class LinkedStack {
    private Node top;

    public LinkedStack() {
        top = null;
    }

    public void push(int element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int element = top.data;
        top = top.next;
        return element;
    }

    public int top() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        int count = 0;
        Node temp = top;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
}

链式存储结构对队列的基本操作

// 链式队列的实现
class LinkedQueue {
    private Node front; // 队头指针
    private Node rear;  // 队尾指针

    public LinkedQueue() {
        front = rear = null;
    }

    public void enqueue(int element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int element = front.data;
        front = front.next;
        if (front == null) {
            rear = null; // 如果队列为空，重置队尾指针
        }
        return element;
    }

    public int front() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return front.data;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public int size() {
        int count = 0;
        Node temp = front;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
}

这里的链式存储结构实现了栈和队列的基本操作，通过指针的方式实现了元素的入栈、出栈、入队、出队等操作。链式结构相对于数组结构在动态操作方面更为灵活。

3.9 掌握顺序存储结构中实现循环队列的具体要求

循环队列是一种特殊的队列实现，通过使用循环方式维护队列的前后指针，实现循环利用底层数组，避免了队列元素在出队时需要移动整个队列的情况。在循环队列里要约定一个空位置，这是为了更好地区分队列为空和队列为满的情况。在循环队列中，队头指针 front 和队尾指针 rear 在数组中移动时，可能会出现两种情况：

1. 队列为空： 当 front 和 rear 指针重合时，队列为空。
2. 队列为满： 当 (rear + 1) % capacity == front 时，队列为满。

如果没有约定一个空位置，那么在队列为空和队列为满时，front 和 rear 指针都会重合，导致无法准确判断队列的状态。通过约定一个空位置，我们可以确保在队列为满时 rear 的下一个位置一定是 front，而在队列为空时，front 和 rear 指针重合。这样就能够清晰地判断队列的状态。

具体来说，如果队列的容量是 7，我们初始化数组为 int[8]，并约定第 8 个位置为空。这样，当 front 和 rear 指针都指向数组的第 0 个位置时，表示队列为空；当 (rear + 1) % capacity == front 时，表示队列为满。

这种约定使得循环队列的状态判断更加清晰，避免了状态混淆。如果队列的容量是 n，那么实际数组的大小应该是 n + 1，其中 n 用于存储队列元素，而另外 1 个位置用于约定为空。

1. 初始化：

   • 使用一个数组来存储队列元素。
   • 使用两个指针，一个指向队头（front），一个指向队尾（rear）。
   • 需要额外一个元素的空间作为约定，即队列中的一个空位置不存储元素。

2. 入队（Enqueue）：

   • 在队尾插入元素，然后将 rear 指针向后移动一位。
   • 如果 rear 指针超过数组边界，将其置为数组的起始位置。

3. 出队（Dequeue）：

   • 返回队头元素，然后将 front 指针向后移动一位。
   • 如果 front 指针超过数组边界，将其置为数组的起始位置。

4. 获取队头元素（Front）：

   • 返回 front 指针指向的元素。

5. 判空（isEmpty）：

   • 当 front 和 rear 指针相等时，队列为空。

6. 判满（isFull）：

   • 当 (rear + 1) % 数组长度等于 front 时，队列为满。

7. 获取队列大小（Size）：

   • 队列大小为 (rear - front + 数组长度) % 数组长度。

下面是基于数组的循环队列的简单实现：

class CircularQueue {
    private int[] queue;
    private int front; // 队头指针
    private int rear;  // 队尾指针
    private int capacity; // 队列容量

    public CircularQueue(int capacity) {
        this.capacity = capacity + 1; // 约定一个空位置
        queue = new int[this.capacity];
        front = rear = 0;
    }

    public void enqueue(int element) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        queue[rear] = element;
        rear = (rear + 1) % capacity;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int element = queue[front];
        front = (front + 1) % capacity;
        return element;
    }

    public int front() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    public int size() {
        return (rear - front + capacity) % capacity;
    }
}

这里的实现采用了取模运算来实现循环的效果，确保队尾指针在数组边界处正确回绕。

3.10 理解递归调用和栈之间的关系

递归调用的基本概念

1. 递归定义： 递归是指在函数的定义中使用函数自身的方法。递归可以将一个大型问题分解成一个或多个相似但规模较小的子问题。

2. 递归调用的特点：

   • 每次递归调用都会生成一个新的函数调用栈帧（包含局部变量、返回地址等信息）。
   • 每个栈帧都代表一个特定的递归层次，这些栈帧形成了一个栈结构。

递归调用的示例

// 计算阶乘的递归函数示例
public class RecursiveExample {
    public static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            // 递归调用
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("Factorial of 5: " + result);
    }
}

递归调用和栈的关系

期末卷综合题中考察了递归函数运行时其栈的调用情况（要画图），建议自己多写几个程序画出其栈的调用情况来练习。

1. 调用栈（Call Stack）： 在进行递归调用时，系统会为每次调用生成一个栈帧，这些栈帧按照调用的先后顺序形成一个调用栈。

2. 栈帧的生成与销毁：

   • 当函数被调用时，会生成一个新的栈帧并推入调用栈。
   • 当函数执行完毕或遇到递归终止条件时，对应的栈帧会从调用栈中弹出，被销毁。

3. 栈的特性：

   • 栈是一种后进先出（LIFO）的数据结构，与递归的特性相吻合。
   • 每个栈帧都包含了函数调用的上下文信息，包括局部变量、返回地址等。

4. 堆栈的大小限制： 递归调用过深可能导致调用栈溢出。在实际应用中，可以通过调整堆栈大小或使用迭代的方式来避免栈溢出的问题。

理解递归调用和栈的关系有助于更好地理解递归的执行流程和调试递归函数。

3.11 掌握栈和队列的经典应用

期末卷在填空题中有考察中缀表达式和后缀表达式的转换。

栈的经典应用

1. 函数调用栈： 编程语言中的函数调用过程通常使用栈来管理函数调用和返回。每次函数调用都会生成一个栈帧，将函数的局部变量、返回地址等信息保存在栈上。

2. 表达式求值： 栈可以用于中缀表达式到后缀表达式的转换，以及后缀表达式的求值。这种应用在计算机编译器和计算器中常见。

   以中缀表达式 `3 + 5 * (4 - 2)` 为例，演示中缀表达式转后缀表达式的顺序流程：
   
   1. **中缀表达式：** `3 + 5 * (4 - 2)`
   
   2. **初始化：** 创建一个空的后缀表达式字符串（用 `postfixExpression` 表示）和一个空的操作符栈（用 `operatorStack` 表示）。
   
   3. **遍历中缀表达式：**
   - 当遇到数字或字母时，直接输出到后缀表达式。当前缀表达式：`3`
   - 当遇到操作符 `+` 时，由于栈为空，直接入操作符栈。当前操作符栈：`+`，当前后缀表达式：`3`
   - 当遇到数字 `5` 时，直接输出到后缀表达式。当前操作符栈：`+`，当前后缀表达式：`3 5`
   - 当遇到操作符 `*` 时，由于栈为空，直接入操作符栈。当前操作符栈：`+*`，当前后缀表达式：`3 5`
   - 当遇到左括号 `(` 时，直接入操作符栈。当前操作符栈：`+*(`，当前后缀表达式：`3 5`
   - 当遇到数字 `4` 时，直接输出到后缀表达式。当前操作符栈：`+*(`，当前后缀表达式：`3 5 4`
   - 当遇到操作符 `-` 时，由于栈顶的操作符优先级低于当前操作符，直接入操作符栈。当前操作符栈：`+*(-`，当前后缀表达式：`3 5 4`
   - 当遇到数字 `2` 时，直接输出到后缀表达式。当前操作符栈：`+*(-`，当前后缀表达式：`3 5 4 2`
   - 当遇到右括号 `)` 时，弹出操作符栈中的所有操作符，直到遇到左括号 `(`，并输出到后缀表达式。当前操作符栈：`+*`，当前后缀表达式：`3 5 4 2 -`
   - 当遇到右括号 `)` 时，弹出操作符栈中的所有操作符，直到遇到左括号 `(`，并输出到后缀表达式。当前操作符栈：`+`，当前后缀表达式：`3 5 4 2 - * +`
   
   4. **遍历结束：** 遍历完中缀表达式后，弹出操作符栈中的所有操作符，并输出到后缀表达式。最终后缀表达式为：`3 5 4 2 - * +`
   
   通过以上步骤，我们成功地将中缀表达式 `3 + 5 * (4 - 2)` 转换为后缀表达式 `3 5 4 2 - * +`。
   

3. 括号匹配： 栈常用于检查表达式中的括号是否匹配。通过维护一个栈，可以在遍历表达式时判断括号的匹配情况。

4. 浏览器前进和后退： 浏览器的历史记录可以使用两个栈来实现，一个用于记录前进的页面，一个用于记录后退的页面。

5. 撤销机制： 在图形设计和文本编辑软件中，撤销操作可以使用栈来实现。每次操作都将状态压入栈中，撤销时弹出栈顶状态。

队列的经典应用

1. 任务调度： 操作系统中的进程调度和任务调度通常使用队列来管理待执行的任务。先进先出的特性使得任务按照顺序执行。

2. 打印队列： 打印任务通常会进入一个打印队列，按照先进先出的原则进行打印。

3. 广度优先搜索（BFS）： 图的广度优先搜索算法常常使用队列来管理待访问的节点，确保按层次遍历图。

4. 消息传递： 在计算机通信中，消息传递的队列模型常用于实现异步通信。消息发送者将消息放入队列，接收者从队列中取出消息进行处理。

5. 缓冲区： 缓冲区是队列的一种应用，用于平衡生产者和消费者之间的速度差异。例如，生产者产生数据，将其放入缓冲区，消费者从缓冲区取出数据进行处理。

4 二叉树、树和森林

重点章节，在选择，填空，综合中都有考察到。

4.1 掌握二叉树、树和森林的定义以及它们之间的异同点

1. 二叉树（Binary Tree）

定义： 二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。这两个子节点的位置是有序的，左子节点的值小于或等于父节点的值，右子节点的值大于父节点的值。

特点：

• 每个节点最多有两个子节点。
• 子节点的位置有序，左子节点值 <= 父节点值，右子节点值 > 父节点值。

性质：

• 在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。
• 深度为k的二叉树至多有2^k-1个结点（k>=1）。
• 对于任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
• 具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。
• 如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第一层到[log2n]+1层，每层从左到右），对任一结点i（1<=i<=n）:
  （1）如果i=1，则结点i是二叉树的根，无双亲，如果i>1,则其双亲结点是结点[i/2]
  （2）如果2i>n，则结点i无左孩子（结点i为叶子结点）否则左孩子是结点2i。
  （3）如果2i+1>n,则结点i无右孩子，否则其右孩子是结点2i+1.

2. 树（Tree）

定义： 树是一种层次结构的数据结构，由节点和连接这些节点的边组成。树中有一个特殊的节点称为根节点，除了根节点之外，每个节点有且只有一个父节点，但可以有多个子节点。

特点：

• 每个节点有且只有一个父节点，除了根节点。
• 节点之间通过边相连，形成层次结构。

3. 森林（Forest）

定义： 森林是多个独立的树组成的集合。每个树都是独立的，没有公共的根节点。换句话说，森林是多个树的集合。

特点：

• 由多个独立的树组成。
• 每个树都是独立的，没有公共的根节点。

异同点

1. 节点数量：

   • 二叉树：每个节点最多有两个子节点。
   • 树：每个节点有且只有一个父节点。
   • 森林：由多个独立的树组成。

2. 连接关系：

   • 二叉树：每个节点有左子节点和右子节点。
   • 树：除了根节点，每个节点有一个父节点。
   • 森林：独立的树结构，没有公共的根节点。

3. 结构关系：

   • 二叉树和树是单一的结构。
   • 森林是由多个独立的树组成的集合。

总体上，可以看出树是一种更一般的结构，而二叉树是树的一种特殊情况。森林是由多个树组成的结构。

4.2 掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力

期末试卷中填空题考到了根据给出的先序遍历和中序遍历字符串写出后序遍历的字符串。

二叉树的四种遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。可视化网站：Binary Tree Traversal

1. 前序遍历（Preorder Traversal）：

前序遍历的顺序是先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。

根 -> 左子树 -> 右子树

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeTraversal {
    public static void preorderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
    }

    public static void main(String[] args) {
        // 构建一棵二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 前序遍历
        System.out.println("Preorder Traversal:");
        preorderTraversal(root);
    }
}

2. 中序遍历（Inorder Traversal）

中序遍历的顺序是先递归地进行左子树的中序遍历，然后访问根节点，最后递归地进行右子树的中序遍历。

左子树 -> 根 -> 右子树

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeTraversal {
    public static void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    }

    public static void main(String[] args) {
        // 构建一棵二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 中序遍历
        System.out.println("Inorder Traversal:");
        inorderTraversal(root);
    }
}

3. 后序遍历（Postorder Traversal）

后序遍历的顺序是先递归地进行左子树的后序遍历，然后递归地进行右子树的后序遍历，最后访问根节点。

左子树 -> 右子树 -> 根

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeTraversal {
    public static void postorderTraversal(TreeNode root) {
        if (root != null) {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.val + " ");
        }
    }

    public static void main(String[] args) {
        // 构建一棵二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 后序遍历
        System.out.println("Postorder Traversal:");
        postorderTraversal(root);
    }
}

4. 层序遍历（Level Order Traversal）

层序遍历按照层次逐层遍历二叉树，从根节点开始，每一层按照从左到右的顺序访问节点。

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeTraversal {
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            System.out.print(current.val + " ");

            if (current.left != null) {
                queue.offer(current.left);
            }

            if (current.right != null) {
                queue.offer(current.right);
            }
        }
    }

    public static void main(String[] args) {
        // 构建一棵二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 层序遍历
        System.out.println("Level Order Traversal:");
        levelOrderTraversal(root);
    }
}

这些遍历方式可以用于对二叉树进行不同类型的操作，例如查找节点、计算树的深度等。

4.3 理解二叉树采用顺序存储结构和链式存储结构的差异性

二叉树可以使用两种不同的存储结构：顺序存储结构和链式存储结构。

1. 顺序存储结构

在顺序存储结构中，使用数组来表示二叉树的节点。二叉树的节点按照某种顺序存储在数组中，可以根据节点在数组中的位置快速找到其父节点、左子节点和右子节点。

特点：

• 使用数组作为存储结构。
• 通过数组下标关系表示节点之间的层次和父子关系。
• 不需要额外的指针，节省存储空间。

缺点：

• 对于非完全二叉树，可能浪费一些数组空间。
• 插入和删除节点操作可能需要移动其他节点，效率较低。

2. 链式存储结构

在链式存储结构中，通过使用节点对象和指针，将节点按照树的层次关系连接在一起。每个节点包含数据和指向左右子节点的指针。

特点：

• 使用节点对象和指针来表示节点之间的关系。
• 可以方便地插入和删除节点，不需要移动其他节点。
• 适用于不规则的树结构，不会浪费空间。

缺点：

• 每个节点需要额外的指针空间，占用更多的存储空间。
• 对于大规模数据的二叉树，可能存在指针的空间开销。

差异性比较

1. 存储结构：

   • 顺序存储结构使用数组。
   • 链式存储结构使用节点对象和指针。

2. 存储方式：

   • 顺序存储结构通过数组下标表示节点关系。
   • 链式存储结构通过指针连接节点。

3. 空间效率：

   • 顺序存储结构可能浪费一些空间，特别是对于非完全二叉树。
   • 链式存储结构对于不规则的树结构更灵活，不会浪费空间。

4. 时间效率：

   • 顺序存储结构的插入和删除操作可能需要移动其他节点，效率较低。
   • 链式存储结构对于插入和删除操作更灵活，效率较高。

选择使用哪种存储结构取决于具体应用场景和需求。如果二叉树的结构较规则且不频繁发生变化，顺序存储结构可能更为合适。如果二叉树结构较为灵活且需要频繁插入和删除操作，链式存储结构可能更适用。

4.4 掌握二叉检索树、Huffman编码以及堆的实现

1. 二叉搜索树（Binary Search Tree，BST）

定义： 二叉搜索树是一种二叉树，其中每个节点的值大于其左子树中的所有节点的值，且小于其右子树中的所有节点的值。

实现要点：

1. 节点的左子树的所有节点值都小于节点的值。
2. 节点的右子树的所有节点值都大于节点的值。
3. 左右子树也分别是二叉搜索树。

Java 代码示例：

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class BinarySearchTree {
    private TreeNode root;

    // 插入节点
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private TreeNode insertRec(TreeNode root, int key) {
        if (root == null) {
            root = new TreeNode(key);
            return root;
        }

        if (key < root.val) {
            root.left = insertRec(root.left, key);
        } else if (key > root.val) {
            root.right = insertRec(root.right, key);
        }

        return root;
    }

    // 中序遍历
    public void inorder() {
        inorderRec(root);
    }

    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.val + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] keys = {50, 30, 20, 40, 70, 60, 80};

        for (int key : keys) {
            bst.insert(key);
        }

        System.out.println("Inorder traversal:");
        bst.inorder();
    }
}

2. Huffman 编码

定义： Huffman 编码是一种压缩算法，通过构建最优二叉树（Huffman 树）来实现对数据的压缩。频率越高的字符对应的编码越短，频率越低的字符对应的编码越长。

实现要点：

1. 构建 Huffman 树。
2. 通过 Huffman 树生成字符的编码。

Java 代码示例：

import java.util.PriorityQueue;

class HuffmanNode implements Comparable<HuffmanNode> {
    char data;
    int frequency;
    HuffmanNode left, right;

    public HuffmanNode(char data, int frequency) {
        this.data = data;
        this.frequency = frequency;
        this.left = this.right = null;
    }

    @Override
    public int compareTo(HuffmanNode node) {
        return this.frequency - node.frequency;
    }
}

public class HuffmanCoding {
    public static void main(String[] args) {
        String input = "hello world";

        // 构建 Huffman 树
        HuffmanNode root = buildHuffmanTree(input);

        // 生成 Huffman 编码
        System.out.println("Huffman Codes:");
        printHuffmanCodes(root, new StringBuilder());
    }

    private static HuffmanNode buildHuffmanTree(String input) {
        // 统计字符频率
        int[] frequency = new int[256];
        for (char ch : input.toCharArray()) {
            frequency[ch]++;
        }

        // 构建最小堆（PriorityQueue）
        PriorityQueue<HuffmanNode> minHeap = new PriorityQueue<>();
        for (char i = 0; i < 256; i++) {
            if (frequency[i] > 0) {
                minHeap.offer(new HuffmanNode(i, frequency[i]));
            }
        }

        // 构建 Huffman 树
        while (minHeap.size() > 1) {
            HuffmanNode left = minHeap.poll();
            HuffmanNode right = minHeap.poll();

            HuffmanNode internalNode = new HuffmanNode('$', left.frequency + right.frequency);
            internalNode.left = left;
            internalNode.right = right;

            minHeap.offer(internalNode);
        }

        return minHeap.poll();  // 返回 Huffman 树的根节点
    }

    private static void printHuffmanCodes(HuffmanNode root, StringBuilder code) {
        if (root == null) {
            return;
        }

        // 叶子节点表示一个字符，打印字符和对应的 Huffman 编码
        if (root.data != '$') {
            System.out.println(root.data + ": " + code);
        }

        // 递归处理左子树
        code.append('0');
        printHuffmanCodes(root.left, code);
        code.deleteCharAt(code.length() - 1);

        // 递归处理右子树
        code.append('1');
        printHuffmanCodes(root.right, code);
        code.deleteCharAt(code.length() - 1);
    }
}

3. 堆的实现

期末试卷中填空题考到了构建二叉检索树，涉及筛选法构建最小堆

public class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity + 1];
    }

    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full. Cannot insert " + value);
            return;
        }

        size++;
        heap[size] = value;
        int current = size;

        // 上移操作，维护堆的性质
        while (current > 1 && heap[current] > heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }

class ForestNode {
    int data;
    ForestNode firstChild; // 指向第一个子节点
    ForestNode nextSibling; // 指向右兄弟节点
}

// 示例：森林的存储
ForestNode tree1 = new ForestNode();
ForestNode tree2 = new ForestNode();

class TreeNode {
    int data;
    TreeNode firstChild; // 指向第一个子节点
    TreeNode nextSibling; // 指向右兄弟节点
}

class BinaryTreeNode {
    int data;
    BinaryTreeNode leftChild; // 左孩子
    BinaryTreeNode rightChild; // 右孩子
}

public class TreeToBinaryTreeConverter {
    public static BinaryTreeNode convertTreeToBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        BinaryTreeNode binaryRoot = new BinaryTreeNode();
        binaryRoot.data = root.data;

        // 将树的子节点转换为二叉树的左孩子
        binaryRoot.leftChild = convertTreeToBinaryTree(root.firstChild);

        // 将树的右兄弟节点转换为二叉树的右孩子
        binaryRoot.rightChild = convertTreeToBinaryTree(root.nextSibling);

        return binaryRoot;
    }
}

class BinaryTreeNode {
    int data;
    BinaryTreeNode leftChild; // 左孩子
    BinaryTreeNode rightChild; // 右孩子
}

class TreeNode {
    int data;
    TreeNode firstChild; // 指向第一个子节点
    TreeNode nextSibling; // 指向右兄弟节点
}

public class BinaryTreeToTreeConverter {
    public static TreeNode convertBinaryTreeToTree(BinaryTreeNode binaryRoot) {
        if (binaryRoot == null) {
            return null;
        }

        TreeNode root = new TreeNode();
        root.data = binaryRoot.data;

        // 将二叉树的左孩子转换为树的第一个子节点
        root.firstChild = convertBinaryTreeToTree(binaryRoot.leftChild);

        // 将二叉树的右孩子转换为树的右兄弟节点
        root.nextSibling = convertBinaryTreeToTree(binaryRoot.rightChild);

        return root;
    }
}

class TreeNode {
    int data;
    TreeNode firstChild; // 指向第一个子节点
    TreeNode nextSibling; // 指向右兄弟节点
}

public class TreeTraversal {
    // 先序遍历树
    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        // 访问根节点
        System.out.print(root.data + " ");

        // 递归遍历子树
        preOrderTraversal(root.firstChild);

        // 递归遍历右兄弟节点
        preOrderTraversal(root.nextSibling);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.data = 1;

        TreeNode child1 = new TreeNode();
        child1.data = 2;

        TreeNode child2 = new TreeNode();
        child2.data = 3;

        root.firstChild = child1;
        child1.nextSibling = child2;

        preOrderTraversal(root);
    }
}

class GraphMatrix {
    private int[][] matrix;

    public GraphMatrix(int n) {
        matrix = new int[n][n];
    }

    public void addEdge(int i, int j) {
        matrix[i][j] = 1;
        matrix[j][i] = 1; // 对于无向图，设置对称位置的元素
    }

    // 其他操作...
}

import java.util.LinkedList;

class GraphList {
    private int V;
    private LinkedList<Integer>[] adjList;

    public GraphList(int V) {
        this.V = V;
        adjList = new LinkedList[V];
        for (int i = 0; i < V; ++i) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int i, int j) {
        adjList[i].add(j);
        adjList[j].add(i); // 对于无向图，添加到两个节点的邻接表中
    }

    // 其他操作...
}

import java.util.LinkedList;
import java.util.Queue;

class Graph {
    private int V; // 节点数量
    private LinkedList<Integer>[] adjList;

    public Graph(int V) {
        this.V = V;
        adjList = new LinkedList[V];
        for (int i = 0; i < V; ++i) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int i, int j) {
        adjList[i].add(j);
        adjList[j].add(i); // 对于无向图，添加到两个节点的邻接表中
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");

            for (int neighbor : adjList[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
}

import java.util.LinkedList;
import java.util.Stack;

class Graph {
    private int V; // 节点数量
    private LinkedList<Integer>[] adjList;

    public Graph(int V) {
        this.V = V;
        adjList = new LinkedList[V];
        for (int i = 0; i < V; ++i) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int i, int j) {
        adjList[i].add(j);
        adjList[j].add(i); // 对于无向图，添加到两个节点的邻接表中
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[V];
        dfsRecursive(start, visited);
    }

    private void dfsRecursive(int current, boolean[] visited) {
        visited[current] = true;
        System.out.print(current + " ");

        for (int neighbor : adjList[current]) {
            if (!visited[neighbor]) {
                dfsRecursive(neighbor, visited);
            }
        }
    }
}

import java.util.Arrays;

class PrimAlgorithm {
    static final int V = 5;

    int minKey(int key[], boolean mstSet[]) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        boolean mstSet[] = new boolean[V];

        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printMST(parent, graph);
    }

    void printMST(int parent[], int graph[][]) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    public static void main(String[] args) {
        PrimAlgorithm t = new PrimAlgorithm();
        int graph[][] = new int[][]{{0, 2, 0, 6, 0},
                                    {2, 0, 3, 8, 5},
                                    {0, 3, 0, 0, 7},
                                    {6, 8, 0, 0, 9},
                                    {0, 5, 7, 9, 0}};

        t.primMST(graph);
    }
}

import java.util.Arrays;

class KruskalAlgorithm {
    class Edge implements Comparable<Edge> {
        int src, dest, weight;

        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    }

    int V, E;
    Edge edge[];

    KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    int find(int parent[], int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }

    void union(int parent[], int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }

    void kruskalMST() {
        Edge result[] = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        Arrays.sort(edge);

        int parent[] = new int[V];
        Arrays.fill(parent, -1);

        i = 0;

        while (e < V - 1) {
            Edge nextEdge = edge[i++];
            int x = find(parent, nextEdge.src);
            int y = find(parent, nextEdge.dest);

            if (x != y) {
                result[e++] = nextEdge;
                union(parent, x, y);
            }
        }

        System.out.println("Edge \tWeight");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " - " + result[i].dest + "\t" + result[i].weight);
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        KruskalAlgorithm graph = new KruskalAlgorithm(V, E);

        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;

        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;

        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;

        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;

        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;

        graph.kruskalMST();
    }
}

import java.util.Arrays;

class DijkstraAlgorithm {
    static final int V = 9;

    int minDistance(int dist[], boolean sptSet[]) {
        int min = Integer.MAX_VALUE, min_index = -1;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        }

        return min_index;
    }

    void printSolution(int dist[]) {
        System.out.println("Vertex \tDistance from Source");
        for (int i = 0;

 i < V; i++)
            System.out.println(i + " \t" + dist[i]);
    }

    void dijkstra(int graph[][], int src) {
        int dist[] = new int[V];
        boolean sptSet[] = new boolean[V];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE &&
                        dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist);
    }

    public static void main(String[] args) {
        int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                    {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                    {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                    {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                    {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                    {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                    {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                    {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                    {0, 0, 2, 0, 0, 0, 6, 7, 0}};

        DijkstraAlgorithm t = new DijkstraAlgorithm();
        t.dijkstra(graph, 0);
    }
}

import java.util.*;

class TopologicalSort {
    private int V;
    private LinkedList<Integer> adj[];

    TopologicalSort(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;
        Integer i;

        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext()) {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        stack.push(v);
    }

    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();

        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);

        System.out.println("Topological Sort:");
        while (!stack.empty())
            System.out.print(stack.pop() + " ");
    }

    public static void main(String args[]) {
        TopologicalSort g = new TopologicalSort(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        g.topologicalSort();
    }
}

(John, 90)
(Jane, 85)
(Bob, 90)
(Alice, 80)

(Alice, 80)
(Jane, 85)
(John, 90)
(Bob, 90)

(Alice, 80)
(Jane, 85)
(Bob, 90)
(John, 90)