正文

201723062018-2019-2《java程序设计与数据结构》第七周学习总结(代码片段)

lc1021  lc1021  2023-01-14  639

关键词：

20172306 2018-2019-2 《Java程序设计与数据结构》第七周学习总结

教材学习内容总结

概述
- 二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。
- 二叉查找树的定义是二叉树定义的扩展。
- 二叉查找树的各种操作：addElement ，removeElement ，removeAllOccurrences(从树中删除所指定元素的任何存在) ，removeMin ，removeMax ，findMin ，finMax
用链表实现二叉查找树
- 每个BinaryTreeNode对象要维护一个指向结点所存储元素的引用，另外还要维护指向结点的每个孩子的引用。
- addElement操作（假设：根结点为node）
  - （1）如果树为空，则插入的element为根结点
  - （2）如果树不为空，element<node，且node的左孩子为null，则null的空为element；如果node的左孩子不为null，则继续遍历根的左孩子，再进行操作。
  - （3）如果树不为空，element>= node,且node的右孩子为null，则null的空为element；如果node的右孩子不为null，则继续遍历根的右孩子，再进行操作。
- removeElement操作
  - 与前面的线性结构研究不同，这里不能简单地通过删除指定结点的相关引用指针而删除该结点。相反，这里必须推选出另一个结点来代替要被删除的那个结点。受保护方法replacement返回指向一个结点的引用，该结点将代替要删除的结点。
  - 替换的replacement的代码如下：
```
private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) 
    BinaryTreeNode<T> result = null;
    if ((node.left == null) && (node.right == null)) 
        result = null;
     else if ((node.left != null) && (node.right == null)) 
        result = node.left;

     else if ((node.left == null) && (node.right != null)) 
        result = node.right;
     else 
        BinaryTreeNode<T> current = node.right;// 初始化右侧第一个结点
        BinaryTreeNode<T> parent = node;

        // 获取右边子树的最左边的结点
        while (current.left != null) 
            parent = current;
            current = current.left;
        

        current.left = node.left;

        // 如果当前待查询的结点
        if (node.right != current) 
            parent.left = current.right;// 整体的树结构移动就可以了
            current.right = node.right;
        

        result = current;
    
    return result;
```
- 选择替换结点的三种情况：
  - 如果被删除结点没有孩子，则replacement返回null
  - 如果被删除结点只有一个孩子，则replacement返回这个孩子
  - 如果被删除结点有两个孩子，则replacement会返回中序后继者（因为相等元素会放到右边）
- 对于这个删除，有几种情况：
  - （1）要删除的结点无孩子结点；删除方法：直接删除该结点
  - （2）要删除的结点只有左孩子结点；删除方法：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点；
  - （3）要删除的结点只有右孩子结点；删除方法：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
  - （4）要删除的结点有左、右孩子结点；删除方法：找中序后继者，用它的值填补到被删除节点中，再来处理该结点的删除
- removeAllOccurrences操作
  - 我觉得这个操作主要还是利用removeElement。和removeElement不同的是，我们会利用一个find的操作来判断有没有这个targetElement的存在，有的话，就继续利用removeElement的相关方法进行删除。没有这个targetElement就抛出异常。
```
public void removeAllOccurrences(T targetElement) 
    removeElement(targetElement);//在我看来就是利用了之前的删除元素的方法

    try 
        while (contains((T) targetElement))
            removeElement(targetElement);
    

    catch (Exception ElementNotFoundException) 
    
```
- removeMin操作（二叉查找树的最右侧结点会存放最大元素，最左侧结点会存放最小元素）
  - 我认为removeMax和removeMin的原理是相同的，懂了removeMin就会removeMax了。
  - 最小元素的位置的3种情形：（假设：树根是root）
    - （1）如果root没有左孩子，则root为min，root的右孩子就会变成新的root
    - （2）如果树的最左侧结点是一片叶子，则这个叶子就是min，这时只需设置其父结点的左孩子引用为null
    - （3）如果树的最左侧结点是一个内部结点，则需要设置其父结点的左孩子引用指向这个将删除结点的右孩子
用有序列表实现二叉查找树
- 树的主要使用之一就是尾其他集合提供高效的实现
- add和remove操作都会对树的平衡有影响，而这一点同时对所使用的算法的分析也有影响
平衡二叉查找树
- 如果二叉查找树不平衡其效率可能比线性结构的还要低
- 右旋：a.根的左孩子为新的根元素；b.原根成为新根的右孩子；c.原根的左孩子的右孩子为原根的新的左孩子。（如果是因为树根左孩子的左子树中较长的路径而导致的不平衡，右旋可以解决它）
- 左旋：a.根的右孩子为新的根元素；b.原根成为新根的左孩子；c.原根的右孩子的左孩子为原根的新的右孩子。（对于由树根右孩子的右子树中较长路径而导致的不平衡，左旋可以解决它）
- 右左旋：先将子树中左旋变成右子树比较长的，然后右旋。
- 左右旋：先将子树中右旋变成左子树比较长的，然后左旋。
- 了解了左旋和右旋，其实右左旋和左右旋都是在这两个的基础上进行的。
这两种二叉查找树：我们以上的这几种操作都是在平衡二叉查找树的条件下进行的，而AVL树和红黑树就是将不是平衡的树变成平衡树。
树只有两个途径能变得不平衡：插入结点和删除结点。
- 原因：我认为是根据之前的插入和删除的操作，可以知道在插入和删除的时候，会对树的长度发生很大的变化，所以极可能导致不平衡。
对于AVL树和红黑树，都要从插入和删除结点的位置需要上溯树，所以通常最好实现为每个结点都包含一个指向其父结点的引用。
实现二叉查找树：AVL树
- 平衡化树的一般性方法：其中自树根而下的路径最大长度必须不超过logn，而且自树根而下的路径最小长度必须不小于logn-1。
- 平衡因子：其左右子树的高度差（即右子树的高度减去左子树的高度）——大于1或者小于-1，则以该结点为树根的子树需要重新平衡。
- 我认为对于AVL的右旋、左旋、右左旋、左右旋的过程和之前的没有区别，我们学习AVL树的就是，它注明了平衡因子，而这个就是为了我们在看到一个树时，判断是利用哪种旋的方式的。
实现二叉查找树：红黑树
- 红黑树的样子：
- 其中白色代表红色，黑色代表黑色。
- 结点存储一种颜色（红色或黑色，通常用一个布尔值来实现，false等价于红色）
- 规则
  - （1）根结点为黑；
  - （2）叶子的结点也为黑，因为每个叶子后面的都跟着一个null，null是黑色结点，所以是黑色结点。
  - （3）红结点的所有孩子都为黑色；
  - （4）从树根到树叶的每条路径都包含同样数目的黑色结点
- 由于红色结点不能有红色孩子，所以路径中至多有一半结点是红色结点、至少有一半结点是黑色结点
- 插入
  - 一般设置要插入结点的颜色为Red。
  - 插入时分为三种情况：
    - 被插入为根结点，那么就直接染色为黑色
    - 被插入结点的双亲结点为黑色，不用做，因为对于黑色没有什么影响。
    - 被插入结点的双亲结点为红色，这就会有三种情况：
      - case1：当前结点的双亲结点A为红色，且其祖父的另一个子结点为红：
      - case2：当前结点的双亲结点A为红色，且其叔叔结点为黑色，且其为其双亲结点的右孩子：
      - case3：当前结点的双亲结点是红色，其叔叔结点为黑色，当前结点是其双亲结点的左孩子：
- 删除
  - 有三种情况：
    - one：要删除结点没有孩子结点：直接删除
    - two：要删除结点只有一个孩子结点：直接使用其孩子结点代替要删除结点
    - three：要删除结点有左右孩子结点:要考虑后继结点的问题

教材学习中的问题和解决过程

问题1：在书中说，LinkedBinarySearchTree类提供了两个构造函数，这两个函数都只是引用了其超类（LinkedBinaryTree类），但是好像很少听到超类这个词
问题1解决方案：我上网查了下，就暴露了我以前书看的不好的问题了。原来超类就是父类啊。

public class A//定义类A

public class B extends A//定义类B，继承类A

则，类A就是超类或父类，类B叫子类

问题2：书中这句，如果被删除结点有两个孩子，则replacement会返回中序后继者，中序后继者这个词我没有理解？
问题2解决方案：这个位置我回到第十章那个中序遍历那看了一眼。用一个图来表示我的收获。

而且我还得到了，其实中序后继者，就是找这个要删除的结点的右子树中最小的那个值，这个值就是中序后继者。
问题3：书中的红黑树部分说，规则之一是从树根到树叶的每条路径都包含同样数目的黑色结点，但是书中有个图
问题3解决方案：这个是不对的，因为不符合规则中的每条路径的黑色结点相同；且这个可以看出，对于红黑树，它的平衡性不是特别的严格。

代码调试中的问题和解决过程

问题1：在对LinkedBinarySearchTree进行测试时，出现了这样的问题。，它出现了地址。
问题1解决方案：最开始我觉得肯定没问题啊，后来出现这样了。这个问题其实挺普遍的，是toString方法没写的缘故，我忘记写了！！！它这个也是树，所以我直接就将第十章的printTree的给拿过来了。

代码托管

技术分享图片

上周考试错题总结

上周没有错题

结对及互评

点评模板：

博客中值得学习的或问题：
- 内容总结的比较详细

点评过的同学博客和代码

本周结对学习情况
- 20172325
- 结对照片
- 结对学习内容
  - 一起学习了第十一章的内容
  - 一起进行了编程十一章的作业

其他（感悟、思考等，可选）

    觉得吧，这一章的红黑树真的是迷的一批，我都看不懂，只能慢慢看，但是这一章的内容在第十章的基础上再看的话，我就觉得好像比刚接触树时更懂点了，而且我还在书中把一些转换的过程自己试了试，尽力的搞懂它，我觉得这也算是一种进步吧。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	0/0	1/1	6/6
第二周	985/985	1/1	18/24
第三周	663/1648	1/1	16/40
第四周	1742 /3390	2/2	44/84
第五周	933/4323	1/1	23/107
第六周	1110/5433	2/2	44/151
第七周	/	1/1	56/207

参考资料

201723062018-2019《程序设计与数据结构》第四周总结(代码片段)

201723062018-2019-2《Java程序设计》第四周学习总结教材学习内容总结列表集合列表集合是一种概念性表示法，其思想是使事物以线性列表的方式进行组织，没有内在的容量大小，它可以随着需要而增大。列表集合的三种类型：有序... 查看详情

java协程框架quasargradle配置

https://github.com/puniverse/quasar-gradle-template/blob/master/gradle/agent.gradle1、将其中的"-javaagent:${configurations.quasar.singleFile}"改为 "-javaagent:${configurations.quasar.iterator().next()}" 查看详情

java基础之流程语句(代码片段)

JAVA流程语句有几下几种：一、if语句：1.if语句：如果满足条件语句，则执行执行语句；　　　if(条件语句)　　　　执行语句；　　　　　....；　　　2.if....else语句：如果满足判断语句，则执行执行语句1，否则执行执行语句2；... 查看详情

java示例代码_在拖放过程中接收关键事件&；滴

java示例代码_在拖放过程中接收关键事件&；滴查看详情

java基础之流程控制

一、顺序结构顺序结构的程序语句只能被执行一次。如果您想要同样的操作执行多次,，就需要使用循环结构。　　if-else-if语句语法：　　if(条件){ 　　当条件为true时，执行大括号内... 查看详情

java示例代码_JAVA：如何从首选项页面访问文件路径并在编程代码中使用它

java示例代码_JAVA：如何从首选项页面访问文件路径并在编程代码中使用它查看详情

java篇之流程控制语句

条件判断语句条件语句：If(boolean类型)else (打大括号避免出错) switch(export)语句：export的类型必须是byte,short,char,int,Stringenum;Switch(export)｛Case(n):语句；Break;（不输入它的话会顺序执行下一分支，遇到才会跳... 查看详情

Flutter - 将 Java 例程转换为颤振

...英文标题】：Flutter-ConvertJavaroutinetoflutter【发布时间】：2019-11-0519:19:44【问题描述】：我有一个androidjava模式，我想在颤振中转换成类似的东西。这很简单，但我很难找到一个明确的例子。这涉及到有一个实用程序类来执行重复... 查看详情

阿花宝宝java基础笔记之流程控制

1.语法：if(条件1){ //代码1 }elseif(条件2){ //代码块2& 查看详情

java开发人员在编程中常见的雷！

身为一名Java从业人员，其职场生涯就是一边踩“坑”，一边上升的过程。这个过程中不仅要学会修改无数bug，也要学会越过很多“坑”。今天，千锋老师为大家分享一些Java开发人员在编程中常见的雷，希望同... 查看详情

对比java学kotlin协程简史(代码片段)

...多线程3.2回调3.3Promise3.4响应式编程3.5协程及常见实现3.5.1JavaScript3.5.2Dart3.5.3Kotlin3.5.4Swift3.5.5Go四、参考文献如果说大前端开发有什么金规铁律的话，那「不要阻塞主线程」肯定算一查看详情

对比java学kotlin协程简史(代码片段)

java学习之流程控制语句（选择结构）

...f语句if语句是指如果满足某种条件，就进行某种处理。在Java中，if语句的具体语法格式如下：if(条件语句){ 执行语句; ……}接下来通过一段代码，学习一下if语句的具体用法，IfDemo01.java在上述代码中，... 查看详情

如何在 UniObjects for Java 子例程调用中指定 LIBPATH？

】如何在UniObjectsforJava子例程调用中指定LIBPATH？【英文标题】：HowcanIspecifytheLIBPATHonaUniObjectsforJavasubroutinecall?【发布时间】：2012-01-2017:38:33【问题描述】：通过UOJ调用UniSubroutine时，由于LIBPATH设置，我遇到了xml错误。参考U2知识库... 查看详情

劲爆！java协程终于来了(代码片段)

点击关注公众号，Java干货及时送达出品|OSC开源社区（ID：oschina2013)从JDK19的概述页面来看，JDK19处于RampdownPhaseTwo阶段，整个功能集已被冻结，将不再对JEP进行改动。Java19只有7个新特性：405:RecordPatterns(Pr... 查看详情

阿花宝宝java基础笔记之流程控制

1.各循环可互相嵌套一般不超过三层外层循环变量变化一次，内层循环变量要变化一遍注意点：循环次数。（内层循环次数*外层循环次数）2.break语句的使用 break语句用于终止某个循环，使... 查看详情

java程序猿之流程控制与数组

　　分支语句　　if括号里的只能是一个逻辑表达式，即这个表达式返回的值只能是true或false。　　代码块用花括号括起来，一个代码块通常被当成一个整体来执行（除非遇到return、break、continue等关键字，或者遇到异常）。　　... 查看详情