柚子快报邀请码778899分享：大数据技术之

柚子快报邀请码778899分享：大数据技术之

http://www.51969.com/

第十九章 Scala语言的数据结构和算法19.1 数据结构(算法)的介绍19.2 看几个实际编程中遇到的问题19.2.1 一个五子棋程序19.2.2 约瑟夫问题(丢手帕问题)19.2.3 其它常见算法问题19.3 稀疏数组 sparsearray19.3.1 基本介绍19.3.2 应用实例19.3.3 课后练习19.4 队列 queue19.4.1 队列的一个使用场景19.4.2 队列介绍19.4.3 数组模拟单向队列19.4.4 数组模拟环形队列19.5 链表 linked list19.5.1 链表介绍19.5.2 单向链表的介绍19.5.3 单向链表的应用实例19.5.4 双向链表的应用实例19.5.5 单向环形链表的应用场景19.6 栈 stack19.6.1 看一个实际需求19.6.2 栈的介绍19.6.3 栈的几个经典的应用场景19.6.4 栈的快速入门19.6.5 栈实现综合计算器19.7 递归 recursive19.7.1 看个实际应用场景19.7.2 递归的概念19.7.3 递归快速入门19.7.4 递归用于解决什么样的问题19.7.5 递归需要遵守的重要原则19.7.6 举一个比较综合的案例-迷宫问题19.8 排序 sort19.8.1 排序的介绍19.8.2 冒泡排序19.8.3 选择排序19.8.4 插入排序19.8.5 快速排序19.8.6 归并排序19.9 查找18.9.1 介绍19.9.2 线性查找19.9.3 二分查找19.10 哈希表(散列表)19.10.1 看一个实际需求19.10.2 哈希表的基本介绍19.10.3 应用实例19.11 二叉树19.11.1 为什么需要树这种数据结构19.11.2 二叉树的示意图19.11.3 二叉树的概念19.11.4 二叉树遍历的说明19.11.5 二叉树遍历应用实例(前序、中序、后序)19.11.6 二叉树-查找指定节点19.11.7 二叉树-删除节点19.12 顺序存储的二叉树19.12.1 顺序存储二叉树的概念19.12.2 顺序存储二叉树的遍历19.13 二叉排序树19.13.1 先看一个需求19.13.2 二叉排序树的介绍19.13.3 二叉排序树的创建和遍历19.13.4 二叉排序树的删除19.14 其它二叉树

第十九章 Scala语言的数据结构和算法

19.1 数据结构(算法)的介绍

数据结构的介绍  1、数据结构是一门研究算法的学科，只从有了编程语言也就有了数据结构。学好数据结构可以编写出更加漂亮、更加有效率的代码。  2、要学习好数据结构就要多多考虑如何将生活中遇到的问题，用程序去实现解决。  3、程序 = 数据结构 + 算法

数据结构和算法的关系  1、算法是程序的灵魂，为什么有些网站能够在高并发，和海量吞吐情况下依然坚如磐石，大家可能会说: 网站使用了服务器群集技术、数据库读写分离和缓存技术(比如 Redis 等)，那如果我再深入的问一句，这些优化技术又是怎样被那些天才的技术高手设计出来的呢？  2、大家请思考一个问题，是什么让不同的人写出的代码从功能看是一样的，但从效率上却有天壤之别, 拿在公司工作的实际经历来说, 我是做服务器的，环境是 UNIX，功能是要支持上千万人同时在线，并保证数据传输的稳定。在服务器上线前，做内测，一切 OK，可上线后，服务器就支撑不住了。公司的 CTO 对我的代码进行优化，再次上线，坚如磐石。那一瞬间，我认识到程序是有灵魂的，就是算法。如果你不想永远都是代码工人，那就花时间来研究下算法吧！  3、本章着重讲解算法的基石-数据结构。

19.2 看几个实际编程中遇到的问题

  试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。示例代码如下：

  def main(args: Array[String]): Unit = {    val str = "scala,scala,hello,world!"    val newStr = str.replaceAll("scala", "尚硅谷")    println("newStr=" + newStr)  }

即：自定义 replaceAll 函数。

19.2.1 一个五子棋程序

如何判断游戏的输赢，并可以完成存盘退出和继续上局的功能。

19.2.2 约瑟夫问题(丢手帕问题)

  Josephu 问题为：设编号为 1，2，…， n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从1开始报数，数到 m 的那个人出列，它的下一位又从1开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。  提示：用一个不带头结点的循环链表来处理 Josephu   问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

19.2.3 其它常见算法问题

邮差问题、最短路径问题、汉诺塔、八皇后问题

19.3 稀疏数组 sparsearray

先看一个实际的需求

19.3.1 基本介绍

  当一个数组中大部分元素为 0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方法是：  1、记录数组一共有几行几列，有多少个不同的值。  2、把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。稀疏数组举例说明

19.3.2 应用实例

  1、使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)。  2、把稀疏数组存盘，并且可以重新恢复原来的二维数组数。  3、整体思路分析如下。

示例代码如下：

package com.atguigu.chapter19.sparsearrayimport scala.collection.mutable.ArrayBufferobject SparseArrayDemo01 {  def main(args: Array[String]): Unit = {    // 演示一个稀疏数组的使用    val rowSize = 11    val colSize = 11    val chessMap = Array.ofDim[Int](rowSize, colSize)    // 初始化棋盘地图    chessMap(1)(2) = 1 // 1 表示黑子    chessMap(2)(3) = 2 // 2 表示白子    println("----------原始的棋盘地图-------------------")    // 输出原始的棋盘地图    for (item1 <- chessMap) { // 行：是一个一维数组      for (item2 <- item1) { // 列        printf("%d\t", item2)      }      println()    }    // 将 chessMap 转成 稀疏数组    // 思路：效果是达到对数据的压缩    // class Node(row, col, value) => ArrayBuffer    val sparseArray = new ArrayBuffer[Node]()    val node = new Node(rowSize, colSize, 0)    sparseArray.append(node)    for (i <- 0 until chessMap.length) {      for (j <- 0 until chessMap(i).length) {        // 判断该值是否为0，如果不为0，就保存        if (chessMap(i)(j) != 0) {          // 就构建一个 Node          val node = new Node(i, j, chessMap(i)(j))          sparseArray.append(node) // 加入到稀疏数组        }      }    }    println("----------输出稀疏数组---------------------")    // 输出稀疏数组    for (node <- sparseArray) {      printf("%d\t%d\t%d\n", node.row, node.col, node.value)    }    // 存盘    // 读盘    // 从稀疏数组恢复原始数据    // 1、读取稀疏数组的第一个节点    val newNode = sparseArray(0)    val newRowSize = newNode.row    val newColSize = newNode.col    val chessMap2 = Array.ofDim[Int](newRowSize, newColSize)    // 遍历稀疏数组    for (i <- 1 until sparseArray.length) {      val node = sparseArray(i)      chessMap2(node.row)(node.col) = node.value    }    println("----------从稀疏数组恢复的棋盘地图----------")    // 输出原始的棋盘地图    for (item1 <- chessMap2) { // 行：是一个一维数组      for (item2 <- item1) { // 列        printf("%d\t", item2)      }      println()    }  }}class Node(val row: Int, val col: Int, val value: Int)

输出结果如下：

----------原始的棋盘地图-------------------0    0   0   0   0   0   0   0   0   0   0   0    0   1   0   0   0   0   0   0   0   0   0    0   0   2   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   ----------输出稀疏数组---------------------11    11  01    2   12    3   2----------从稀疏数组恢复的棋盘地图----------0    0   0   0   0   0   0   0   0   0   0   0    0   1   0   0   0   0   0   0   0   0   0    0   0   2   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0   0

19.3.3 课后练习

要求：  1、在前面的基础上，将稀疏数组保存到磁盘上，比如 map.data。  2、恢复原来的数组时，读取 map.data 进行恢复。

19.4 队列 queue

19.4.1 队列的一个使用场景

银行排队的案例：

19.4.2 队列介绍

  1、队列是一个有序列表，可以用数组或是链表来实现。  2、遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。

19.4.3 数组模拟单向队列

  1、队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下：其中 maxSize 是该队列的最大容量。  2、因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front(或head) 及 rear(或tail) 分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示：

图解说明：当我们将数据存入队列时称为“addqueue”，addqueue 的处理需要有两个步骤：  1、将尾指针往后移：rear + 1，如果 front == rear [表示队列为空]  2、若尾指引 rear 小于等于队列的最大下标 maxSize - 1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1 [表示队列已满]代码实现：

package com.atguigu.chapter19.queueimport scala.io.StdIn/**  * 1、数组模拟单向队列  */object ArrayQueueDemo01 {  def main(args: Array[String]): Unit = {    // 初始化一个队列    val queue = new ArrayQueue(3)    var key = ""    while (true) {      println("show：表示显示队列")      println("exit：表示退出队列")      println("add：表示添加数据到队列")      println("get：表示取出队列的数据")      println("head: 查看队列头的数据(不改变队列)")      key = StdIn.readLine()      key match {        case "show" => queue.showQueue()        case "exit" => System.exit(0)        case "add" => {          println("请输入一个数据(Int类型)：")          val n = StdIn.readInt()          queue.addQueue(n)        }        case "get" => {          val res = queue.getQueue()          if (res.isInstanceOf[Exception]) {            println(res.asInstanceOf[Exception].getMessage)          } else {            println(s"取出对列的数据是 $res")          }        }        case "head" => {          val res = queue.headQueue()          if(res.isInstanceOf[Exception]) {            // 显示错误信息            println(res.asInstanceOf[Exception].getMessage)          }else {            println("队列头元素的值为=" + res)          }        }      }    }  }}// 使用数组模拟单向队列class ArrayQueue(arrMaxSize: Int) {  // 该队列的最大容量  val maxSize = arrMaxSize  // 该数组存放数据，模拟队列  val arr = new Array[Int](maxSize)  // 记录队列前端  var front = -1 // front 是队列最前元素的索引[不含]  // 记录队列后端  var rear = -1 // rear 是队列最后元素的索引[含]  // 判断队列是否已满  def isFull(): Boolean = {    rear == maxSize - 1  }  // 判断队列是否为空  def isEmpty(): Boolean = {    rear == front  }  // 添加数据到队列  def addQueue(n: Int): Unit = {    // 添加数据到队列之前，先判断队列是否已满    if (isFull()) {      println("队列已满，无法添加数据...")      return    }    rear += 1    arr(rear) = n  }  // 获取对列数据  def getQueue(): Any = {    // 获取队列数据之前，先判断队列是否为空    if (isEmpty()) {      return new Exception("对列为空，无法获取对列数据")    }    front += 1    return arr(front)  }  // 显示队列的所有数据  def showQueue(): Unit = {    // 显示队列数据之前，先判断队列是否为空    if (isEmpty()) {      println("队列为空，没有数据可显示...")      return    }    // 遍历队列数据    for (i <- front + 1 to rear) {      printf("arr[%d]=%d\n", i, arr(i))    }  }  // 查看队列的头元素，但是不是改变队列  def headQueue(): Any = {    if (isEmpty()) {      return new Exception("队列为空，没有头元素可查看")    }    // 这里注意，不要去改变 fornt 值    return arr(front + 1)  }}

对上面代码的说明：虽然实现了队列，但是数据空间不能复用，因此我们需要对其进行优化，使用取模的方式实现环形队列。

19.4.4 数组模拟环形队列

说明：  对前面的数组模拟队列的优化，充分利用数组，因此将数组看做是一个环形的。(通过取模的方式来实现即可)分析说明：  1、尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front [表示队列已满]  2、rear == front [表示队列为空]代码实现:

package com.atguigu.chapter19.queueimport scala.io.StdIn/**  * 2、数组模拟环形队列  */object ArrayQueueDemo02 {  def main(args: Array[String]): Unit = {    // 初始化一个队列    val queue = new ArrayQueue(4)    var key = ""    while (true) {      println("show：表示显示队列")      println("exit：表示退出队列")      println("add：表示添加数据到队列")      println("get：表示取出队列的数据")      println("head: 查看队列头的数据(不改变队列)")      key = StdIn.readLine()      key match {        case "show" => queue.showQueue()        case "exit" => System.exit(0)        case "add" => {          println("请输入一个数据(Int类型)：")          val n = StdIn.readInt()          queue.addQueue(n)        }        case "get" => {          val res = queue.getQueue()          if (res.isInstanceOf[Exception]) {            println(res.asInstanceOf[Exception].getMessage)          } else {            println(s"取出对列的数据是 $res")          }        }        case "head" => {          val res = queue.headQueue()          if(res.isInstanceOf[Exception]) {            // 显示错误信息            println(res.asInstanceOf[Exception].getMessage)          }else {            println("队列头元素的值为=" + res)          }        }      }    }  }}// 使用数组模拟环形队列class ArrayQueue(arrMaxSize: Int) {  // 该队列的最大容量  val maxSize = arrMaxSize  // 该数组存放数据，模拟队列  val arr = new Array[Int](maxSize)  // 记录队列前端  var front = 0 // front 是队列最前元素的索引[含]  // 记录队列后端  var rear = 0 // rear 是队列最后元素的索引[含]  // 判断队列是否已满  def isFull(): Boolean = {    // 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意    (rear + 1) % maxSize == front  }  // 判断队列是否为空  def isEmpty(): Boolean = {    rear == front  }  // 添加数据到队列  def addQueue(n: Int): Unit = {    // 添加数据到队列之前，先判断队列是否已满    if (isFull()) {      println("队列已满，无法添加数据...")      return    }    arr(rear) = n    rear = (rear + 1) % maxSize // 将 rear 通过取模的方式后移，注意与 rear = rear + 1 的区别  }  // 获取对列数据  def getQueue(): Any = {    // 获取队列数据之前，先判断队列是否为空    if (isEmpty()) {      return new Exception("对列为空，无法获取对列数据")    }    val value = arr(front)    front = (front + 1) % maxSize // 将 front 通过取模的方式后移，注意与 front = front + 1 的区别    return value  }  // 显示环形队列的所有数据  def showQueue(): Unit = {    // 显示队列数据之前，先判断队列是否为空    if (isEmpty()) {      println("队列为空，没有数据可显示...")      return    }    // 思路：从 front 取，取出几个元素    for (i <- front until front + size()) {      printf("arr[%d]=%d\n", i % maxSize, arr(i % maxSize))    }  }  // 求出当前环形队列有几个元素  def size(): Int = {    // 算法    (rear + maxSize - front) % maxSize  }  // 查看队列的头元素，但是不是改变队列  def headQueue(): Any = {    if (isEmpty()) {      return new Exception("队列为空，没有头元素可查看")    }    // 这里注意，不要去改变 fornt 值    return arr(front)  }}

19.5 链表 linked list

19.5.1 链表介绍

链表是有序的列表，但是它在内存中是存储如下：

小结：  1、链表是一个有序列表。  2、链表的数据，在内存空间不一定是连续分布的。

19.5.2 单向链表的介绍

单向链表(带头结点) 逻辑结构示意图如下：

所谓带头节点，就是链表的头有一个 head 节点，该节点不存放具体的数据，只是为了操作方便而设计的这个节点。

19.5.3 单向链表的应用实例

  使用带 head 头的单向链表实现：水浒英雄排行榜管理。完成对英雄人物的增删改查操作。注：删除、修改和查找可以考虑学员独立完成。

第一种方式：在添加英雄时，直接添加到链表的尾部。思路分析：

代码实现：示例代码如下：

package com.atguigu.chapter19.linkedlistimport util.control.Breaks._/**  * 1、无序插入单向链表节点，即 在添加英雄时，直接添加到链表的尾部。  */object SingleLinkedListDemo01 {  def main(args: Array[String]): Unit = {    // 测试单向链表的添加和遍历    val heroNode1 = new HeroNode(1, "宋江", "及时雨")    val heroNode3 = new HeroNode(3, "吴用", "智多星")    val heroNode4 = new HeroNode(4, "公孙胜", "入云龙")    val heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟")    // 创建一个单向链表    val singleLinkedList = new SingleLinkedList    // 添加英雄    singleLinkedList.add(heroNode1)    singleLinkedList.add(heroNode3)    singleLinkedList.add(heroNode4)    singleLinkedList.add(heroNode2)    // 遍历英雄    singleLinkedList.list()  }}// 定义单向链表，用来管理 Heroclass SingleLinkedList {  // 先初始化一个头结点，头结点一般不用  val head = new HeroNode(0, "", "")  // 编写添加英雄的方法  // 第一种方式：在添加英雄时，直接添加到链表的尾部。  def add(heroNode: HeroNode): Unit = {    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助，即使用 temp 也指向 new HeroNode(0, "", "") 的地址    var temp = head    // 先找到该链表的最后    breakable {      while (true) {        if (temp.next == null) {          break()        }        // 如果没有到链表最后，接着找        temp = temp.next      }    }    // 当退出 while 循环后，temp 指向的就是链表的最后    temp.next = heroNode // 在链表的最后将 英雄对象的地址 赋值给 temp  }  // 遍历单向链表  def list(): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空！")      return    }    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助    // 又因为 head 节点的数据我们不关心，因此这里使得 temp 指向 head 的下一个地址（我们真正的数据）    var temp = head.next    breakable {      while (true) {        if (temp == null) {          break()        }        printf("节点信息：no=%d name=%s nickname=%s\n", temp.no, temp.name, temp.nickname)        temp = temp.next      }    }  }}// 先创建 HeroNodeclass HeroNode(hNo: Int, hName: String, hNickname: String) {  var no: Int = hNo  var name: String = hName  var nickname: String = hNickname  var next: HeroNode = null // next 默认为 null}

输出结果如下：

节点信息：no=1 name=宋江 nickname=及时雨节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙节点信息：no=2 name=卢俊义 nickname=玉麒麟

第二种方式：在添加英雄时，根据排名将英雄插入到指定位置。

示例代码如下：

package com.atguigu.chapter19.linkedlistimport util.control.Breaks._/**  * 2、有序插入单向链表节点，即 在添加英雄时，根据排名将英雄插入到指定位置。(如果有这个排名，则添加失败，并给出提示)  */object SingleLinkedListDemo02 {  def main(args: Array[String]): Unit = {    // 测试单向链表的添加和遍历    val heroNode1 = new HeroNode2(1, "宋江", "及时雨")    val heroNode3 = new HeroNode2(3, "吴用", "智多星")    val heroNode4 = new HeroNode2(4, "公孙胜", "入云龙")    val heroNode2 = new HeroNode2(2, "卢俊义", "玉麒麟")    // 创建一个单向链表    val singleLinkedList2 = new SingleLinkedList2    // 添加英雄    singleLinkedList2.add(heroNode1)    singleLinkedList2.add(heroNode3)    singleLinkedList2.add(heroNode4)    singleLinkedList2.add(heroNode2)    // 遍历英雄    singleLinkedList2.list()  }}// 定义单向链表，用来管理 Heroclass SingleLinkedList2 {  // 先初始化一个头结点，头结点一般不用  val head = new HeroNode2(0, "", "")  // 编写添加英雄的方法  // 第二种方式：在添加英雄时，根据排名将英雄插入到指定位置。(如果有这个排名，则添加失败，并给出提示)  def add(heroNode: HeroNode2): Unit = {    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助，即使用 temp 也指向 new HeroNode2(0, "", "") 的地址    // 注意：我们在找这个添加位置时，是将这个节点加入到节点 temp 的后面    // 因此，在比较时，是将当前的节点 heroNode 和节点 temp.next 比较    var temp = head    var flag = false // flag 用于判断该英雄的编号是否已存在    breakable {      while (true) {        if (temp.next == null) { // 说明节点 temp 已经是链表的最后          break()        }        if (heroNode.no < temp.next.no) { // 说明位置找到，当前这个节点 heroNode 应加入到 节点 temp 的后面，节点 temp.next 的前面          break()        } else if (heroNode.no == temp.next.no) { // 说明已经有该节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) { //      printf("待添加的英雄编号 %d 已经存在，不能加入\n", heroNode.no)    } else {      // 加入英雄，注意：添加顺序      heroNode.next = temp.next      temp.next = heroNode    }  }  // 遍历单向链表  def list(): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空！")      return    }    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助    // 又因为 head 节点的数据我们不关心，因此这里使得 temp 指向 head 的下一个地址（我们真正的数据）    var temp = head.next    breakable {      while (true) {        if (temp == null) {          break()        }        printf("节点信息：no=%d name=%s nickname=%s\n", temp.no, temp.name, temp.nickname)        temp = temp.next      }    }  }}// 先创建 HeroNode2class HeroNode2(hNo: Int, hName: String, hNickname: String) {  var no: Int = hNo  var name: String = hName  var nickname: String = hNickname  var next: HeroNode2 = null // next 默认为 null}

输出结果如下：

节点信息：no=1 name=宋江 nickname=及时雨节点信息：no=2 name=卢俊义 nickname=玉麒麟节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙

练习：  1、修改节点的值，根据编号的值进行修改（即编号不能变）  2、将整个节点替换（即重新指向）  3、删除节点（根据编号删除）

示例代码如下：

package com.atguigu.chapter19.linkedlistimport util.control.Breaks._/**  * 2、有序插入单向链表节点，即 在添加英雄时，根据排名将英雄插入到指定位置。(如果有这个排名，则添加失败，并给出提示)  */object SingleLinkedListDemo02 {  def main(args: Array[String]): Unit = {    // 测试单向链表的添加和遍历    val heroNode1 = new HeroNode2(1, "宋江", "及时雨")    val heroNode3 = new HeroNode2(3, "吴用", "智多星")    val heroNode4 = new HeroNode2(4, "公孙胜", "入云龙")    val heroNode2 = new HeroNode2(2, "卢俊义", "玉麒麟")    // 创建一个单向链表    val singleLinkedList2 = new SingleLinkedList2    println("----------添加节点（有序添加）----------------")    // 添加英雄    singleLinkedList2.add(heroNode1)    singleLinkedList2.add(heroNode3)    singleLinkedList2.add(heroNode4)    singleLinkedList2.add(heroNode2)    // 遍历英雄    singleLinkedList2.list()    println("----------修改节点的值-----------------------")    // 修改节点的值    val heroNode5 = new HeroNode2(1, "宋公明", "山东及时雨")    singleLinkedList2.update(heroNode5)    // 遍历英雄    singleLinkedList2.list()    println("----------修改节点的值（全部替换）------------")    // 修改节点的值（全部替换）    val heroNode6 = new HeroNode2(2, "卢员外", "河北玉麒麟")    singleLinkedList2.update2(heroNode6)    // 遍历英雄    singleLinkedList2.list()    println("----------删除节点--------------------------")    // 删除节点    singleLinkedList2.del(4)    // 遍历英雄    singleLinkedList2.list()  }}// 定义单向链表，用来管理 Heroclass SingleLinkedList2 {  // 先初始化一个头结点，头结点一般不用  val head = new HeroNode2(0, "", "")  // 删除节点（根据编号删除）  def del(no: Int): Unit = {    var temp = head    var flag = false    breakable {      while (true) {        if (temp.next == null) {          break()        }        if (temp.next.no == no) { // 找到节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) {      // 删除节点      temp.next = temp.next.next    } else {      printf("要删除的 no=%d 节点不存在\n", no)    }  }  // 将整个节点替换（即重新指向）  def update2(heroNode: HeroNode2): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空，不能修改！")      return    }    // 先找到节点    var temp = head.next    var flag = false    breakable {      while (true) {        if (temp == null) { // 没有找到节点          break()        }        if (temp.no == heroNode.no) { // 找到节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) {      del(temp.no)      add(heroNode)    } else {      printf("没有找到编号为 %d 的节点，不能修改！\n", heroNode.no)    }  }  // 修改节点的值，根据编号的值进行修改（即编号不能变）  def update(heroNode: HeroNode2): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空，不能修改！")      return    }    // 先找到节点    var temp = head.next    var flag = false    breakable {      while (true) {        if (temp == null) { // 没有找到节点          break()        }        if (temp.no == heroNode.no) { // 找到节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) {      temp.name = heroNode.name      temp.nickname = heroNode.nickname    } else {      printf("没有找到编号为 %d 的节点，不能修改！\n", heroNode.no)    }  }  // 编写添加英雄的方法  // 第二种方式：在添加英雄时，根据排名将英雄插入到指定位置。(如果有这个排名，则添加失败，并给出提示)  def add(heroNode: HeroNode2): Unit = {    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助，即使用 temp 也指向 new HeroNode2(0, "", "") 的地址    // 注意：我们在找这个添加位置时，是将这个节点加入到节点 temp 的后面    // 因此，在比较时，是将当前的节点 heroNode 和节点 temp.next 比较    var temp = head    var flag = false // flag 用于判断该英雄的编号是否已存在    breakable {      while (true) {        if (temp.next == null) { // 说明节点 temp 已经是链表的最后          break()        }        if (heroNode.no < temp.next.no) { // 说明位置找到，当前这个节点 heroNode 应加入到 节点 temp 的后面，节点 temp.next 的前面          break()        } else if (heroNode.no == temp.next.no) { // 说明已经有该节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) { //      printf("待添加的英雄编号 %d 已经存在，不能加入\n", heroNode.no)    } else {      // 加入英雄，注意：添加顺序      heroNode.next = temp.next      temp.next = heroNode    }  }  // 遍历单向链表  def list(): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空！")      return    }    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助    // 又因为 head 节点的数据我们不关心，因此这里使得 temp 指向 head 的下一个地址（我们真正的数据）    var temp = head.next    breakable {      while (true) {        if (temp == null) {          break()        }        printf("节点信息：no=%d name=%s nickname=%s\n", temp.no, temp.name, temp.nickname)        temp = temp.next      }    }  }}// 先创建 HeroNode2class HeroNode2(hNo: Int, hName: String, hNickname: String) {  var no: Int = hNo  var name: String = hName  var nickname: String = hNickname  var next: HeroNode2 = null // next 默认为 null}

输出结果如下：

----------添加节点（有序添加）----------------节点信息：no=1 name=宋江 nickname=及时雨节点信息：no=2 name=卢俊义 nickname=玉麒麟节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙----------修改节点的值-----------------------节点信息：no=1 name=宋公明 nickname=山东及时雨节点信息：no=2 name=卢俊义 nickname=玉麒麟节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙----------修改节点的值（全部替换）------------节点信息：no=1 name=宋公明 nickname=山东及时雨节点信息：no=2 name=卢员外 nickname=河北玉麒麟节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙----------删除节点--------------------------节点信息：no=1 name=宋公明 nickname=山东及时雨节点信息：no=2 name=卢员外 nickname=河北玉麒麟节点信息：no=3 name=吴用 nickname=智多星

19.5.4 双向链表的应用实例

  使用带 head 头的双向链表实现：水浒英雄排行榜管理。

单向链表的缺点分析:  1、单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。  2、单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp 的下一个节点来删除的(认真体会)。  3、示意图帮助理解删除。

将前面的单向链表改成双向链表双向链表删除图解

示例代码如下：

package com.atguigu.chapter19.linkedlistimport util.control.Breaks.{break, breakable}/**  * 双向链表  */object DoubleLinkedListDemo01 {  def main(args: Array[String]): Unit = {    // 测试双向链表的添加和遍历    println("----------添加节点（无序添加）----------------")    val heroNode1 = new HeroNode3(1, "宋江", "及时雨")    val heroNode3 = new HeroNode3(3, "吴用", "智多星")    val heroNode4 = new HeroNode3(4, "公孙胜", "入云龙")    val heroNode2 = new HeroNode3(2, "卢俊义", "玉麒麟")    // 创建一个双向链表    val doubleLinkedList = new DoubleLinkedList    // 添加英雄    doubleLinkedList.add(heroNode1)    doubleLinkedList.add(heroNode3)    doubleLinkedList.add(heroNode4)    doubleLinkedList.add(heroNode2)    // 遍历英雄    doubleLinkedList.list()    println("----------修改节点的值-----------------------")    // 修改节点的值    val heroNode5 = new HeroNode3(1, "宋公明", "山东及时雨")    doubleLinkedList.update(heroNode5)    // 遍历英雄    doubleLinkedList.list()    println("----------删除节点--------------------------")    // 删除节点    doubleLinkedList.del(2)    doubleLinkedList.del(3)    doubleLinkedList.del(4)    // 遍历英雄    doubleLinkedList.list()    println("----------再次添加节点----------------------")    doubleLinkedList.add(heroNode3)    // 遍历英雄    doubleLinkedList.list()  }}// 定义双向链表，用来管理 Heroclass DoubleLinkedList {  // 先初始化一个头结点，头结点一般不用（不会动）  val head = new HeroNode3(0, "", "")  // 添加-遍历-修改-删除  // 编写添加英雄的方法  // 第一种方式：在添加英雄时，直接添加到链表的尾部。  def add(heroNode: HeroNode3): Unit = {    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助，即使用 temp 也指向 new HeroNode3(0, "", "") 的地址    var temp = head    // 先找到该链表的最后    breakable {      while (true) {        if (temp.next == null) {          break()        }        // 如果没有到链表最后，接着找        temp = temp.next      }    }    // 当退出 while 循环后，temp 指向的就是链表的最后    temp.next = heroNode // 在链表的最后将 英雄对象的地址 赋值给 temp    heroNode.pre = temp  }  // 遍历双向链表  def list(): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空！")      return    }    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助    // 又因为 head 节点的数据我们不关心，因此这里使得 temp 指向 head 的下一个地址（我们真正的数据）    var temp = head.next    breakable {      while (true) {        // 判断是否到最后        if (temp == null) {          break()        }        printf("节点信息：no=%d name=%s nickname=%s\n", temp.no, temp.name, temp.nickname)        temp = temp.next      }    }  }  // 修改节点的值，根据编号的值进行修改（即编号不能变）  def update(heroNode: HeroNode3): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空，不能修改！")      return    }    // 先找到节点    var temp = head.next    var flag = false    breakable {      while (true) {        if (temp == null) { // 没有找到节点          break()        }        if (temp.no == heroNode.no) { // 找到节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) {      temp.name = heroNode.name      temp.nickname = heroNode.nickname    } else {      printf("没有找到编号为 %d 的节点，不能修改！\n", heroNode.no)    }  }  // 删除节点（根据编号删除）  // 利用双向链表可以实现自我删除的特点  def del(no: Int): Unit = {    // 先判断当前列表是否为空    if (head.next == null) {      println("链表为空，不能删除！")      return    }    // 辅助节点    var temp = head.next    var flag = false    breakable {      while (true) {        if (temp == null) {          break()        }        if (temp.no == no) { // 找到节点          flag = true          break()        }        temp = temp.next      }    }    if (flag) {      // 删除节点      temp.pre.next = temp.next      if (temp.next != null) {        temp.next.pre = temp.pre        temp.pre = null        temp.next = null      } else {        temp.pre = null      }    } else {      printf("要删除的 no=%d 节点不存在\n", no)    }  }}// 先创建 HeroNode3class HeroNode3(hNo: Int, hName: String, hNickname: String) {  var no: Int = hNo  var name: String = hName  var nickname: String = hNickname  var pre: HeroNode3 = null // pre 默认为 null  var next: HeroNode3 = null // next 默认为 null}

输出结果如下：

----------添加节点（无序添加）----------------节点信息：no=1 name=宋江 nickname=及时雨节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙节点信息：no=2 name=卢俊义 nickname=玉麒麟----------修改节点的值-----------------------节点信息：no=1 name=宋公明 nickname=山东及时雨节点信息：no=3 name=吴用 nickname=智多星节点信息：no=4 name=公孙胜 nickname=入云龙节点信息：no=2 name=卢俊义 nickname=玉麒麟----------删除节点--------------------------节点信息：no=1 name=宋公明 nickname=山东及时雨----------再次添加节点----------------------节点信息：no=1 name=宋公明 nickname=山东及时雨节点信息：no=3 name=吴用 nickname=智多星

19.5.5 单向环形链表的应用场景

  Josephu 问题(丢手帕问题)：设编号为1，2，…，n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。  提示：用一个不带头结点的循环链表来处理 Josephu 问题。  问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。  示意图说明：

思路分析：示例代码如下：

package com.atguigu.chapter19.linkedlistimport util.control.Breaks._object JosephuDemo {  def main(args: Array[String]): Unit = {    // 创建一个双向链表 BoyGame    val boyGame = new BoyGame    boyGame.addBoy(7)    boyGame.showBoy()    println("--------------------")    boyGame.countBoy(4, 3, 7)  }}// 定义单向链表，用来管理 Boyclass BoyGame {  // 先初始化一个头结点，头结点一般不用（不会动）  var first: Boy = null  // 添加 Boy，形成一个单向环形链表  // nums 表示共有几个小孩  def addBoy(nums: Int): Unit = {    if (nums < 1) {      println("Boy的个数不正确")      return    }    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助，只是该辅助节点的指向是null，即是一个没有指向任何地址的指针    var temp: Boy = null    for (no <- 1 to nums) {      // 根据编号创建 Boy 对象      val boy = new Boy(no)      // 如果是第一个 Boy，则自己指向自己，并将 temp 也指向 第一个 Boy      if (no == 1) {        first = boy        boy.next = first        temp = first // 辅助指针指向到 第一个 Boy，即 first      } else {        temp.next = boy // 辅助指针指向 当前的 Boy        boy.next = first // 当前的 Boy 指向 第一个 Boy        temp = boy // 辅助指针指向下一个 Boy      }    }  }  // 遍历单向环形链表  def showBoy(): Unit = {    if (first.next == null) {      println("没有Boy")      return    }    // 因为头结点不能动，因此我们需要有一个临时节点作为辅助    // 又因为 first 节点的数据跟我们有关，因此这里使得 temp 指向 first 的地址    var temp = first    breakable {      while (true) {        printf("Boy 的编号是 %d\n", temp.no)        if (temp.next == first) {          break()        }        temp = temp.next // 移动指针到下一个 Boy      }    }  }  // 编写 countBoy  // startNo 从第几个人开始数  // countNum 数几下  // nums 总人数  def countBoy(startNo: Int, countNum: Int, nums: Int): Unit = {    // 对参数进行判断    if (first.next == null || startNo < 1 || startNo > nums) {      println("参数有误，请重新输入！")      return    }    // 思路：    // 1、在 first 前面设计一个辅助指针 temp，即将 temp 指针定位到 first 前面    var temp = first // 辅助指针    breakable {      while (true) { // 遍历一圈单向环形链表后，找到指针 first 的前一个位置，此时是 新temp        if (temp.next == first) {          break()        }        temp = temp.next // 移动指针      }    }    // 2、将 first 指针移动到 startNo 位置，将 temp 指针移动到 startNo - 1 位置    for (i <- 1 until startNo) {      first = first.next      temp = temp.next    }    breakable {      while (true) {        if (temp == first) {          break()        }        // 3、开始数 countNum 个位置， first 和 temp 指针对应移动        for (i <- 1 until countNum) {          first = first.next          temp = temp.next        }        printf("Boy %d 号出圈\n", first.no)        // 4、删除 first 指向的节点，并移动 first 指针到下一节点，temp 指针对应移动        // first = first.next        temp.next = first.next        first = first.next      }    }    // while 循环结束后，只有一个人了    printf("最后一个人是Boy %d 号", first.no)  }}// 定义 Boy 类class Boy(bNo: Int) {  var no: Int = bNo  var next: Boy = null}

输出结果如下：

Boy 的编号是 1Boy 的编号是 2Boy 的编号是 3Boy 的编号是 4Boy 的编号是 5Boy 的编号是 6Boy 的编号是 7--------------------Boy 6 号出圈Boy 2 号出圈Boy 5 号出圈Boy 3 号出圈Boy 1 号出圈Boy 4 号出圈最后一个人是Boy 7 号

19.6 栈 stack

19.6.1 看一个实际需求

请输入一个表达式计算式：[722-5+1-5+3-3] 点击计算，[如下图]

请问：计算机底层是如何运算得到结果的？ 注意：不是简单的把算式列出运算，因为我们看这个算式 7 * 2 * 2 - 5， 但是计算机怎么理解这个算式的（对计算机而言，它接收到的就是一个字符串），我们讨论的是这个问题。

19.6.2 栈的介绍

  1、栈的英文为(stack)。  2、栈是一个先入后出(FILO:First In Last Out)的有序列表。  3、栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。  4、根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

出栈和入栈的概念(如图所示)入栈

出栈

19.6.3 栈的几个经典的应用场景

  1、子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。  2、处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。  3、表达式的转换与求值(实际解决)。  4、二叉树的遍历。  5、图形的深度优先(depth-first)搜索法。

19.6.4 栈的快速入门

用数组模拟栈的使用 由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈、入栈等操作。实现思路分析，并画出示意图，如下：

示例代码如下：

package com.atguigu.chapter19.stackimport scala.io.StdIn/**  * 1、用数组模拟栈的使用  */object ArrayStackDemo01 {  def main(args: Array[String]): Unit = {    // 测试栈的基本使用    val arrayStack = new ArrayStack(3)    var key = ""    while (true) {      println("list：表示显示栈的数据")      println("exit：表示退出程序")      println("push：表示将数据压栈")      println("pop：表示将数据弹栈")      key = StdIn.readLine()      key match {        case "list" => arrayStack.list()        case "exit" => System.exit(0)        case "push" => {          print("请输入一个数据(Int类型)：")          val n = StdIn.readInt()          arrayStack.push(n)        }        case "pop" => arrayStack.pop()      }    }  }}// 用数组模拟栈的使用class ArrayStack(size: Int) {  // 栈的大小  val maxSize = size  var stack = new Array[Int](maxSize)  // 栈顶，初始化为 -1  var top = -1  // 判断是否栈满  def isFull(): Boolean = {    top == maxSize - 1  }  // 判断是否栈空  def isEmpty(): Boolean = {    top == -1  }  // 将数据压入栈的方法  def push(value: Int): Unit = {    if (isFull()) {      println("栈满，不能再存放数据")      return    }    top += 1    stack(top) = value  }  // 将数据弹出栈的方法  def pop(): Any = {    if (isEmpty()) {      println("栈空，不能再取出数据")      return    }    val value = stack(top)    top -= 1    return value  }  // 遍历栈（从栈顶往下取出）  def list(): Unit = {    if (isEmpty()) {      println("栈空，没有数据可显示")      return    }    for (i <- 0 to top reverse) {      printf("stack[%d]=%d\n", i, stack(i))    }  }}

使用链表来模拟栈的使用有空做做

19.6.5 栈实现综合计算器

代码实现的思路分析

示例代码如下：

package com.atguigu.chapter19.stackimport util.control.Breaks._/**  * 2、完成多位数表达式的计算，例如：30+2*6-2   7*2*2-5+1-5+3-4  */object CalculatorDemo02 {  def main(args: Array[String]): Unit = {    // 数值栈    val numStack = new ArrayStack3(20)    // 符号栈    val operStack = new ArrayStack3(20)    /*    expression = "3+2*6-2"    思路：    1、设计两个栈：数值栈，符号栈    2、对 expresson 进行扫描，一个一个的取出    3、当取出的字符是数值时，就直接入数值栈    4、当取出的字符是符号时：      4.1 如果当前符号栈中没有数据，就直接入栈      4.2 如果当前符号的优先级小于等于符号栈的栈顶的符号的优先级，          则pop出该符号，并从数值栈中一次弹出两个数据，进行运算，          将结果重新push到数值栈，再将当前符号push到符号栈      4.3 反之直接入符号栈    5、当整个表达式扫描完毕后，依次从数值栈和符号栈中取出数据，       进行运算，最后在数值栈中的数据就是结果     */    // val expression = "30+2*6-2"    val expression = "7*2*2-5+1-5+3-4"    var index = 0    var num1 = 0    var num2 = 0    var oper = 0    var res = 0    var char = ' '    var keepNum = "" // 在进行扫描时，保存上次的数字char，并进行拼接    // 循环的取出 expression 的字符    breakable {      while (true) {        // 1、设计两个栈：数值栈，符号栈        // 2、对 expresson 进行扫描，一个一个的取出        char = (expression.substring(index, index + 1)) (0)        if (operStack.isOper(char)) { // 如果当前符号是一个操作符          if (!operStack.isEmpty()) { // 如果当前符号栈中有数据            // 当前符号的优先级小于等于符号栈的栈顶的符号的优先级            if (operStack.priority(char) <= operStack.priority(operStack.stack(operStack.top))) {              // 开始计算              num1 = numStack.pop().toString.toInt              num2 = numStack.pop().toString.toInt              oper = operStack.pop().toString.toInt              res = numStack.cal(num1, num2, oper)              // 将计算的结果入数值栈              numStack.push(res)              // 将操作符压入符号栈              operStack.push(char)            } else {              // 反之直接入符号栈              operStack.push(char)            }          } else {            operStack.push(char)          }        } else { // 是一个数          // 处理多位数的逻辑          keepNum += char          // 如果 char 已经是 expression 的最后一个字符，则该数直接入栈          if (index == expression.length - 1) {            numStack.push(keepNum.toInt)          } else {            // 判断 char 的下一个字符是不是数字，如果是数字，则进行下一次扫描，如果是操作符，就该数直接入栈            if (operStack.isOper(expression.substring(index + 1, index + 2)(0))) { // 是操作符，就该数直接入栈              numStack.push(keepNum.toInt)              keepNum = "" // 清空            }          }          // numStack.push(char - 48) // '1' => 49          // numStack.push((char + "").toInt)        }        // index 后移        index += 1        if (index >= expression.length) {          break()        }      }    }    // 5、当整个表达式扫描完毕后，依次从数值栈和符号栈中取出数据，进行运算，最后在数值栈中的数据就是结果    breakable {      while (true) {        if (operStack.isEmpty()) {          break()        }        // 开始计算        num1 = numStack.pop().toString.toInt        num2 = numStack.pop().toString.toInt        oper = operStack.pop().toString.toInt        res = numStack.cal(num1, num2, oper)        // 将计算的结果入数值栈        numStack.push(res)      }    }    printf("表达式： %s = %d", expression, numStack.pop().toString.toInt)  }}// 用数组模拟栈的使用，该栈已经测试过了，可以使用class ArrayStack3(size: Int) {  // 栈的大小  val maxSize = size  var stack = new Array[Int](maxSize)  // 栈顶，初始化为 -1  var top = -1  // 判断是否栈满  def isFull(): Boolean = {    top == maxSize - 1  }  // 判断是否栈空  def isEmpty(): Boolean = {    top == -1  }  // 将数据压入栈的方法  def push(value: Int): Unit = {    if (isFull()) {      println("栈满，不能再存放数据")      return    }    top += 1    stack(top) = value  }  // 将数据弹出栈的方法  def pop(): Any = {    if (isEmpty()) {      println("栈空，不能再取出数据")      return    }    val value = stack(top)    top -= 1    return value  }  // 遍历栈（从栈顶往下取出）  def list(): Unit = {    if (isEmpty()) {      println("栈空，没有数据可显示")      return    }    for (i <- 0 to top reverse) {      printf("stack[%d]=%d\n", i, stack(i))    }  }  // 自定义运算符的优先级，这里我们先简单定义下符号的优先级  // +- => 0    * / => 1    数字越大优先级越高  def priority(oper: Int): Int = {    if (oper == '*' || oper == '/') {      return 1    } else if (oper == '+' || oper == '-') {      return 0    } else {      return -1 // 运算符不正确    }  }  // 判断是否是一个操作符（即符号）  def isOper(value: Int): Boolean = {    value == '+' || value == '-' || value == '*' || value == '/'  }  // 计算的方法，这里我们仅考虑整数的计算  def cal(num1: Int, num2: Int, oper: Int): Int = {    var res = 0    oper match {      case '+' => res = num2 + num1      case '-' => res = num2 - num1      case '*' => res = num2 * num1      case '/' => res = num2 / num1    }    res  }}

输出结果如下：

表达式： 7*2*2-5+1-5+3-4 = 18

19.7 递归 recursive

19.7.1 看个实际应用场景

迷宫问题(回溯)

19.7.2 递归的概念

简单的说：递归就是函数/方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

19.7.3 递归快速入门

我列举两个小案例,来帮助大家理解递归，递归在讲函数时已经讲过(当时讲的相对比较简单)，这里在给大家回顾一下递归调用机制  1、打印问题  2、阶乘问题思路分析

  if (5 > 2) {    if (4 > 2) {      if (3 > 2) {        if (2 > 2) {        }        println("n=" + 2)      }      println("n=" + 3)    }    println("n=" + 4)  }  println("n=" + 5)

打印代码如下：

package com.atguigu.chapter19.recursiveobject Demo01 {  def main(args: Array[String]): Unit = {    test1(5)    println("----------")    test2(5)    println("----------")    test3(5)  }  def test1(n: Int): Unit = {    if (n > 2) {      test1(n - 1)    }    println("n=" + n)  }  def test2(n: Int): Unit = {    println("n=" + n)    if (n > 2) {      test2(n - 1)    }  }  def test3(n: Int): Unit = {    if (n > 2) {      test3(n - 1)      println("n=" + n)    }  }}

输出结果如下：

n=2n=3n=4n=5----------n=5n=4n=3n=2----------n=3n=4n=5

求阶乘代码如下：

package com.atguigu.chapter19.recursiveobject Demo02 {  def main(args: Array[String]): Unit = {      println(factorial(3))  }  // 阶乘  def factorial(n: Int): Int = {    if (n == 1) {      1    } else {      factorial(n - 1) * n    }  }}

输出结果如下：

6

19.7.4 递归用于解决什么样的问题

  1、各种数学问题如: 8 皇后问题、汉诺塔、阶乘问题、迷宫问题、球和篮子的问题(google 编程大赛，有空看看)  2、将用栈解决的问题 -> 递归代码比较简洁

19.7.5 递归需要遵守的重要原则

  1、执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)。  2、函数的局部变量是独立的，不会相互影响。  3、递归必须向退出递归的条件逼近，否则就是无限递归，死龟了:)。  4、当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁。

19.7.6 举一个比较综合的案例-迷宫问题

解释说明  1、小球得到的路径，和程序员设置的找路策略有关，即：找路的上下左右的顺序相关。  2、再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化。  3、测试回溯现象。  4、思考: 如何求出最短路径？

思路分析

代码实现

package com.atguigu.chapter19.recursive/**  * 迷宫问题思路分析：  * 1、创建一个二维数组（表示地图）  * 2、约定元素的值：0表示可以走还没有走，1表示墙，2表示可以走，3表示已经走过，但是是死路。  * 3、确定一个策略：下->右->上->左  * 4、代码  */object MiGongDemo01 {  def main(args: Array[String]): Unit = {    // 创建地图    val map = Array.ofDim[Int](8, 7)    // 上下全部置1，1表示墙    for (i <- 0 until 7) {      map(0)(i) = 1      map(7)(i) = 1    }    // 左右全部置1，1表示墙    for (i <- 0 until 8) {      map(i)(0) = 1      map(i)(6) = 1    }    map(3)(1) = 1    map(3)(2) = 1    // 打印地图    for (i <- 0 until 8) {      for (j <- 0 until 7) {        print(map(i)(j) + " ")      }      println()    }/*    println("----------策略为：下->右->上->左----------")    // 测试递归回溯方法    findWay1(map, 1, 1)    // 打印地图    for (i <- 0 until 8) {      for (j <- 0 until 7) {        print(map(i)(j) + " ")      }      println()    }*/    println("----------策略为：上->右->下->左----------")    // 测试递归回溯方法    findWay2(map, 1, 1)    // 打印地图    for (i <- 0 until 8) {      for (j <- 0 until 7) {        print(map(i)(j) + " ")      }      println()    }    // 使用递归回溯来找路，确定一个策略为：下->右->上->左    // map 表示地图，i j 是指定从地图的哪个点开始出发，测试的时候我们指定为 (1, 1)    def findWay1(map: Array[Array[Int]], i: Int, j: Int): Boolean = {      if (map(6)(5) == 2) { // 表示路已经通了        return true      } else {        if (map(i)(j) == 0) { // 0表示可以走还没有走          // 开始递归回溯（试探性判断）          map(i)(j) = 2 // 先假定该点(1, 1)可以走通          if (findWay1(map, i + 1, j)) { // 先向下找，可以走通            return true          } else if (findWay1(map, i, j + 1)) { // 先向下找，不可以走通，则向右找，可以走通            return true          } else if (findWay1(map, i - 1, j)) { // 先向下找，不可以走通，则向右找，不可以走通，则向上找，可以走通            return true          } else if (findWay1(map, i, j - 1)) { // 向 下 右 上 不可以走通，则向左走，可以走通            return true          } else { // 都不可以走通            map(i)(j) = 3            return false          }        } else { // map(i)(j) == 1或者2或者3          return false        }      }    }    // 使用递归回溯来找路，确定一个新的策略为：上->右->下->左    // map 表示地图，i j 是指定从地图的哪个点开始出发，测试的时候我们指定为 (1, 1)    def findWay2(map: Array[Array[Int]], i: Int, j: Int): Boolean = {      if (map(6)(5) == 2) { // 表示路已经通了        return true      } else {        if (map(i)(j) == 0) { // 0表示可以走还没有走          // 开始递归回溯（试探性判断）          map(i)(j) = 2 // 先假定该点可以走通          if (findWay2(map, i - 1, j)) { // 先向上找，可以走通            return true          } else if (findWay2(map, i, j + 1)) { // 先向上找，不可以走通，则向右找，可以走通            return true          } else if (findWay2(map, i + 1, j)) { // 先上找，不可以走通，则向右找，不可以走通，则向下找，可以走通            return true          } else if (findWay2(map, i, j - 1)) { // 向 上 右 下 不可以走通，则向左走，可以走通            return true          } else { // 都不可以走通            map(i)(j) = 3            return false          }        } else { // map(i)(j) == 1或者2或者3          return false        }      }    }  }}

输出结果如下：

1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 ----------策略为：上->右->下->左----------1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 0 0 0 0 2 1 1 1 1 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 1 1 1 1 1 1

19.8 排序 sort

19.8.1 排序的介绍

排序是将一组数据，依指定的顺序进行排列的过程，常见的排序：  1) 冒泡排序  2) 选择排序  3) 插入排序  4) 快速排序  5) 归并排序

19.8.2 冒泡排序

冒泡排序思想  冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。  因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。

冒泡排序的代码：

package com.atguigu.chapter19.sortimport java.text.SimpleDateFormatimport java.util.Dateobject BubbleSortDemo01 {  def main(args: Array[String]): Unit = {    // 数组    // val arr = Array(3, 9, -1, 10, 20)    // 创建一个80000个随机数据的数组，冒泡排序用时10秒    val random = new util.Random()    val arr = new Array[Int](80000)    for (i <- 0 until 80000) {      arr(i) = random.nextInt(8000000)    }    val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")    val now: Date = new Date()    val date = dateFormat.format(now)    println("冒泡排序前")    // println(arr.mkString(" "))    println("冒泡排序前时间 = " + date) // 输出时间    println("冒泡排序后")    bubbleSort(arr)    // println(arr.mkString(" "))    val now2: Date = new Date()    val date2 = dateFormat.format(now2)    println("冒泡排序后时间 = " + date2) // 输出时间  }  def bubbleSort(arr: Array[Int]): Unit = {    for (i <- 0 until arr.length - 1) {      for (j <- 0 until arr.length - 1 - i) {        if (arr(j) > arr(j + 1)) {          val temp = arr(j)          arr(j) = arr(j + 1)          arr(j + 1) = temp        }      }    }  }}

输出结果如下：

冒泡排序前冒泡排序前时间 = 2019-04-10 09:32:33冒泡排序后冒泡排序后时间 = 2019-04-10 09:32:43

19.8.3 选择排序

基本介绍  选择式排序也属于内部排序法(内存排序)，是从排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依规定交换位置后达到排序的目的。

选择排序思想  选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 R[0]~R[n-1] 中选取最小值，与 R[0] 交换，第二次从 R[1]~R[n-1] 中选取最小值，与 R[1] 交换，第三次从 R[2]~R[n-1] 中选取最小值，与 R[2] 交换，…，第 i 次从 R[i-1]~R[n-1] 中选取最小值，与 R[i-1] 交换，…, 第 n-1 次从 R[n-2]~R[n-1] 中选取最小值，与 R[n-2] 交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

选择排序思路分析图

选择排序的代码：

package com.atguigu.chapter19.sortimport java.text.SimpleDateFormatimport java.util.Dateobject SelectSortDemo01 {  def main(args: Array[String]): Unit = {    // var arr = Array(101, 34, 119, 1)    // 创建一个80000个随机数据的数组，选择排序用时3秒    val random = new util.Random()    val arr = new Array[Int](80000)    for (i <- 0 until 80000) {      arr(i) = random.nextInt(8000000)    }    val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")    val now: Date = new Date()    val date = dateFormat.format(now)    println("选择排序前")    // println(arr.mkString(" "))    println("选择排序前时间 = " + date) // 输出时间    println("选择排序后")    selectSort(arr)    // println(arr.mkString(" "))    val now2: Date = new Date()    val date2 = dateFormat.format(now2)    println("选择排序后时间 = " + date2) // 输出时间    /*    // 选择排序演变过程    // 第1轮选择排序 (101, 34, 119, 1) => (1, 34, 119, 101)    var min = arr(0) // 假定第一个为最小值    var minIndex = 0    // 遍历    for (j <- 0 + 1 until arr.length) {      if (min > arr(j)) { // 说明 min 不是真的最小值        min = arr(j) // 重置 min        minIndex = j // 重置 minIndex      }    }    // 判断一下是否需要交换位置（注意：这里没有交换位置操作，实际是赋值操作，因为新的最小值已经被我们记录下了，效率更高）    if (minIndex != 0) {      arr(minIndex) = arr(0)      arr(0) = min // 这是赋值操作    }    println("第1轮选择排序结束，结果是")    println(arr.mkString(" "))    // 第2轮选择排序 (1, 34, 119, 101) => (1, 34, 119, 101)    min = arr(1)    minIndex = 1    // 遍历    for (j <- 1 + 1 until arr.length) {      if (min > arr(j)) { // 说明 min 不是真的最小值        min = arr(j) // 重置 min        minIndex = j // 重置 minIndex      }    }    // 判断一下是否需要交换位置（注意：这里没有交换位置操作，实际是赋值操作，因为新的最小值已经被我们记录下了，效率更高）    if (minIndex != 1) {      arr(minIndex) = arr(1)      arr(1) = min // 这是赋值操作    }    println("第2轮选择排序结束，结果是")    println(arr.mkString(" "))    // 第3轮选择排序 (1, 34, 119, 101) => (1, 34, 101, 119)    min = arr(2)    minIndex = 2    // 遍历    for (j <- 2 + 1 until arr.length) {      if (min > arr(j)) { // 说明 min 不是真的最小值        min = arr(j) // 重置 min        minIndex = j // 重置 minIndex      }    }    // 判断一下是否需要交换位置（注意：这里没有交换位置操作，实际是赋值操作，因为新的最小值已经被我们记录下了，效率更高）    if (minIndex != 2) {      arr(minIndex) = arr(2)      arr(2) = min // 这是赋值操作    }    println("第3轮选择排序结束，结果是")    println(arr.mkString(" "))    */    /*    // 总结规律    for (i <- 0 until arr.length - 1) {      var min = arr(i) // 假定第一个为最小值      var minIndex = i      // 遍历      for (j <- i + 1 until arr.length) {        if (min > arr(j)) { // 说明 min 不是真的最小值          min = arr(j) // 重置 min          minIndex = j // 重置 minIndex        }      }      // 判断一下是否需要交换位置（注意：这里没有交换位置操作，实际是赋值操作，因为新的最小值已经被我们记录下了，效率更高）      if (minIndex != i) {        arr(minIndex) = arr(i)        arr(i) = min // 这是赋值操作      }      println(s"选择排序第 ${i + 1} 轮结束，结果是")      println(arr.mkString(" "))    }    */  }  def selectSort(arr: Array[Int]): Unit = {    for (i <- 0 until arr.length - 1) {      var min = arr(i) // 假定第一个为最小值      var minIndex = i      // 遍历      for (j <- i + 1 until arr.length) {        if (min > arr(j)) { // 说明 min 不是真的最小值          min = arr(j) // 重置 min          minIndex = j // 重置 minIndex        }      }      // 判断一下是否需要交换位置（注意：这里没有交换位置操作，实际是赋值操作，因为新的最小值已经被我们记录下了，效率更高）      if (minIndex != i) {        arr(minIndex) = arr(i)        arr(i) = min // 这是赋值操作      }    }  }}

输出结果如下：

选择排序前选择排序前时间 = 2019-04-10 10:21:06选择排序后选择排序后时间 = 2019-04-10 10:21:09

19.8.4 插入排序

基本介绍  插入式排序属于内部排序法，对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序法思想  插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

插入排序思路分析图

插入排序的代码：

package com.atguigu.chapter19.sortimport java.text.SimpleDateFormatimport java.util.Dateimport com.atguigu.chapter19.sort.SelectSortDemo01.selectSortobject InsertSortDemo01 {  def main(args: Array[String]): Unit = {    // var arr = Array(101, 34, 119, 1)    // 创建一个80000个随机数据的数组，插入排序用时1秒    val random = new util.Random()    val arr = new Array[Int](80000)    for (i <- 0 until 80000) {      arr(i) = random.nextInt(8000000)    }    val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")    val now: Date = new Date()    val date = dateFormat.format(now)    println("插入排序前")    // println(arr.mkString(" "))    println("选择排序前时间 = " + date) // 输出时间    println("插入排序后")    selectSort(arr)    // println(arr.mkString(" "))    val now2: Date = new Date()    val date2 = dateFormat.format(now2)    println("插入排序后时间 = " + date2) // 输出时间    /*    // 插入排序演变过程    // 第1轮插入排序 ((101), 34, 119, 1) => ((34, 101), 119, 1)    val insertValue = arr(1) // 将要插入的元素的值    var insertIndex = 1 - 1 // 表示(101)有序表的最后这个元素的索引，即有序表的最大值的索引    while (insertIndex >= 0 && arr(insertIndex) > insertValue) {      arr(insertIndex + 1) = arr(insertIndex) // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是自己      insertIndex -= 1 // insertIndex = -1    }    // 退出 while 循环或者不进入 while 循环，表示要插入的位置找到了    arr(insertIndex + 1) = insertValue  // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是要插入的值    println("第1轮插入排序结束，结果是")    println(arr.mkString(" "))    // 第2轮插入排序 ((34, 101), 119, 1) => ((34, 101, 119), 1)    insertValue = arr(2) // 将要插入的元素的值    insertIndex = 2 - 1 // 表示(34, 101)有序表的最后这个元素的索引，即有序表的最大值的索引    while (insertIndex >= 0 && arr(insertIndex) > insertValue) {      arr(insertIndex + 1) = arr(insertIndex) // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是自己      insertIndex -= 1 // insertIndex = -1    }    // 退出 while 循环或者不进入 while 循环，表示要插入的位置找到了    arr(insertIndex + 1) = insertValue  // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是要插入的值    println("第2轮插入排序结束，结果是")    println(arr.mkString(" "))    // 第3轮插入排序 ((34, 101, 119), 1) => (1, 34, 101, 119)    insertValue = arr(3) // 将要插入的元素的值    insertIndex = 3 - 1 // 表示(34, 101, 119)有序表的最后这个元素的索引，即有序表的最大值的索引    while (insertIndex >= 0 && arr(insertIndex) > insertValue) {      arr(insertIndex + 1) = arr(insertIndex) // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是自己      insertIndex -= 1 // insertIndex = -1    }    // 退出 while 循环或者不进入 while 循环，表示要插入的位置找到了    arr(insertIndex + 1) = insertValue  // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是要插入的值    println("第3轮插入排序结束，结果是")    println(arr.mkString(" "))    // 总结规律    for (i <- 1 until arr.length) {      val insertValue = arr(i) // 将要插入的元素的值      var insertIndex = i - 1 // 表示有序表的最后这个元素的索引，即有序表的最大值的索引      while (insertIndex >= 0 && arr(insertIndex) > insertValue) {        arr(insertIndex + 1) = arr(insertIndex) // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是自己        insertIndex -= 1 // insertIndex = -1      }      // 退出 while 循环或者不进入 while 循环，表示要插入的位置找到了      arr(insertIndex + 1) = insertValue  // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是要插入的值      println(s"第${i}轮插入排序结束，结果是")      println(arr.mkString(" "))    }    */  }  def insertSort(arr: Array[Int]): Unit = {    for (i <- 1 until arr.length) {      val insertValue = arr(i) // 将要插入的元素的值      var insertIndex = i - 1 // 表示有序表的最后这个元素的索引，即有序表的最大值的索引      while (insertIndex >= 0 && arr(insertIndex) > insertValue) {        arr(insertIndex + 1) = arr(insertIndex) // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是自己        insertIndex -= 1 // insertIndex = -1      }      // 退出 while 循环或者不进入 while 循环，表示要插入的位置找到了      arr(insertIndex + 1) = insertValue  // 插入的位置的意思是：插入有序表中最后一个元素的下一个位置，插入的是要插入的值    }  }}

输出结果如下：

插入排序前选择排序前时间 = 2019-04-10 11:27:55插入排序后插入排序后时间 = 2019-04-10 11:27:56

19.8.5 快速排序

基本介绍  快速排序（Quicksort）是对冒泡排序的一种改进。

插入排序法思想  基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序示意图

快速排序的代码：

package com.atguigu.chapter19.sortimport java.text.SimpleDateFormatimport java.util.Dateimport util.control.Breaks._object QuickSortDemo01 {  def main(args: Array[String]): Unit = {    // var arr = Array[Int](-9, 78, 0, 23, -567, 70)    // println("快速排序前")    // println(arr.mkString(" "))    // println("快速排序后")    // quickSort(0, arr.length - 1, arr)    // println(arr.mkString(" "))    // 如果取消左右递归，结果是  -9 -567 0 23 78 70    // 如果取消右递归，结果是    -567 -9 0 23 78 70    // 如果取消左递归，结果是    -9 -567 0 23 70 78    // 如果正常，结果是         -567 -9 0 23 70 78    // 创建一个8000 0000个随机数据的数组，快速排序用时12秒（八千万个数据），太快了！！！    val random = new util.Random()    val arr = new Array[Int](80000000)    for (i <- 0 until 80000000) {      arr(i) = random.nextInt(800000000)    }    val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")    val now: Date = new Date()    val date = dateFormat.format(now)    println("快速排序前")    // println(arr.mkString(" "))    println("快速排序前时间 = " + date) // 输出时间    println("快速排序后")    quickSort(0, arr.length - 1, arr)    // println(arr.mkString(" "))    val now2: Date = new Date()    val date2 = dateFormat.format(now2)    println("快速排序后时间 = " + date2) // 输出时间  }  // left: 从数组的左边的索引 0  // right: 从数组的右边的索引 arr.length - 1  // arr: 进行排序的数组  def quickSort(left: Int, right: Int, arr: Array[Int]): Unit = {    var l = left    var r = right    val pivot = arr((left + right) / 2)    breakable {      // while 语句的作用就是把比 pivot 小的数放到左边，比 pivot 大的数放到右边      while (l < r) {        while (arr(l) < pivot) { // 从左边找一个比 pivot 大的值          l += 1        }        while (arr(r) > pivot) { // 从右边找一个比 pivot 小的值          r -= 1        }        if (l >= r) { // 说明本次交换结束，退出本次 while          break()        }        // 交换二者位置        val temp = arr(l)        arr(l) = arr(r)        arr(r) = temp        // 二者已经交换后再进行的判断，即 arr(l) 表示的是 右边        if (arr(l) == pivot) { // 如果 从右边找一个与 pivot 相等的值，则不用交换，继续进行右边下一个，提高效率          r -= 1        }        // 二者已经交换后再进行的判断，即 arr(r) 表示的是 左边        if (arr(r) == pivot) { // 如果 从左边找一个与 pivot 相等的值，则不用交换，继续进行左边下一个，提高效率          l += 1        }      }    }    // 提高效率    if (l == r) {      l += 1 // 为向右递归做准备      r -= 1 // 为向左递归做准备    }    if (left < r) { // 向左递归      quickSort(left, r, arr)    }    if (right > l) { // 向右递归      quickSort(l, right, arr)    }  }}

输出结果如下：

快速排序前快速排序前时间 = 2019-04-10 13:25:56快速排序后快速排序后时间 = 2019-04-10 13:26:06

快速排序代码详细图解

19.8.6 归并排序

基本介绍  归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之）。

归并排序思想示意图1-基本思想  可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分的阶段可以理解为就是递归拆分子序列的过程。

归并排序思想示意图2-合并相邻有序子序列  再来看看治的阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将 [4,5,7,8] 和 [1,2,3,6] 两个已经有序的子序列，合并为最终序列 [1,2,3,4,5,6,7,8]，来看下实现步骤：

归并排序的代码：

package com.atguigu.chapter19.sortimport java.text.SimpleDateFormatimport java.util.Dateobject MergeSortDemo01 {  def main(args: Array[String]): Unit = {    // val arr = Array(7, 6, 5, 4, 3, 2, 1)    // val temp = new Array[Int](arr.length)    // println("归并排序前")    // println(arr.mkString(" "))    // println("归并排序后")    // mergeSort(arr, 0, arr.length - 1, temp)    // println(arr.mkString(" "))    // 创建一个8000 0000个随机数据的数组，归并排序用时12秒（八千万个数据），太快了！！！    val random = new util.Random()    val arr = new Array[Int](80000000)    val temp = new Array[Int](arr.length)    for (i <- 0 until 80000000) {      arr(i) = random.nextInt(800000000)    }    val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")    val now: Date = new Date()    val date = dateFormat.format(now)    println("归并排序前")    // println(arr.mkString(" "))    println("归并排序前时间 = " + date) // 输出时间    println("归并排序后")    mergeSort(arr, 0, arr.length - 1, temp)    // println(arr.mkString(" "))    val now2: Date = new Date()    val date2 = dateFormat.format(now2)    println("归并排序后时间 = " + date2) // 输出时间  }  // 归并排序  // arr 待排序的数组  // left 数组的左边的索引 0  // right 数组的右边边的索引 arr.length - 1  // temp 临时数组，事先开辟好的，大小与 arr 一样  def mergeSort(arr: Array[Int], left: Int, right: Int, temp: Array[Int]): Unit = {    // 拆分操作    if (left < right) {      val mid = (left + right) / 2      mergeSort(arr, left, mid, temp) // 递归拆分左边数组成有序列表      mergeSort(arr, mid + 1, right, temp) // 递归拆分右边数组成有序列表      merge(arr, left, mid, right, temp) // 合并    }  }  // 合并操作  def merge(arr: Array[Int], left: Int, mid: Int, right: Int, temp: Array[Int]) {    var i = left // 辅助指针    var j = mid + 1 // 辅助指针    var t = 0 // 表示临时数组的第一个元素的索引    while (i <= mid && j <= right) {      if (arr(i) <= arr(j)) { // 当前左边的有序列表的值小于当前右边有序列表的值        temp(t) = arr(i) // 把当前左边的有序列表的值依次赋值给临时数组        t += 1 // 临时数组的索引右移一位        i += 1 // 左边有序列表的索引右移一位      } else {        temp(t) = arr(j) // 把当前右边的有序列表的值依次赋值给临时数组        t += 1 // 临时数组的索引右移一位        j += 1 // 右边有序列表的索引右移一位      }    }    while (i <= mid) { // 说明左边有序列表还有数据，就把当前左边的有序列表的值依次赋值给临时数组      temp(t) = arr(i)      t += 1      i += 1    }    while (j <= right) { // 说明右边有序列表还有数据，就把当前右边的有序列表的值依次赋值给临时数组      temp(t) = arr(j)      t += 1      j += 1    }    // 下面代码时完成将本次的临时数组 temp 的数据拷贝到原始数组 arr 中    t = 0 // 归位到临时数组的第一个元素的索引    var tempLeft = left // 辅助指针    while (tempLeft <= right) { // 将临时数组中的数据依次拷贝至原数组中去      arr(tempLeft) = temp(t)      t += 1      tempLeft += 1    }  }}

输出结果如下：

归并排序前归并排序前时间 = 2019-04-10 17:40:46归并排序后归并排序后时间 = 2019-04-10 17:40:58

19.9 查找

18.9.1 介绍

在 java 中，我们常用的查找有两种:  1、顺序(线性)查找  2、二分查找

19.9.2 线性查找

  有一个数列：{1, 8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称。  要求: 如果找到了，就提示找到，并给出下标值。

19.9.3 二分查找

  请对一个有序数组进行二分查找 {1, 8, 10, 89, 1000, 1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。  课后思考题：{1, 8, 10, 89, 1000, 1000, 1234} 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如：这里的 1000

二分查找 + 二分查找所有相同的值 的代码实现

package com.atguigu.chapter19.searchimport scala.collection.mutable.ArrayBufferimport util.control.Breaks._object BinarySearchDemo01 {  def main(args: Array[String]): Unit = {    val arr = Array(1, 8, 10, 89, 1000, 1000, 1000, 1234)    // 测试：二分查找    val index = binarySearch(arr, 0, arr.length - 1, 1000)    if (index != -1) {      println("找到，索引为 = " + index)    } else {      println("没有找到")    }    println("--------------------")    // 测试：二分查找所有相同的值    val resArr = binarySearch2(arr, 0, arr.length - 1, 1000)    if (resArr.length != 0) {      for (index <- resArr) {        println("找到，索引分别 = " + index)      }    } else {      println("没有找到")    }  }  // 二分查找  // 1. 先找到中间值  // 2. 然后将中间值和查找的值进行比较  //   2.1 相等，找到，返回索引  //   2.2 查找值 < 中间值，向左进行递归查找  //   2.3 查找值 > 中间值，向右进行递归查找  // 如果存在该值，就返回对应的索引，否则返回 -1  def binarySearch(arr: Array[Int], left: Int, right: Int, findValue: Int): Int = {    val midIndex = (left + right) / 2    val midValue = arr(midIndex)    // 找不到的情况判断    if (left > right) {      return -1    }    if (findValue < midValue) {      binarySearch(arr, left, midIndex - 1, findValue)    } else if (findValue > midValue) {      binarySearch(arr, midIndex + 1, right, findValue)    } else {      return midIndex    }  }  // 二分查找所有相同的值  // 1. 先找到中间值  // 2. 然后将中间值和查找的值进行比较  //   2.1 相等，找到，返回索引  //   2.2 查找值 < 中间值，向左进行递归查找  //   2.3 查找值 > 中间值，向右进行递归查找  // 如果存在该值，就返回对应的索引，否则返回 -1  // 1.返回个结果是一个可变数组 ArrayBuffer  // 2.在找到结果时，分别向左边扫描和向右边扫描  // 3.又找到结果后，就加入到 ArrayBuffer，在分别向左边扫描和向右边扫描......  def binarySearch2(arr: Array[Int], left: Int, right: Int, findValue: Int): ArrayBuffer[Int] = {    val midIndex = (left + right) / 2    val midValue = arr(midIndex)    // 如果找不到，返回 -1    if (left > right) {      return ArrayBuffer() // 返回一个空的可变数组，之后可以通过数组长度进行判断    }    // 如果找到，返回对应的索引    if (findValue < midValue) {      binarySearch2(arr, left, midIndex - 1, findValue)    } else if (findValue > midValue) {      binarySearch2(arr, midIndex + 1, right, findValue)    } else {      // 定义一个可变数组      val resArr = ArrayBuffer[Int]()      // 向左扫描      var temp = midIndex - 1 // 辅助指针      breakable {        while (true) {          if (temp < 0 || arr(temp) != findValue) {            break()          }          if (arr(temp) == findValue) {            resArr.append(temp)          }          temp -= 1 // 找到，移动指针，继续向左扫描        }      }      // 将中间这个已经找到的索引加入到可变数组      resArr.append(midIndex) // 注意：该句代码放的位置不同，可能导致找到的索引输出的结果顺序不同      // 向右扫描      temp = midIndex + 1 // 辅助指针      breakable {        while (true) {          if (temp > right || arr(temp) != findValue) {            break()          }          if (arr(temp) == findValue) {            resArr.append(temp)          }          temp += 1 // 找到，移动指针，继续向右扫描        }      }      return resArr    }  }}

输出结果如下：

找到，索引为 = 5--------------------找到，索引分别 = 4找到，索引分别 = 5找到，索引分别 = 6

19.10 哈希表(散列表)

19.10.1 看一个实际需求

  google 公司的一个上机题：  有一个公司，当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…)，当输入该员工的 id 时，要求查找到该员工的所有信息。  要求：不使用数据库，尽量节省内存，速度越快越好 => 哈希表(散列)

19.10.2 哈希表的基本介绍

  散列表（Hash table，也叫哈希表），是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

自定义缓存

19.10.3 应用实例

  google 公司的一个上机题：  有一个公司，当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…)，当输入该员工的 id 时，要求查找到该员工的所有信息。  要求：  1、不使用数据库，尽量节省内存，速度越快越好 => 哈希表(散列)  2、使用链表来实现哈希表，该链表不带表头。[即: 链表的第一个结点就存放雇员信息]  3、添加时，保证按照 id 从低到高插入。

思路分析示意图

[思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到高，怎么解决？以及插入链表中的数据不能重复，如何解决？] 代码如下代码实现[增删改查(显示所有员工,按 id 查询)]

package com.atguigu.chapter19.hashtabimport scala.io.StdInimport util.control.Breaks._object HashTabDemo01 {  def main(args: Array[String]): Unit = {    // 创建 HashTab    val hashTab = new HashTab(7)    // 写一个简单地菜单    var key = ""    while (true) {      println("add：添加雇员 ")      println("list：显示雇员")      println("find：查找雇员")      println("exit：退出系统")      key = StdIn.readLine()      key match {        case "add" => {          print("请输入id：")          val id = StdIn.readInt()          print("请输入名字：")          val name = StdIn.readLine()          val emp = new Emp(id, name)          hashTab.add2(emp)        }        case "list" => {          hashTab.list()        }        case "find" => {          print("请输入id：")          val id = StdIn.readInt()          hashTab.findEmpById(id)        }        case "exit" => {          System.exit(0)        }      }    }  }}// 创建 HashTab，用于雇员链表的增删改查+决定雇员应该添加到哪一条具体的雇员链表上 等等class HashTab(val size: Int) { // 暂时默认 size = 7，注意：size 是只读属性  val empLinkedListArr: Array[EmpLinkedList] = new Array[EmpLinkedList](size)  // 初始化雇员链表数组的各个元素  for (i <- 0 until size) {    empLinkedListArr(i) = new EmpLinkedList  }  // 散列函数（该函数视具体情况而定）  // 决定雇员应该添加到哪一条具体的雇员链表上  def hashFun(id: Int): Int = {    id % size  }  // 向雇员链表上添加雇员  def add2(emp: Emp): Unit = {    val empLinkedListNo = hashFun(emp.id) // Array 数组的索引，即具体哪一天链表    // 判断要添加的雇员 id 是否存在，如果存在，则直接返回并弹出信息；如果不存在，则添加    if (this.empLinkedListArr(empLinkedListNo).findEmpById(emp.id) != null) {      printf("要添加的雇员 id=%d 已存在，请重新添加\n", emp.id)      return    } else {      this.empLinkedListArr(empLinkedListNo).add2(emp)    }  }  // 遍历整个哈希表  def list(): Unit = {    for (i <- 0 until size) {      empLinkedListArr(i).list(i)    }  }  // 查找雇员  def findEmpById(id: Int): Unit = {    val empLinkedListNo = hashFun(id) // Array 数组的索引，即具体哪一天链表    val emp = this.empLinkedListArr(empLinkedListNo).findEmpById(id)    if (emp != null) {      printf(s"在第 ${empLinkedListNo} 条雇员链表上找到 id=%d name=%s 的雇员\n", id, emp.name)    } else {      printf("没有找到id为 %d 的雇员\n", id)    }  }}// 创建 EmpLinkedList，用于雇员的增删改查class EmpLinkedList {  // 定义头指针，注意：这里的 head 直接指向一个雇员  var head: Emp = null  // 添加雇员的方法一  // 找到链表的尾部加入即可  // 假定添加雇员的 id 是自增的，即雇员分配的 id 总是从小到大  def add(emp: Emp): Unit = {    // 对于第一个雇员    if (head == null) {      head = emp // head 直接指向第一个雇员      return    }    // 定义一个辅助指针    var temp = head    // 找到链表的尾部    breakable {      while (true) {        if (temp.next == null) { // 说明已到该链表的尾部          break()        }        temp = temp.next // 后移指针      }    }    // 该链表的尾部指向新加入的雇员    temp.next = emp  }  // 添加雇员的方法二  // 在添加雇员的时候，根据雇员的id将雇员插入指定的位置（如果该雇员的 id 已存在，则添加失败，并给出提示）  def add2(emp: Emp): Unit = {    // 对于第一个雇员    if (head == null) {      head = emp // head 直接指向第一个雇员，由于我们的头结点也使用，所以判断雇员的 id 是否存在的操作，我们放在了调用添加雇员方法之前。      return    }    // 走到这一步，说明链表中至少有一个雇员了    // 定义一个辅助指针    var temp = head    var flag = false    breakable {      while (true) {        if (temp.next == null) { // 说明已到该链表的尾部          break()        }        if (emp.id < temp.id) { // 执行到这一步，说明链表中已经有两个以上(包括两个)雇员          flag = true          break()        }        if (emp.id < temp.next.id) { // 说明位置找到，当前这个节点 Emp 应加入到节点 temp 的后面 和节点 temp.next 的前面          break()        }        temp = temp.next // 后移指针      }    }    if (flag) { // 当链表中已经有两个以上(包括两个)雇员，新的雇员添加至链表头的操作      head = emp      emp.next = temp    } else {      if (emp.id < temp.id) { // 当链表中只有一个雇员，新的雇员添加至链表头的操作        head = emp        emp.next = temp      } else { // 当链表中已经有两个以上(包括两个)雇员，，新的雇员添加至链表中的操作        // 添加雇员，注意添加的顺序        emp.next = temp.next        temp.next = emp      }    }  }  // 遍历雇员链表  def list(i: Int): Unit = {    if (head == null) {      println(s"第 ${i} 条雇员链表的数据为空")      return    }    print(s"第 ${i} 条雇员链表的数据为：")    // 定义一个辅助指针    var temp = head    breakable {      while (true) {        if (temp == null) {          break()        }        // 输出雇员信息        printf("=> id=%d name=%s\t", temp.id, temp.name)        temp = temp.next // 后移指针      }    }    println()  }  // 查找雇员，找到返回 Emp，找不到返回 null  def findEmpById(id: Int): Emp = {    // 遍历    if (head == null) {      return null    }    // 定义一个辅助指针    var temp = head    breakable {      while (true) {        if (temp == null) {          break()        }        if (temp.id == id) {          break()        }        temp = temp.next      }    }    return temp  }}// 创建雇员类class Emp(eId: Int, eName: String) {  val id = eId  var name = eName  var next: Emp = null}

核心代码截图如下：

19.11 二叉树

19.11.1 为什么需要树这种数据结构

1、数组存储方式的分析  优点：通过索引的方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。  缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低。

2、链式存储方式的分析  优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入的节点，链接到链表中即可)。  缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)。

3、树存储方式的分析  能提高数据存储、读取的效率，比如：利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。

19.11.2 二叉树的示意图

19.11.3 二叉树的概念

1、树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。2、二叉树的子节点分为左节点和右节点。

3、如果该二叉树的所有叶子节点都在最后一层，并且结点总数 = 2^n - 1，n 为层数，则我们称为满二叉树。4、如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

19.11.4 二叉树遍历的说明

  使用前序、中序和后序对下面的二叉树进行遍历，对各种遍历方式的说明:  前序遍历：先输出父节点，再遍历左子树和右子树。  中序遍历：先遍历左子树，再输出父节点，再遍历右子树。  后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。  小结：看输出父节点的顺序，就确定是前序、中序还是后序。

19.11.5 二叉树遍历应用实例(前序、中序、后序)

示例代码如下：

package com.atguigu.chapter19.binarytreeobject BinaryTreeDemo01 {  def main(args: Array[String]): Unit = {    // 先使用简单的方法：直接手动关联    val heroNode1 = new HeroNode(1, "宋江")    val heroNode2 = new HeroNode(2, "卢俊义")    val heroNode3 = new HeroNode(3, "吴用")    val heroNode4 = new HeroNode(4, "入云龙")    val heroNode5 = new HeroNode(5, "关胜")    heroNode1.left = heroNode2    heroNode1.right = heroNode3    heroNode3.left = heroNode5    heroNode3.right = heroNode4    val binaryTree = new BinaryTree    binaryTree.root = heroNode1    println("-----前序遍历的结果-----")    binaryTree.preOrder()    println("-----中序遍历的结果-----")    binaryTree.infixOrder()    println("-----后序遍历的结果-----")    binaryTree.postOrder()  }}// 定义管理英雄节点的二叉树class BinaryTree {  var root: HeroNode = null  // 前序遍历  def preOrder(): Unit = {    if (root != null) {      root.preOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }  // 中序遍历  def infixOrder(): Unit = {    if (root != null) {      root.infixOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }  // 后序遍历  def postOrder(): Unit = {    if (root != null) {      root.postOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }}// 定义英雄节点class HeroNode(hNo: Int, hName: String) {  val no = hNo  var name = hName  var left: HeroNode = null  var right: HeroNode = null  // 前序遍历：先输出父节点，再遍历左子树和右子树。  def preOrder(): Unit = {    // 先输出当前节点信息    printf("节点信息 no=%d name=%s \n", no, name)    // 向左递归输出左子树    if (this.left != null) {      this.left.preOrder()    }    // 向右递归输出右子树    if (this.right != null) {      this.right.preOrder()    }  }  // 中序遍历：先遍历左子树，再输出父节点，再遍历右子树。  def infixOrder(): Unit = {    // 向左递归输出左子树    if (this.left != null) {      this.left.infixOrder()    }    // 输出当前节点信息    printf("节点信息 no=%d name=%s \n", no, name)    // 向右递归输出右子树    if (this.right != null) {      this.right.infixOrder()    }  }  // 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。  def postOrder(): Unit = {    // 向左递归输出左子树    if (this.left != null) {      this.left.postOrder()    }    // 向右递归输出右子树    if (this.right != null) {      this.right.postOrder()    }    // 输出当前节点信息    printf("节点信息 no=%d name=%s \n", no, name)  }}

输出结果如下：

-----前序遍历的结果-----节点信息 no=1 name=宋江 节点信息 no=2 name=卢俊义 节点信息 no=3 name=吴用 节点信息 no=5 name=关胜 节点信息 no=4 name=入云龙 -----中序遍历的结果-----节点信息 no=2 name=卢俊义 节点信息 no=1 name=宋江 节点信息 no=5 name=关胜 节点信息 no=3 name=吴用 节点信息 no=4 name=入云龙 -----后序遍历的结果-----节点信息 no=2 name=卢俊义 节点信息 no=5 name=关胜 节点信息 no=4 name=入云龙 节点信息 no=3 name=吴用 节点信息 no=1 name=宋江 

19.11.6 二叉树-查找指定节点

要求  1、请编写前序查找、中序查找和后序查找的方法。  2、并分别使用三种查找方式，查找 hNo = 5 的节点  3、并分析各种查找方式，分别比较了多少  4、代码实现和思路分析

示例代码如下：

package com.atguigu.chapter19.binarytreeobject BinaryTreeDemo01 {  def main(args: Array[String]): Unit = {    // 先使用简单的方法：直接手动关联    val heroNode1 = new HeroNode(1, "宋江")    val heroNode2 = new HeroNode(2, "卢俊义")    val heroNode3 = new HeroNode(3, "吴用")    val heroNode4 = new HeroNode(4, "入云龙")    val heroNode5 = new HeroNode(5, "关胜")    heroNode1.left = heroNode2    heroNode1.right = heroNode3    heroNode3.left = heroNode5    heroNode3.right = heroNode4    val binaryTree = new BinaryTree    binaryTree.root = heroNode1    println("-----前序遍历的结果-----")    binaryTree.preOrder()    println("-----中序遍历的结果-----")    binaryTree.infixOrder()    println("-----后序遍历的结果-----")    binaryTree.postOrder()    println()    println("-----前序查找的结果-----")    val temp = binaryTree.preOrderSearch(5)    if (temp != null) {      printf("找到，该节点的信息是 no=%d name=%s\n", temp.no, temp.name)    } else {      println("没有找到该节点")    }    println()    println("-----中序查找的结果-----")    val temp2 = binaryTree.infixOrderSearch(5)    if (temp2 != null) {      printf("找到，该节点的信息是 no=%d name=%s\n", temp2.no, temp2.name)    } else {      println("没有找到该节点")    }    println()    println("-----后序查找的结果-----")    val temp3 = binaryTree.postOrderSearch(5)    if (temp3 != null) {      printf("找到，该节点的信息是 no=%d name=%s\n", temp3.no, temp3.name)    } else {      println("没有找到该节点")    }  }}// 定义管理英雄节点的二叉树class BinaryTree {  var root: HeroNode = null  // 前序遍历  def preOrder(): Unit = {    if (root != null) {      root.preOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }  // 中序遍历  def infixOrder(): Unit = {    if (root != null) {      root.infixOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }  // 后序遍历  def postOrder(): Unit = {    if (root != null) {      root.postOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }  // 前序查找  def preOrderSearch(no: Int): HeroNode = {    if (root != null) {      return root.preOrderSearch(no)    } else {      return null // 二叉树为空    }  }  // 中序查找  def infixOrderSearch(no: Int): HeroNode = {    if (root != null) {      return root.infixOrderSearch(no)    } else {      return null // 二叉树为空    }  }  // 后序查找  def postOrderSearch(no: Int): HeroNode = {    if (root != null) {      return root.postOrderSearch(no)    } else {      return null // 二叉树为空    }  }}// 定义英雄节点class HeroNode(hNo: Int, hName: String) {  val no = hNo  var name = hName  var left: HeroNode = null  var right: HeroNode = null  // 前序遍历：先输出父节点，再遍历左子树和右子树。  def preOrder(): Unit = {    // 先输出当前节点信息    printf("节点信息 no=%d name=%s \n", no, name)    // 向左递归输出左子树    if (this.left != null) {      this.left.preOrder()    }    // 向右递归输出右子树    if (this.right != null) {      this.right.preOrder()    }  }  // 中序遍历：先遍历左子树，再输出父节点，再遍历右子树。  def infixOrder(): Unit = {    // 向左递归输出左子树    if (this.left != null) {      this.left.infixOrder()    }    // 输出当前节点信息    printf("节点信息 no=%d name=%s \n", no, name)    // 向右递归输出右子树    if (this.right != null) {      this.right.infixOrder()    }  }  // 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点。  def postOrder(): Unit = {    // 向左递归输出左子树    if (this.left != null) {      this.left.postOrder()    }    // 向右递归输出右子树    if (this.right != null) {      this.right.postOrder()    }    // 输出当前节点信息    printf("节点信息 no=%d name=%s \n", no, name)  }  // 前序查找  def preOrderSearch(no: Int): HeroNode = {    println("-----前序查找次数标记-----")    // 先比较当前节点，如果是，就返回当前节点的值，如果不是，就向左子树递归查找    if (no == this.no) {      return this    }    // 向左递归查找    var temp: HeroNode = null // 辅助指针    // 如果左子树不为空，才进行递归查找    if (this.left != null) {      temp = this.left.preOrderSearch(no)    }    if (temp != null) {      return temp    }    // 向右递归查找    // 如果右子树不为空，才进行递归查找    if (this.right != null) {      temp = this.right.preOrderSearch(no)    }    if (temp != null) {      return temp    }    return temp  }  // 中序查找  def infixOrderSearch(no: Int): HeroNode = {    // 先向左递归查找    var temp: HeroNode = null // 辅助指针    // 如果左子树不为空，才进行递归查找    if (this.left != null) {      temp = this.left.infixOrderSearch(no)    }    if (temp != null) {      return temp    }    println("-----中序查找次数标记-----")    // 再比较当前节点，如果是，就返回当前节点的值，如果不是，就向左子树递归查找    if (no == this.no) {      return this    }    // 最后向右递归查找    // 如果右子树不为空，才进行递归查找    if (this.right != null) {      temp = this.right.infixOrderSearch(no)    }    if (temp != null) {      return temp    }    return temp  }  // 后序查找  def postOrderSearch(no: Int): HeroNode = {    // 先向左递归查找    var temp: HeroNode = null // 辅助指针    // 如果左子树不为空，才进行递归查找    if (this.left != null) {      temp = this.left.postOrderSearch(no)    }    if (temp != null) {      return temp    }    // 再向右递归查找    // 如果右子树不为空，才进行递归查找    if (this.right != null) {      temp = this.right.postOrderSearch(no)    }    if (temp != null) {      return temp    }    println("-----后序查找次数标记-----")    // 最后比较当前节点，如果是，就返回当前节点的值，如果不是，就向左子树递归查找    if (no == this.no) {      return this    }    return temp  }}

输出结果如下：

-----前序遍历的结果-----节点信息 no=1 name=宋江 节点信息 no=2 name=卢俊义 节点信息 no=3 name=吴用 节点信息 no=5 name=关胜 节点信息 no=4 name=入云龙 -----中序遍历的结果-----节点信息 no=2 name=卢俊义 节点信息 no=1 name=宋江 节点信息 no=5 name=关胜 节点信息 no=3 name=吴用 节点信息 no=4 name=入云龙 -----后序遍历的结果-----节点信息 no=2 name=卢俊义 节点信息 no=5 name=关胜 节点信息 no=4 name=入云龙 节点信息 no=3 name=吴用 节点信息 no=1 name=宋江 -----前序查找的结果----------前序查找次数标记----------前序查找次数标记----------前序查找次数标记----------前序查找次数标记-----找到，该节点的信息是 no=5 name=关胜-----中序查找的结果----------中序查找次数标记----------中序查找次数标记----------中序查找次数标记-----找到，该节点的信息是 no=5 name=关胜-----后序查找的结果----------后序查找次数标记----------后序查找次数标记-----找到，该节点的信息是 no=5 name=关胜

19.11.7 二叉树-删除节点

要求  1、如果删除的节点是叶子节点，则删除该节点  2、如果删除的节点是非叶子节点，则删除该子树  3、测试，删除掉 5 号叶子节点 和 3 号子树。  4、代码，思路在代码中。

核心代码示例如下：

    println("-----测试删除节点-------")    binaryTree.delNode(1)    println("-----删除后前序遍历---------")    binaryTree.preOrder()-----------------------------------------------------// 定义管理英雄节点的二叉树class BinaryTree {  var root: HeroNode = null  // 删除节点  def delNode(no: Int): Unit = {    if (root != null) {      // 先判断下 root 节点是否是要删除的节点      if (root.no == no) {        root = null      }      root.delNode(no)    }  }}-----------------------------------------------------// 定义英雄节点class HeroNode(hNo: Int, hName: String) {  val no = hNo  var name = hName  var left: HeroNode = null  var right: HeroNode = null  // 删除节点  // 删除节点的规则一  //   （1）如果删除的节点是叶子节点，则删除该节点  //   （2）如果删除的节点是非叶子节点，则删除该子树  def delNode(no: Int): Unit = {    // 当前节点的左节点是为要删除的节点    if (this.left != null && this.left.no == no) {      this.left = null      return    }    // 当前节点的右节点是为要删除的节点    if (this.right != null && this.right.no == no) {      this.right = null      return    }    // 说明当前节点的左/右节点不是要删除的节点，则向左递归删除和向右递归删除    if (this.left != null) {      this.left.delNode(no)    }    if (this.right != null) {      this.right.delNode(no)    }  }}

思考如果要删除的节点是非叶子节点，现在我们不希望将该非叶子节点为根节点的子树删除，需要指定规则, 假如规定如下:删除A节点（1）如果该非叶子节点A只有一个子节点B，则子节点B替代节点A（2）如果该非叶子节点A有左子节点B和右子节点C，则让左子节点B替代节点A。

19.12 顺序存储的二叉树

19.12.1 顺序存储二叉树的概念

基本说明  从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看下面的示意图。

19.12.2 顺序存储二叉树的遍历

需求：给你一个数组 Array(1,2,3,4,5,6,7)，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7代码实现：

package com.atguigu.chapter19.binarytreeobject ArrayTreeDemo01 {  def main(args: Array[String]): Unit = {    val arr = Array(1, 2, 3, 4, 5, 6, 7)    val arrayTree = new ArrayTree(arr)    println("-----前序遍历(数组)的结果-----")    arrayTree.preOrder()    println("-----中序遍历(数组)的结果-----")    arrayTree.infixOrder()    println("-----后序遍历(数组)的结果-----")    arrayTree.postOrder()  }}// 把数组当成二叉树，把数组以二叉树前序遍历的方式进行遍历class ArrayTree(val arr: Array[Int]) {  // 为了方便，对 preOrder 进行一个方法重载  def preOrder():Unit = {    this.preOrder(0)  }  // 为了方便，对 infixOrder 进行一个方法重载  def infixOrder():Unit = {    this.infixOrder(0)  }  // 为了方便，对 postOrder 进行一个方法重载  def postOrder():Unit = {    this.postOrder(0)  }  // 前序遍历二叉树，即前序遍历数组  // 前序遍历：先输出父节点，再遍历左子树和右子树。  def preOrder(index: Int): Unit = {    if (arr == null || arr.length == 0) {      println("数组为空，不能按照二叉树遍历的方式进行遍历")    }    // 先输出当前节点信息    println(arr(index)) // index 初始化值为0，即对应 root 节点    // 向左递归输出左子树    if ((index * 2 + 1) < arr.length) {      preOrder(index * 2 + 1)    }    // 向右递归输出右子树    if ((index * 2 + 2) < arr.length) {      preOrder(index * 2 + 2)    }  }  // 中序遍历二叉树，即中序遍历数组  // 中序遍历：：先遍历左子树，再输出父节点，再遍历右子树。  def infixOrder(index: Int): Unit = {    if (arr == null || arr.length == 0) {      println("数组为空，不能按照二叉树遍历的方式进行遍历")    }    // 向左递归输出左子树    if ((index * 2 + 1) < arr.length) {      infixOrder(index * 2 + 1)    }    // 输出当前节点信息    println(arr(index)) // index 初始化值为0，即对应 root 节点    // 向右递归输出右子树    if ((index * 2 + 2) < arr.length) {      infixOrder(index * 2 + 2)    }  }  // 后序遍历二叉树，即后序遍历数组  // 后序遍历：：先遍历左子树，再遍历右子树，最后输出父节点。  def postOrder(index: Int): Unit = {    if (arr == null || arr.length == 0) {      println("数组为空，不能按照二叉树遍历的方式进行遍历")    }    // 向左递归输出左子树    if ((index * 2 + 1) < arr.length) {      postOrder(index * 2 + 1)    }    // 向右递归输出右子树    if ((index * 2 + 2) < arr.length) {      postOrder(index * 2 + 2)    }    // 输出当前节点信息    println(arr(index)) // index 初始化值为0，即对应 root 节点  }}

输出结果如下：

-----前序遍历(数组)的结果-----1245367-----中序遍历(数组)的结果-----4251637-----后序遍历(数组)的结果-----4526731

19.13 二叉排序树

19.13.1 先看一个需求

需求  给你一个数组 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数组的查询和添加。

解决方案分析1、使用数组  数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢。  数组排序，优点：可以使用二分查找，查找速度快。缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。

2、使用链式存储-链表  不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。

3、使用二叉排序树

19.13.2 二叉排序树的介绍

  二叉排序树：BST: (Binary Sort(Search) Tree)，对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点，比如针对前面的数组 (7, 3, 10, 12, 5, 1, 9)，插入2，则对应的二叉排序树为：

19.13.3 二叉排序树的创建和遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如 数组为 Array(7, 3, 10, 12, 5, 1, 9)。示例代码如下：

package com.atguigu.chapter19.binarytreeobject BinarySortTreeDemo01 {  def main(args: Array[String]): Unit = {    val arr = Array(7, 3, 10, 12, 5, 1, 9)    // 测试    // 创建一颗二叉排序树    val binarySortTree = new BinarySortTree    // 添加节点    for (item <- arr) {      binarySortTree.add(new Node(item))    }    // 遍历二叉排序树    binarySortTree.infixOrder()  }}// 定义二叉排序树class BinarySortTree {  var root: Node = null  // 添加节点  def add(node: Node): Unit = {    if (root == null) {      root = node    }else {      root.add(node)    }  }  // 中序遍历  def infixOrder(): Unit = {    if (root != null) {      root.infixOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }}// 定义某某节点class Node(val value: Int) {  var left: Node = null  var right: Node = null  // 添加节点  def add(node: Node): Unit = {    if (node == null) { // 如果节点为空，则直接返回      return    }    // 如果要插入的节点的值小于当前节点的值    if (node.value < this.value) {      if (this.left == null) { // 说明当前节点没有左子节点        this.left = node      } else {        // 递归地进行添加        this.left.add(node)      }    } else { // 如果要插入的节点的值大于或等于当前节点的值      if (this.right == null) { // 说明当前节点没有有子节点        this.right = node      } else {        // 递归地进行添加        this.right.add(node)      }    }  }  // 中序遍历：先遍历左子树，再输出父节点，再遍历右子树。  def infixOrder(): Unit = {    // 向左递归输出左子树    if (this.left != null) {      this.left.infixOrder()    }    // 输出当前节点信息    printf("节点信息 no=%d \n", value)    // 向右递归输出右子树    if (this.right != null) {      this.right.infixOrder()    }  }}

输出结果如下：

节点信息 no=1 节点信息 no=3 节点信息 no=5 节点信息 no=7 节点信息 no=9 节点信息 no=10 节点信息 no=12

19.13.4 二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑  1) 删除叶子节点 (比如：2, 5, 9, 12)，即该节点下没有左右子节点  2) 删除只有一颗子树的节点 (比如：1)，即该节点有左子节点或者右子节点  3) 删除有两颗子树的节点. (比如：7, 3, 10)，该节点有左子节点和右子节点  

思路分析完整代码如下：

package com.atguigu.chapter19.binarytreeobject BinarySortTreeDemo01 {  def main(args: Array[String]): Unit = {    val arr = Array(7, 3, 10, 12, 5, 1, 9, 2)    // 测试    // 创建一颗二叉排序树    val binarySortTree = new BinarySortTree    // 添加节点    for (item <- arr) {      binarySortTree.add(new Node(item))    }    // 中序遍历二叉排序树    binarySortTree.infixOrder()    println("----------删除节点----------")    // 测试删除叶子节点    // binarySortTree.delNode(2)    // binarySortTree.delNode(5)    // binarySortTree.delNode(9)    // binarySortTree.delNode(12)    // 中序遍历二叉排序树    // binarySortTree.infixOrder()    // 测试删除只有一颗子树的节点    // binarySortTree.delNode(1)    // 中序遍历二叉排序树    // binarySortTree.infixOrder()    // 测试删除有两颗子树的节点    binarySortTree.delNode(7)    // 中序遍历二叉排序树    binarySortTree.infixOrder()  }}// 定义二叉排序树class BinarySortTree {  var root: Node = null  // 添加节点  def add(node: Node): Unit = {    if (root == null) {      root = node    } else {      root.add(node)    }  }  // 中序遍历  def infixOrder(): Unit = {    if (root != null) {      root.infixOrder()    } else {      println("当前二叉树为空，不能遍历")    }  }  // 根据值，查找某个节点  def search(value: Int): Node = {    if (root != null) {      return root.search(value)    } else {      return null    }  }  // 根据值，查找某个节点的父节点  def searchParent(value: Int): Node = {    if (root != null) {      return root.searchParent(value)    } else {      return null    }  }  // 删除叶子节点 (比如：2, 5, 9, 12)，即该节点下没有左右子节点  // 删除只有一颗子树的节点 (比如：1)，即该节点有左子节点或者右子节点  // 删除有两颗子树的节点. (比如：7, 3, 10)，该节点有左子节点和右子节点  def delNode(value: Int): Unit = {    if (root == null) {      return    }    // 根据值，查找某个节点    val tagetNode = search(value)    if (tagetNode == null) {      return    }    // 程序能执行到这里说明找到要删除的节点了    // 根据值，查找某个节点的父节点    val parentNode = searchParent(value)    // 要删除的节点 tagetNode 是不是叶子节点    if (tagetNode.left == null && tagetNode.right == null) { // tagetNode是 叶子节点      if (parentNode.left != null && parentNode.left.value == value) { // 该叶子节点 tagetNode 是父节点 parentNode 的左子节点        parentNode.left = null      } else { // 该叶子节点 tagetNode 是父节点 parentNode 的右子节点        parentNode.right = null      }    } else if (tagetNode.left != null && tagetNode.right != null) { // 要删除的节点 tagetNode 有两颗子树      // 找到删除节点的右子树的最小值，删除并返回最小值      val value = delRightTreeMin(tagetNode)      // 将要删除的节点的值替换为最小值      tagetNode.value = value    } else { // 要删除的节点 tagetNode 只有一颗子树      if (tagetNode.left != null) { // 要删除的节点的左子节点不为空，右子节点为空 <= 注意        // 判断 tagetNode 是 parentNode 的左子节点还是右子节点        if (parentNode.left.value == value) { // 左子节点          parentNode.left = tagetNode.left        } else { // 右子节点          parentNode.right = tagetNode.left        }      } else { // 要删除的节点的左子节点为空，右子节点不为空 <= 注意        // 判断 tagetNode 是 parentNode 的左子节点还是右子节点        if (parentNode.left.value == value) { // 左子节点          parentNode.left = tagetNode.right        } else { // 右子节点          parentNode.right = tagetNode.right        }      }    }  }  // 要删除的节点的右子树的最小值的节点，并返回最小值  def delRightTreeMin(node: Node): Int = {    var tagetRight = node    // 循环找到要删除的节点的右子树的最小值    while (tagetRight.left != null) {      tagetRight = tagetRight.left    }    val minValue = tagetRight.value    delNode(minValue)    return minValue  }}// 定义某某节点class Node(var value: Int) {  var left: Node = null  var right: Node = null  // 添加节点  def add(node: Node): Unit = {    if (node == null) { // 如果节点为空，则直接返回      return    }    // 如果要插入的节点的值小于当前节点的值    if (node.value < this.value) {      if (this.left == null) { // 说明当前节点没有左子节点        this.left = node      } else {        // 递归地进行添加        this.left.add(node)      }    } else { // 如果要插入的节点的值大于或等于当前节点的值      if (this.right == null) { // 说明当前节点没有有子节点        this.right = node      } else {        // 递归地进行添加        this.right.add(node)      }    }  }  // 中序遍历：先遍历左子树，再输出父节点，再遍历右子树。  def infixOrder(): Unit = {    // 向左递归输出左子树    if (this.left != null) {      this.left.infixOrder()    }    // 输出当前节点信息    printf("节点信息 no=%d \n", value)    // 向右递归输出右子树    if (this.right != null) {      this.right.infixOrder()    }  }  // 根据值，查找某个节点  def search(value: Int): Node = {    // 先判断当前节点是否是要删除的节点    if (value == this.value) {      return this    } else if (value < this.value) { // 不是，向左递归查找      if (this.left == null) {        return null      } else {        return this.left.search(value)      }    } else { // 不是，向右递归查找      if (this.right == null) {        return null      } else {        return this.right.search(value)      }    }  }  // 根据值，查找某个节点的父节点  def searchParent(value: Int): Node = {    // 先判断当前节点的左子节点的值或右子节点的值是否是要查找的值    if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) { // 是      return this    } else { // 不是，向左递归查找或者向右递归查找      if (this.left != null && value < this.value) { // 先判断向左的条件        return this.left.searchParent(value)      } else if (this.right != null && value > this.value) { // 先判断向右的条件        return this.right.searchParent(value)      } else {        return null      }    }  }}

输出结果如下：

节点信息 no=1 节点信息 no=2 节点信息 no=3 节点信息 no=5 节点信息 no=7 节点信息 no=9 节点信息 no=10 节点信息 no=12 ----------删除节点----------节点信息 no=2 节点信息 no=3 节点信息 no=5 节点信息 no=1 节点信息 no=9 节点信息 no=10 节点信息 no=12 

19.14 其它二叉树

  1、线索二叉树：利用没有用到的节点反向指向其父节点。  2、赫夫曼二叉树(哈夫曼树/最优二叉树) [数据编码、解码 和 数据压缩、解压]  3、平衡二叉树(平衡二叉搜索树/AVL树) 常用的实现方法有：红黑树、替罪羊树、伸展树等  4、B树  5、B+树  6、2-3树  7、图

柚子快报邀请码778899分享：大数据技术之

http://www.51969.com/

查看原文