数据结构与算法（Java语言版）课件 第9章 二叉树与TreeSet类

第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