20182308 2019-2020-1 《数据结构与面向对象程序设计》第9周学习总结

教材学习内容总结

• 结点度数至多为2：至多有两棵子树；
  有序树：子树有左右之分；
  满二叉树：
  完全二叉树：满二叉树，去掉最下层、最右边。

• 堆是一个完全二叉树
  包含同样数据的最小堆：小顶堆；
  包含同样数据的最大堆：大顶堆；
  堆只有上面三种情况；
  堆的插入：插入是作为堆的叶子结点插入，而且需要保持树的完整性。
  堆排序：是选择排序的一种改良，保留了中间的比较元素。

• 二叉排序树：
  二叉排序树上的一种基本搜索操作就是遍历。
  在使用二叉排序树的时候，我们是先从根开始搜索的。如果给定值等于根节点的关键词，就查找成功。如果给定值小于根，就在左子树上找；如果大于，就在右子树上找。
  二叉排序树的平衡化：左旋、右旋、左右旋

• 哈夫曼树也就是最优二叉树：带权路径长度最小的二叉树
  （1）路径长度：连接两个结点的路径上的分支数。
  （2）树的带权路径长度WPL：树中的所有叶子结点的E(X)（长度*概率加权）之和
  哈夫曼编码是已知的最佳无损压缩算法

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

• 问题1：平衡树是什么，完全树又是什么东西？
• 问题1解决方案：平衡树是指叶结点都在同一层或最多两个相邻层中的树；而完全树就是说所有叶结点都在树中尽可能往左边聚集的树。
• 问题2：二叉查找树的所谓“左旋”、“右旋”是什么意思呢？
• 问题2解决方案：左旋和右旋都是一种旋转。而二叉查找树的旋转是将二叉查找树变回平衡状态的一个操作。平衡树是什么，在上一个问题中已经提到了。

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

• 问题1：在实现BSTNode的过程中，BSTNode find (T target)的相关内容总是出红字。而与此相对的，BTNode中的BTNode find (T target)就没有任何的问题。
• 问题1解决方案：再次确认了书上的代码并没有错误，而根据BTNode中的相似部分没有报错也可以确定这个语法没有错误。经过同学提醒问题可能出在细节处，仔细一看果然是少打了一个}.

代码托管

上周考试错题总结

• If a binary search tree is not __________, it may be less efficient than a linear structure.
  A .complete
  B .empty
  C .balanced
  D .None of the above
  错解：A 正解：C
  解析：如题目中说到的那样，如果一个二叉搜索树不平衡，那么它的搜索效率可能不如线性搜索。在课堂中也曾实践证明过。

• A minheap stores its smallest element at the ________ of the binary tree.
  A .leaf
  B .internal node
  C .root
  D .sibling
  错解：A 正解：C
  解析：课堂中提到过这种树，每次都把最小数放到根的位置，然后断掉放进另外一个数组当中进行排序，后取得的这个数组就是有序的数组了。

• What exception is thrown if the pop method is called on an empty stack?
  A .EmptyStackException
  B .NoSuchElementException
  C .ArrayOutOfBoundsException
  D .EmptyCollectionException
  E .none of the above
  错解：A 正解：D
  解析：If a pop method is called on an empty stack, the EmptyCollectionException is thrown.（如果在空堆栈上调用pop方法，则会抛出EmptyCollectionException）这个目前只要记住就好了。

点评过的同学博客和代码

• 本周结对学习情况
  • 20182312
  • 结对学习内容
    • 主要一起看了看实验相关的内容，并且交流了一下左旋、右旋的概念。因为我们两个人最初都把哈夫曼树的算法做错了，所以事后在补博客的时候，他根据离散数学的知识概念教了我一遍哈夫曼树的内容。
• 上周博客互评情况
  • 20182312

其他

这星期课本上的程序和课后习题并不算多，而许多内容都是在课后实践和实验的时候完成的。比如第十七章的代码，许多都是建立在第十六章的BTNode的基础上的，接口也extends，LinkedBinarySearchTree的代码也是对接口的实现，更加体现了Java语言面向对象的特性以及一步错、步步皆错的特点。而且因为实践、实验的许多代码都是基于课本中程序代码的补全和实现，因此在剩下的数据结构部分的学习中，应该先去努力地把课本程序通篇地看一下，然后再根据需要先进行补全，再进行实验和实践。否则即便打出了相关的代码，比如我最早的时候去百度上搜索了BTNode的代码，但是因为和课本中的代码不匹配，所以之后诸多不顺。

学习进度条

• 计划学习时间:25小时

• 实际学习时间:25小时

• 改进情况：没什么改进的地方。

参考资料

• 《Java程序设计与数据结构教程（第二版）》

• 《Java程序设计与数据结构教程（第二版）》学习指导

20182308 华罗晗 2019-2020-1 《数据结构与面向对象程序设计》第9周学习总结

原文：https://www.cnblogs.com/77599aa/p/11890942.html