20182310第九周学习总结

《数据结构与面向对象程序设计》第九周学习总结

教材学习内容总结

• 1.二叉查找树（binary search tree）：二叉树定义的扩展，一种带有附加属性的二叉树。附加属性是什么？树中的每个节点，其左孩子都要小于其父节点，而父节点又小于或等于其右孩子。

• 2.堆排序
  
  

• 3.关于堆排序的内容：
  原理：根据堆的有序属性，将列表的每一个元素添加到堆中，然后一次一个的把他们从根中删除。
  堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)。
  堆排序时间复杂度O(nlogn)。
  步骤：
  步骤一：构造初始堆。将给定无序序列构造成一个堆（升序采用小顶堆，降序采用大顶堆)。
  步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

• 4.删除元素（removeElement）：
  在二叉查找树中删除一个给定的结点p有三种情况：

(1)结点p无左右子树，则直接删除该结点

(2)结点p有左子树（右子树），则把p的左子树（右子树）接到p的父节点上

(3)左右子树同时存在,找到结点p的中序直接后继结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的右子树总最左的结点，因而s无左子树，删除结点s.

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

• 问题1：关于树，高度和深度究竟有什么区别？

• 问题1解决方案：高度和深度一组相反的概念
  高度是指当前结点到叶子结点的最长路径，如所有叶子结点的高度都为0。
  深度则是指从根结点到当前结点的最大路径长度，如根结点的深度为0。
  高度就是从要计算的结点开始寻找最远路径长度，深度就是从根结点到该结点的最大路径长度；在一棵树中，高度+深度 = 树中最远的路径长度。

• 问题2：关于用链表实现堆，在敲完书本代码BinaryTreeNode后，还是有很多不了解的地方

• 问题2解决方案：因为要求插入元素以后能够向上遍历，所以堆中的结点必须存储指向双亲的指针。继承BinaryTreeNode类，并且添加双亲指针和对应的set方法。
  关于add element操作
  addElement操作：
  在适当位置添加一个元素。
  对堆进行重排序，以保持其有序属性。

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

• 问题1：代码中未能实现树形输出，在本应该出现树形图案的地方出现如下情况：
  

• 问题1解决方案：在上网查阅资料，查询博客之后发现问题，修改toString方法，输出树状图案。

代码托管

上周考试错题总结

上周没有进行考试，所以没有错题。

结对及互评

评分标准

• 博客中值得学习的或问题：
  • 学习：在总结问题时有附上详细的图片，而我总是忘记截图，代码中出现的问题也能及时自己发现错误来源。
  • 问题：教材学习内容总结不够详细。
• 代码中值得学习的或问题：无
• 基于评分标准，我给本博客打分：15分。得分情况如下：

1. 正确使用Markdown语法（加1分）：
2. 模板中的要素齐全（加1分）

3. 教材学习中的问题和解决过程, 一个问题加1分（）

4. 代码调试中的问题和解决过程, 一个问题加1分（）
5. 本周有效代码超过300分行的（加2分）
6. 其他加分：
   • 感想，体会不假大空的加1分
   • 排版精美的加一分
   • 进度条中记录学习时间与改进情况的加1分
   • 有动手写新代码的加1分
   • 课后选择题有验证的加1分
   • 错题学习深入的加1分
   • 点评认真，能指出博客和代码中的问题的加1分
   • 结对学习情况真实可信的加1分

点评过的同学博客和代码

• 本周结对学习情况
  • 20182305
  • 结对照片
• 上周博客互评情况
  • 20182305
  • 20182327

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

最近学习的都是数据结构的知识，相对应的代码量也变得多了起来，作业和课堂实践也变多了。但是博客还是应该要认真完成，不忘初心，继续努力！

学习进度条

20182310第九周学习总结

原文：https://www.cnblogs.com/tursws/p/11854934.html