数据结构与算法（Java语言版）课件 第9、10章 二叉树与TreeSet类、散列表与HashMap类

第9章二叉树与TreeSet类2024/11/919.1二叉树的基本概念2024/11/92一棵树上的每个结点至多有2个子结节点，称这样的树是二叉树。没有任何结点的二叉树被称为空二叉树。一个结点如果有2个子结点，那么把一个称为左子结点，把另一个称为右子结点，如果只有1个子结点，那么这个子结点也要分为是左子结点还是右子结点。2024/11/939.1二叉树的基本概念●左子树与右子树一个结点和它的左、右子结点是父子关系。一个结点的左、右子结点是兄弟关系，二者互称为兄弟结点，即有相同父结点的结点是兄弟结点。●父子关系与兄弟关系把二叉树的一个结点的左子节点看作一个树的根节点的话，那么以左子节点为根的树也是一个二叉树，称作该节点的左子树（如果没有左子结点，左子树是空树），同样把此结点右子节点看作一个树的根节点的话，以右子节点为根的树也是一个二叉树（如果没有右子结点，右子树是空树）。一个树，就是由根结点和它的左子树和右子树所构成。2024/11/949.1二叉树的基本概念●树的层

树用倒置的树形来表示，结点按层从上向下排列，根结点是第0层。二叉树从也是从根开始定义，根为第0层，根的子结点为第1层，以此类推。除了第0层，每一层上的结点和上一层中的一个结点有关系，但可能和下一层的至多2结点有关系。即根结点没有父节点，其它结点有且只有一个父结点，但至多有2个子结点，叶结点没有子结点。2024/11/959.1二叉树的基本概念●满二叉树（FullBinaryTree）每个非叶结点都有两个子结点的是满二叉树。●完美二叉树(PerfectBinaryTree)

2024/11/969.1二叉树的基本概念●完全二叉树(CompleteBinaryTree)完全二叉树从根结点到倒数第二层的结点数目都是满的，最后一层可以不满，但最后一层叶子结点都是靠左对齐（按最后一层从左向右的序号，一个挨着一个靠左对齐），并且从左向右数，只允许最后一个叶子结点可以没有兄弟结点，而且如果最后一个叶子结点没有兄弟结点的话，它必须是左子结点。2024/11/979.1二叉树的基本概念●树的高度与深度一个叶结点所在的层的层数加1（层是从0开始的，只有一个根结点的二叉树高度为1，规定空二叉树的高度是0），称作这个叶节点的高度，所有叶节点中，其高度最大者称为二叉树的高度.从根结点（包括根结点）按照父子关系找到一个叶结点所经历过的结点（包括叶结点）数目，称作这个叶结点的深度。所有叶节点中，其深度最大者的深度称为树的深度。不难得知，树的深度和高度是相等的，只是叙述的方式不同而已。

9.2遍历二叉树2024/11/98遍历二叉树有三种常见的方式，分别是前序遍历，中序遍历和后序遍历。2024/11/999.2遍历二叉树●前序遍历

publicvoidpreOrder(Nodep){//前序遍历if(p!=null){p.visited();//输出ppreOrder(p.left);//递归遍历左子树preOrder(p.right);//递归遍历右子树}}ABDFECG2024/11/9109.2遍历二叉树●中序遍历

publicvoidinOrder(Nodep){//中序遍历if(p!=null){inOrder(p.left);p.visited();inOrder(p.right);}}FDBEACG2024/11/9119.2遍历二叉树●后序遍历FDBECGA

publicvoidpostOrder(Nodep){//后序遍历if(p!=null){postOrder(p.left);postOrder(p.right);p.visited();}}9.3二叉树的存储2024/11/912二叉树的结点的存储方式通常为链式存储，即一个结点中含有一个对象，以及左子结点和右子结点的引用。对于一个没有增加限制的二叉树，给出通用的添加、删除结点的算法是不可能的，理由是在链式存储的二叉树中，要确定一个结点的位置，需要知道它的父结点和它在父结点的位置（是左子结点还是右子结点）。因此，在进行添加或删除操作时，需要先找到要添加或删除的结点的位置，而这个过程会涉及到一系列的判断和遍历操作，因而比较复杂。不同的二叉树可能有不同的限制条件，因此没有通用的算法适用于所有的情况。但是，对于二叉查询树，人么就可以给出有关的算法，见稍后的9.5节。2024/11/9139.3二叉树的存储Node.java例子1例子1中的BinaryTree类负责创建的二叉树，其结点Node是链式存储的。Example9_1.javaBinaryTree.java例子1的主类，使用BinaryTree类创建二叉树，并分别使用前序、中序和后序遍历了这棵二叉树，同时查询了某个对象是否和树上的某个结点中的对象相同.9.4平衡二叉树2024/11/914平衡二叉树：①左子树和右子树深度之差的绝对值不大于1，②左子树和右子树也都是平衡二叉树。

9.5二叉查询树2024/11/915笼统的二叉树很难能形成有效算法，所以本节先给出二叉查询树，然后介绍两种经典的平衡二叉查询树。2024/11/9169.5二叉查询树●二叉查询树二叉查询树（BinarySearchTree，简称BST）的每个结点node都存储一个可比较大小的对象，且满足以下条件①node的左子树中所有结点中的对象都小于node结点中的对象；②node的右子树中所有结点的对象都大于等于node节点的中的对象；③左、右子树都是二叉查询树。如果按中序遍历二叉查询树，输出的对象刚好是升序排列。所以也称二叉查询树是有序二叉树。按中序遍历输出了树上的结点中的数据：ABCDEFG2024/11/9179.5二叉查询树●二叉查询树二叉查询树的任意结点中的对象大于左子结点中的对象，小于等于右子结点中的对象。但是，如果一个二叉树的任意结点中的对象大于左子结点中的对象，小于等于右子结点中的对象，它不一定是二叉查询树.2024/11/9189.5二叉查询树Node.java例子2Example9_1.javaBinaryTree.java例子2中的主类使用例子1的BinaryTree类负责创建了二叉树查询树，并按中序遍历输出了树上的结点中的数据。2024/11/9199.5二叉查询树●平衡二叉查询树

平衡二叉查询树的查找操作非常类似二分法，由于是平衡二叉查询树，查询过程中，结点的数目近似以2的方幂在减少，所以它的查询时间复杂度和二分法的查询时间复杂度相同.2024/11/9209.5二叉查询树Node.java例子3Example9_3.javaBinaryBST.java

平衡二叉查询树129231056191722282024/11/9219.5二叉查询树●红黑树红黑树是一种平衡的二叉搜索树。它的平衡性质的维护主要是通过颜色标记节点等操作来达成。

Java实现的二叉搜索树是红黑树（见稍后的TreeSet类），讲解红黑树，内部算法细节超出了本书的范围。2024/11/9229.5二叉查询树●AVL树AVL树是根据两位发明者Adel’son-Velskii和Landis命名的一种平衡二叉搜索树。

Java实现的二叉搜索树是红黑树（见稍后的TreeSet类），讲解红黑树，以及AVL树的内部算法细节超出了本书的范围。9.5TreeSet树集2024/11/923TreeSet<E>泛型类实现了SortedSet接口。2024/11/9249.6TreeSet树集创建一个TreeSet<E>类的对象必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定树集的结点里的对象的类型。例如，指定E是Integer：TreeSet<Integer>treeOne=newTreeSet<>();或TreeSet<Integer>treeOne=newTreeSet<Integer>();TreeSet类不允许有两个结点的对象相同，即大小一样的对象。

树集使用add(Eobj)方法向树集添加结点。树集使用addAll(Collection<?extendsE>c)方法添加多个结点到树集，结点中的对象可以是参数指定的集合中的结点中的对象。2024/11/9259.6TreeSet树集例子4Example9_4.java例子4中的主类Example9_4中首先创建一个空树集treeOne，然后向空树集treeOne添加4个节点，随后再用treeOne创建树集treeTwo。用新的大小关系创建treeTree，然后向treeTree添加结点，结点中的对象和treeOne的相同。9.6树集的基本操作2024/11/926publicEfirst()返回树集上节点值最小的节点中的对象。publicElast()返回树集上节点值最大的节点中的对象。publicbooeleanadd(Eobj)树集使用该方法向其添加结点，但需要注意的是，如果树集上已经有节点值是obj将无法将值是ob的结点添加到树集上，此时返回false表示添加失败。publicbooleanaddAll(Collection<?extendsE>c)树集使用该方法向其添加多个结点，结点值可以是参数指定的集合中的结点中的对象，即c可以是链表，栈，队列或另一个树集。但需要注意的是，c中如果有相同的对象，只能有一个被添加到树集上。2024/11/9279.7树集的基本操作例子5RandomByTree.java

Example9_5.java双色球的每注投注号码由6个红色球号码和1个蓝色球号码组成。6个红色球的号码互不相同、号码是1至33的随机数；蓝色球号码是1至16的一个随机数。例子5中的主类Exmple9_5使用RandomByTree类的getRandom(intnumber,intn)方法模拟双色球。2024/11/9289.7树集的基本操作例子6ConnectNumber.javaExample9_6.java

例子6的ConnectNumber类的intgetMaxConnectNumber(int…m)方法返回几个正整数最大的连接数，intgetMaxConnectNumber(int…m)返回几个正整数的最小连接数。9.8树集的视图2024/11/929树集是有序集，因此，树集的视图也是有序集，规定视图在添加结点时，不可以添加大于视图中最大值的结点，也不可以添加小于视图中最小值的结点，即对于视图subView，subView添加的结点的节点值不能大于sunView.last()的结点值，不能小于subView.first()的结点值。publicSortedSet<E>subSet(Efrom,Eto)返回树集的一个视图，视图中的结点由树集上结点值大于等于from结点值、小于to结点值的结点所构成。如果from结点值等于to结点值，方法返回null，如果from结点值小于to结点值，会触发运行异常：IllegalArgumentException。2024/11/9309.8树集的视图例子7Example9_7.java例子7的主类Example9_7获取的树集的视图，查询了视图中的结点，并对视图进行了添加和删除结点的操作.树集的视图是树集的一个子集，更改视图的结点（增加或删除节点）都会使得当前树集发生同步的改变，同样地，如果更改树集的结点（增加或删除节点），就也会使得视图发生同步的相应的改变，即树集的视图和原树集会同步变化，这也是视图的本意。9.9树集与数据统计2024/11/931

2024/11/9329.9树集与数据统计例子8Example9_8.java例子8中的主类Example9_8对统计了随机数.9.10树集与过滤数据2024/11/933第4章的4.3曾讲过过滤数组，即去除数组中的某些数据。使用树集来过滤数据会更加方便，而且能发挥树集，在删除、查询方面的速度优势。经常使用下列方法来过滤数据。publicbooleanremoveAll(Collection<?>c)删除节点值在c里的结点publicbooleanretainAll(Collection<?>c)保留节点值在c里的结点publicbooleanremoveIf(Predicate<?superE>filter)删除满足filter给出的条件的结点。2024/11/9349.10树集与过滤数据例子9Example9_9.java例子9中的主类Example9_9的树集使用树集提供的方法实现过滤数据。2024/11/9359.10树集与过滤数据例子10HandleRecurring.java例子10中的HandleRecurring类的handleRecurring(int[]arr)方法处理数组arr中重复的数据，该方法返回的数组中的数据是arr中去掉重复数据后的数据（重复的数据只保留一个）。学习例子10时，注意这样的知识点：如果想动态更改结点的大小关系，就需要使用TreeSet(Comparator<?superE>comparator)构造方法创建一个新的树集newTree，该树集上结点中的对象使用新的大小关系比较大小，然后newTree.addAll(tree)把原树集tree上的结点中的对象添加到新树集newTree上的结点中。Example9_10.java2024/11/9369.11树集与节目单例子11ProgramList.javaExample9_11.java编辑一场舞台演出节目单，最糟糕的是把两个不同的节目安排在了相同的演出时间、引起麻烦。如果使用树集来存放节目单中的节目，就会避免这样的麻烦事情发生，理由是，节目单里的节目按演出时间比较大小，树集能保证树集上不能有大小相同的两个对象。例子11中的ProgramList类按时间比较其实例的大小。例子11的主类Example9_11将节目单的节目存放在树集上，然后输出树集上的节目.第10章散列表与HashMap类2024/11/93710.1散列结构的特点2024/11/938生活中有些数据之间可能是密切相关的一对，例如，一副手套，一双鞋子，一对夫妻等，即数据的逻辑结构是成对的，即不是线性也不是树形结构，一对数据与另一对数据之间也无须有必然的关系。如何存储这样的数据对，也是数据结构非常关心的，以下要介绍的散列结构，就是存储“数据对”的最重用的手段之一.2024/11/93910.1散列结构的特点●散列结构与散列表数据对，也称作"键-值"对，键和值都是某种类的实例，即对象。叙述时可以把这"键-值"对记作(key,value)，称key是关键字、value是键值或值。散列结构使用两个集合存储对象，一个集合称作关键字集合，记作Key。另一个是值的集合，记作Value。Key集合中的节点（或称元素）负责存储关键字，所有关键字对应的全部值称作散列结构的值集合，记作Value，即Value中的节点负责存储值。称Value为散列结构中的散列表（hash表，也常常被音译称作哈希表）。简单说，散列结构是根据关键字直接进行访问数据的数据结构，其核心思想是使用散列函数（hash()函数）把关键字映射到散列表中一个位置，即映射到散列表中的某个节点。2024/11/94010.1散列结构的特点●散列结构与散列表hash()函数本质上就是集合Key到整数集合

2024/11/94110.1散列结构的特点●散列结构与散列表对于一个关键字，比如key1，如果hash(key1)=98，那么key1关键字对应的节点就是数组hashValue第98个元素，即hashValue[98]。2024/11/94210.1散列结构的特点●散列结构与散列表一个散列函数，即hash()函数需保证下列两点：①

对于不同的关键字，比如，key1，key2是Key中两个节点，即两个关键字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是两个不同的节点。但节点中的对象可能是相同的（数组的两个不同的元素中的值可能是相同的）。②为了保证第①点，让hash()函数映射出的全部节点，分散地分布在一块连续的内存中，这也是人们把Value称作一个散列表的原因。由于散列表中的节点是随机、分散分布的，所以我们不在散列表上定义任何关系（见第1章）。散列表或散列二字不是指数据之间的关系，而是形容存储形式的特点（hash()函数映射存储位置）。如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。2024/11/94310.1散列结构的特点●散列结构与散列表如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。可以用链接法解决冲突，散列函数把和关键字key有相同对应的值的那些关键字所对应的存储位置依次设置为一个链表的中不同的节点（链表头节点是key对应的存储位置），这样一来，就会增大查询Value中值的时间复杂度。如果散列函数设计的合理，那么一般不会发生关键字冲突或发生关键字冲突的概率非常小，因此也就不需要使用链式方法解决冲突或使用链式方法解决冲突的概率很小。链接法是最后保证不同关键字对应的不同节点（不同的存储位置）的最后办法。2024/11/94410.1散列结构的特点●查找、添加、删除的特点由散列结构的特点可以知道，使用关键字查找、删除、添加Value中的节点，时间复杂度通常都是

（如果关键字冲突，使用了链接法）散列结构具有数组的优点，即非常快的查询速度，同时又将查询数据（Value）的索引分离到另一个独立的集合中（Key）。数组最大的缺点就是将索引（下标）和数组元素绑定，因此，一旦创建数组，就无法更改索引，即无法再改变数组的长度。而散列结构可以随时添加一个“键-值”对（一个关键字，一个相应的值），或删除一个“键-值”对。10.2简单的散列函数2024/11/945通过简单的例子：停车场，进一步理解散列结构，后面我们将使用Java的HashMap类实现的散列结构。2024/11/94610.2简单的散列函数●顺序扩建停车位当Value中节点的数目越来越多时，比如达到总内存大小的一半时，就要重新调整内存，即分配新的数组，并把原数组hashValue[]的值复制到新的数组中，新的数组成为Value的新的一块连续内存。汽车停车场（模拟散列表）初始状态有10个连续的车位，相当于散列结构中分配给散列表Value的一块连续的内存空间（数组的长度是10）。假设汽车的车牌号是3位数的正整数，相当于散列结构中的Key集合中节点里的关键字。停车场可以根据需要，随时顺序地扩大停车场，即连续地扩建停车位。

2024/11/94710.2简单的散列函数●顺序扩建停车位

2024/11/94810.2简单的散列函数●顺序扩建停车位每当一辆车来到停车场，如果用散列函数计算了若干次，得到的车位号对应的车位上都是已经停放了车辆，这个时候，就扩建停车场、让其容量增加2倍，然后再用散列函数计算车位号……，如此这般，只要内存足够大，总能找到停车位，如图所示意。由于用散列函数的算法是随机的，所以，某个时刻以后，扩建停车场的概率就很小了。2024/11/94910.2简单的散列函数●链式扩展停车位当用散列函数计算出同样的车位数时，比如都是9，就把二者的停车位分别指定为同一个链表中的不同的两个节点，链表的头节点是数组的第9个元素。2024/11/95010.2简单的散列函数例子1Key.javaExample10_1.java例子1中的ParkingOne类使用顺序办法增加停车场的车位，ParkingTwo类使用链式办法增加停车场的车位。Car.javaParkingOne.javaParkingTwo.java例子1中的主类Example10_1模拟了两个停车场的停车情况。10.3HashMap类2024/11/951HashMap<K,V>泛型类继承Map泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了Map泛型接口中的抽象方法。HashMap<K,V>泛型类的对象为散列表,散列表的Key集合是实现Set接口的一个实例，Key集合中不允许有两个结点中的对象相同，即大小一样的两个结点，Key中不同的key对应的Value中的节点是不同的，但Value中的节点中的对象，即数据可以是相同的，就像数组的不同元素（节点）里可以存放相同的数据。HashMap<K,V>泛型类提供的添加、删除、查找等操作的时间复杂度都是O(1).2024/11/95210.3HasMap类HashMap<K,V>泛型类直接实现了Map接口，注意，没有实现SortedMap接口。2024/11/95310.3HasMap类例子2Example10_2.java声明一个HashMap<K,V>泛型类的对象，即散列表，必须要指定Key和Value的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定Key中节点里的对象的类型和Value中节点里的对象的类型。例如，指定K是String类型、V是Car类型，例如：HashMap<String,Car>hashMap=newHashMap<>();或HashMap<String,Car>hashMap=newHashMap<String,Car>();Car.java例子2中的主类Example10_2中首先创建一个空散列表hashMapOne，然后向散列表hashMapOne添加4个”键-值”对，随后再用hashMapOne创建另一个散列表hashMapTwo。10.4散列表的基本操作2024/11/954publicVput(Kkey,Vvalue)向散列表添加”键-值”对，即将key存储在Key中，把value放置在Value中，如果添加成功返回null。需要注意的是，如果散列表Key中已经有了键key，那么当前添加的”键-值”对将替换已存在的”键-值”对，并返回旧”键-值”对中的value值，即返回被替换的”键-值”对的值。publicVputIfAbsent(Kkey,Vvalue)如果散列表Key中没有key，则添加该键值对(key,value)到散列表，并返回null，如果散列表Key中已经有键key，则返回旧key对应的value(不做添加操作)。10.4散列表的基本操作2024/11/955publicVget(Objectkey)返回”键-值”对(key,value)中的value，如果key不在集合Key中，方法返回null。publicbooleancontainsKey(Objectkey)判断Key中是否有关键字key，有返回true，否则返回false。publicbooleancontainsValue(Objectvalue)判断Value中是否有value，有返回true，否则返回false。publicbooleanisEmpty()如果散列表中没有任何"键-值"对，则返回true，否则返回false。10.4散列表的基本操作2024/11/956publicVremove(Objectkey)删除关键字key组合的”键-值”对(key,value)，并返回value。publicVreplace(Kkey,Vvalue)如果散列表Key已有key，就用(key,value)替换已有的key组合的”键-值”对，并返回替换后的value，如果Key中没有关键字key，不进行替换操作，并返回null。publicvoidclear()删除散列表的全部”键-值”对。2024/11/95710.4散列表的基本操作例子3Example10_3.java例子3的主类Example10_3使用了HashMap<K,V>泛型类的一些常用方法。10.5遍历散列表2024/11/958publicvoidforEach(BiConsumer<?superK,?superV>action)对散列表中的所有(key,value)执行给定的action操作，直到所有(key,value)对都被处理或操作引发异常。BiConsumer是一个函数接口，该接口里的抽象方法是voidaccept(Kk,Vv)。使用forEach()方法时将一个Lambda表达式传递给action，例如：（k,v）->{System.out.println(v);}。forEach()方法将Lambda表达式中的k,v，依次取散列表中的(key,value)。2024/11/95910.5遍历散列表例子4Example10_4.java例子4的主类Example10_4将正整数和正整数的平方根（最多保留3位小数）作为(key,value)存放在一个散列表中，然后遍历散列表。10.6散列表与字符、单词频率2024/11/960●每次读取文件的一个字符，如果是字母，并且散列表中还没有(key,value)：(字母,次数)，散列表就添加(key,value)：(字母，次数)，如果散列表中已经有(key,value)：(字母，次数)，就更新该(key,value)：(字母，次数)，将其次数增加1。●每次读取文件的一个单词，如果散列表中还没有(key,value)：(单词，次数)，散列表就添加(key,value)：(单词，次数)，如果散列表中已经有(key,value)：(单词，次数)，就更新该(key,value)：(单词，次数)，将其次数增加1。2024/11/96110.6散列表与字符、单词频率例子5LettersFrequency.java例子5中的LettersFrequency类负责统计文本文件中字符出现的次数和频率，WordsFrequency负责统计文本文件中单词出现的次数和频率。WordsFrequency.javaExample10_5.java例子5中Example10_5.java中的主类Example10_5使用LettersFrequency类统计了Example10_5.java里字母出现的次数和频率，另外一个主类MainClass使用WordsFrequency统计了Example10_5.java里单词出现的次数和频率。10.7散列表与单件模式2024/11/962●单件模式

保证一个类仅有一个实例，并提供一个访问它的全局访问点。散列表可以用来存储已知的数据，在后续的操作中，通过散列表查找是否已经存在，从而实现唯一性验证的功能。因此在实现的具体代码中可以借助散列表来实现单件模式。2024/11/96310.7散列表与单件模式例子6SingletonSun.javaExample10_6.java例子6中的SingletonSun类实现了单件模式，SingletonSun类只能创建一个“太阳”。在例子6中，SingletonSun类中的getInstance()方法检查散列表中是否已经存在当前类的实例对象，如果不存在则创建一个新的，然后将其存储到散列表中，并返回该实例。这样就保证了SingletonSun类在整个程序中只能创建它的一个对象。10.8散列表与数据缓存2024/11/964

2024/11/96510.8散列表与数据缓存例子7Hash.javaExample10_7.java例子7中的Hash类将频繁使用的阶乘放在散列表中(用到第3章例子3中的SumMulti类)10.9TreeMap类2024/11/96610.9TreeMap类2024/11/967在类的层次上，TreeMap<K,V>泛型类HashMap<K,V>泛型类不同，HashMap<K,V>泛型类直接实现Map接口，TreeMap<K,V>泛型类不是直接实现Map接口，而是实现NavigableMap接口，该接口又是SortedMap的子接口，SortedMap接口又是Map的子接口，如图前图。称TreeMap<K,V>泛型类的实例或创建的对象是一个映射树。10.9TreeMap类2024/11/968在存