关键词：

20172301 《程序设计与数据结构》第七周学习总结

教材学习内容总结

• 二叉查找树是一种含有附加属性的二叉树，其左孩子小于父结点，父结点小于或者等于右孩子。

用链表实现二叉查找树

• addElement操作：根据给定元素的值，在树中的恰当位置添加该元素。
  • 判断元素是不是Comparable，不是则抛出异常。
  • 树为空：新元素成为根结点。
  • 树非空：新元素与根元素进行比较
    • 小于：如果根的左孩子为空，成为根的左孩子；左孩子不空，遍历添加。
    • 大于：如果根的右孩子为空，成为根的右孩子；右孩子不空，遍历添加。
• removeElement操作：从二叉查找树中删除给定的Comparable元素；找不到则抛出异常。
  • 选择替换结点的三种情况：
    （1）被删除结点没有孩子，replacement返回null；
    （2）被删除结点有一个孩子，replacement返回这个孩子 ；
    （3）被删除结点有两个孩子，replacement返回中序后继者；（处于根结点右子树上）
    
• removeAllOccurrences操作：从二叉查找树中删除指定元素的所有存在。
  • 方法使用了LinkedBinaryTree类的contains方法。
• removeMin操作：
  • 最小元素在二叉查找树的可能情况：
    （1）树根没有左孩子，树根即为最小元素，树根右孩子变成新的根结点；
    （2）树的最左侧结点为一片叶子，该叶子即为最小元素，设置其父结点的左孩子应用为null；
    （3）树的最左侧结点为内部结点，设置其父结点的左孩子引用指向最小元素的右孩子。
    

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

• 问题1：关于书P228页的中序后继者的理解。
• 问题1解决方案：
  • 所谓的中序后继者意思是：中序遍历二叉树结点的后继结点
  • 如何查找中序后继者？
    • 若右子树不为空，则找到右子树最左的叶子节点；
      
    • 若右子树为空，且拥有右父亲节点，则找到右父亲节点；
    • 若右子树为空，且拥有左父亲节点，则找到最近的右祖先节点；
  • 而对于删除结点有两个孩子的情况时，不一定replacement返回中序后继者。也可以返回中继前驱者。 具体的需要看代码实现，而不需要局限于书本。
  • 如何查找中序前驱者？
    • 若左子树不为空，则找到左子树的最右的叶子节点；
    • 若左子树为空，且拥有左父亲节点，则找到左父亲节点；
    • 若左子树为空，且拥有右父亲节点，则找到最近的左父祖先节点；
• 问题2：
• 问题2解决方案：XXXXXX
• ...

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

• 问题1：是否需要定义新的指针类AVLTreeNode，换句话说，AVL树和二叉查找树以及链表实现的二叉树之间的关系。
• 问题1解决方案：

  • 首先，根据书上P240所述

    由于需要上溯树，因此AVL树通常最好实现为每个结点都包含一个指向其父结点的引用。

  • 这里的上溯树是因为，树因为插入结点或者删除结点而变得不平衡，所以每次在进行这两个操作的时候，需要更新平衡因子，从插入或者删除的那个结点开始，检查到根结点。所以，我们的指针类很可能除了指向左右孩子的指针，还需要一个指向父结点的。

  • 其次，根据书上P239所述

    对于树中的每个结点，我们都会跟踪其左、右子树的高度。

  • 由此，指针类会需要一个int型变量height，来得出结点的高度。
  • 在我实现了指针类AVLTreeNode和LinkedAVLTree的平衡方法后，我需要实现添加和删除方法。但是，AVL树和二叉查找树唯一不同的是添加和删除中如果不平衡要进行旋转。 所以，AVL树是可以继承二叉查找树的。
  • 这时，其实我陷入了一个思维误区。我写的指针类AVLTreeNode因此肯定也要继承二叉树指针类BinaryTreeNode。但是，其实根本不用这么麻烦呀！
    直接在BinaryTreeNode构建新的构造方法不就可以了！

  public BinaryTreeNode(T obj, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right,int height)`

  • 存在的问题：
    虽然准确理解了AVL树中旋转平衡的操作，但是并没有整体理解代码与代码之间的关系。花费大量的时间做了无用功，同时让自己陷入了错误的循环。
    如果，我直接发现AVL树是二叉查找树的子类，那我也不会构建新的指针类。
    所以，解决代码问题，首先需要宏观的观察，确定好整体的架构，这便是UML类图的重要性。不然，尽管你细节处理的再完美，方向错了，便是越走越远。

    先设计，考虑所有的情况，再去实现。

• 问题2：链表旋转方法的顺序问题。
• 问题2解决方案：这里以右旋为例。

  • 根据书P238 给出右旋的操作

    • 使树根的左孩子元素成为新的根元素。
    • 使原根元素成为这个新树根的右孩子元素。
    • 使原树根的左孩子的右孩子，成为原树根的新的左孩子。

  • 所以我们实现右旋方法就可以使用一下操作，其中node是原树根，node1是新树根。

  node1 = node.left;
  node1.right = node;
  node.left = node1.right;

  • 然后，添加上更新高度的操作。就可以返回新的根元素。

  node.height = Math.max(height(node.left),height(node.right));
  node1.height = Math.max(height(node1.left),height(node1.right));
  return node1;

  • 运行，首先给我抛出的是StackOverflowError错误。
    

  

  • 当应用程序递归太深而发生堆栈溢出时，抛出该错误。也就是说，方法里出现了死递归。这个问题，我在上周侯泽洋同学的博客中也看见过。

• ...

代码托管

上周考试错题总结

上周无错题，优秀！

结对及互评

点评过的同学博客和代码

• 上周博客互评情况
  • 20172304
  • 20172328

其他

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/0	1/1	10/10
第二周	610/610	1/2	20/30
第三周	593/1230	1/3	18/48
第四周	2011/3241	2/5	30/78
第五周	956/4197	1/6	22/100
第六周	2294/6491	2/8	20/120
第七周	914/7405	1/9	20/140

参考资料

• 二叉树的前驱和后继

20165309第七周学习总结

201653092017-2018-2《Java程序设计》第七周学习总结教材学习内容总结第11章JDBC与MySQL数据库JDBC的操作：(1)与一个数据库建立连接。(2)向数据库发送SQL语句。(3)处理数据库返回的结果。连接数据库P329查询操作得到SQL查询语句对象处理... 查看详情

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

201723322017-2018-2《程序设计与数据结构》第六周学习总结教材学习内容总结第九章继承1.创建子类。子类与父类的关系。子类是父类的其中一种。派生操作在子类中加保留字extends实现。子类的实例化并不依赖于父类的实例化。2.pro... 查看详情

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

学号20172326《程序设计与数据结构》第七周学习总结教材学习内容总结AVL树AVL树是实现平衡二叉树的一种算法实现，别的方法也可实现例如红黑树。平衡因子：右子树高度-左子树高度的差值（高度是指当前结点到叶子结点的最长... 查看详情

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

201723152018-2019-2《程序设计与数据结构》第七周学习总结教材学习内容总结二又查找树是一种含有附加属性的二又树，即其左孩子小于父结点，而父结点又小于或等于右孩子。每个BinaryTreeNode对象要维护一个指向结点所存储元素的... 查看详情

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

201723332018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结《Java软件结构与数据结构》第十一章-二叉查找树一、二叉查找树的概念及相关方法①思路：二叉查找树与普通的二叉树的区别类似于有序链表与无序链表... 查看详情

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

201723132018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结概述二叉查找树：二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。二叉查找树的定义是二叉树定义的... 查看详情

20172311《程序设计与数据结构》第七周学习总结(代码片段)

20172311《程序设计与数据结构》第七周学习总结教材学习内容总结第十一章二叉查找树树是一种非线性结构，其中的元素被组织成一个层次结构含有m个元素的平衡n元树具有的高度为lognm树的数组实现之计算策略：如果我们存储的... 查看详情

201723302018-2019-1《程序设计与数据结构》第七周学习总结

201723302018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结二叉查找树在二叉查找树中：若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；任意节点的右子树不空，则右子树上所有结点... 查看详情

201723102017-2018《程序设计与数据结构》（下）第七周学习总结(代码片段)

201723102017-2018《程序设计与数据结构》（下）第七周学习总结教材学习内容总结本章学习的是二叉查找树11.1概述二叉查找树(binayscarchtree)是种带有附加属性的二叉树，即对树中的每个结点，其左孩子都要小于其父结点，而父结点... 查看详情

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

201723062018-2019-2《Java程序设计与数据结构》第七周学习总结教材学习内容总结概述二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。二叉查找树的定义是二叉树定义的扩展。二叉... 查看详情

20172319《程序设计与数据结构》第七周学习总结(代码片段)

201723192018.10.27-11.02《程序设计与数据结构》第7周学习总结目录教材学习内容总结教材学习中的问题和解决过程代码调试中的问题和解决过程代码托管上周考试错题总结结对及互评学习进度条参考资料教材学习内容总结第十一章... 查看详情

20172322《程序设计与数据结构》第七周学习总结(代码片段)

20172322《程序设计与数据结构》第七周学习总结教材学习内容总结本章的内容主要讲二叉查找树，二叉查找树是对于二叉树的一种拓展，这意味着上一章中对于二叉树的操作对于二叉查找树同样适用，同时它也是一种带有附加属... 查看详情

20172308《程序设计与数据结构》第七周学习总结(代码片段)

教材学习内容总结第十一章二叉查找树一、概述二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，父结点小于或等于右孩子（二叉查找树的定义是二叉树定义的扩展）二、用链表实现二叉查找树addElement操作：ad... 查看详情

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

教材学习内容总结概述二叉查找树：是含附加属性的二叉树，即其左孩子小于父节点，而父节点又小于或等于右孩子。二叉查找树的定义是二叉树定义的扩展。二叉查找树的各种操作用链表实现二叉查找树每个BinaryTreeNode对象要... 查看详情

20165214第七周学习任务(代码片段)

201652142017-2018-2《Java程序设计》第七周学习总结教材学习内容总结11.1介绍了如何下载MySQL社区版，我跟着流程下载成功了。11.2介绍了如何启动MySQL数据库服务器；可以使用mysqadmin-r[用户名]-p[密码]来修改密码。初始化成功后出现... 查看详情

201723282018-2019《java软件结构与数据结构》第七周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第七周学习总结概述Generalization本周学习了第11章：二叉查找树。在本章中，主要探讨了二叉查找树的概念和各种二叉查找树实现，考察为二叉查找树添加和删除元素的算法以及维护平衡... 查看详情

201723052018-2019-1《java软件结构与数据结构》第七周学习总结

201723052018-2019-1《Java软件结构与数据结构》第七周学习总结教材学习内容总结本周内容主要为书第十一章内容：二叉查找树(附加属性的二叉树)二叉查找树是对树中的每个结点，其左结点都要小于其父结点，而父结点又小于或等... 查看详情

2018-2019-20172329《java软件结构与数据结构》第七周学习总结(代码片段)

2018-2019-20172329《Java软件结构与数据结构》第七周学习总结教材学习内容总结《Java软件结构与数据结构》第十一章-二叉查找树一、概述1、什么是二叉查找树：二叉查找树是一种带有附加属性的二叉树，即对树中的每个结点，其... 查看详情