关键词：

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

教材学习内容总结

第十一章 二叉查找树

• 树是一种非线性结构，其中的元素被组织成一个层次结构
• 含有m个元素的平衡n元树具有的高度为lognm

• 树的数组实现之计算策略：

  如果我们存储的树不是完全的或者只是相对完全的，则该数组会为不包含数据的树位置分配空间
  

• 树的数组实现之模拟链接策略：

  这种方式使得元素能够连续存储在数组中，因此不会浪费空间，但是该方式增加了删除树中元素的成本。
  

• 树的遍历
  1.先序遍历
  即根节点在左右子树之前遍历：
  先访问根节点
  再先序遍历左子树
  再先序遍历右子树
  退出
  2.中序遍历
  先中序遍历左子树
  再访问根节点
  再中序遍历右子树
  退出
  3.后序遍历
  即根节点在左右子树之后遍历：
  先后序遍历左子树
  再后序遍历右子树
  最后访问根节点
  退出
  4.层序遍历
  即从根节点开始，访问每一层的所有结点，一次一层
  

以上图为例，三种遍历结果：

先序遍历：
1 2 4 5 7 3 6

中序遍历：
4 2 7 5 1 3 6

后序遍历：
4 7 5 2 6 3 1

层序遍历：
1 2 3 4 5 6 7

• 二叉树的ADT
  

• 二叉树

  二叉树是有限个节点的集合，这个集合可以是空集，也可以是一个根节点和至多两个子二叉树组成的集合，其中一颗树叫做根的左子树，另一棵叫做根的右子树。简单地说，二叉树是每个节点至多有两个子树的树

• 完全二叉树

  完全二叉树是一种特殊的二叉树，满足以下要求：
  1.所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；
  2.第 k 层可是不是慢的，但是第 k 层的所有节点必须集中在最左边。
  简单地说, 就是叶子节点都必须在最后一层或者倒数第二层，而且必须在左边。任何一个节点都不能没有左子树却有右子树。

• 满二叉树

  如果一棵树的高度为 k,且拥有 2^k-1 个节点，则称之为 满二叉树。
  就是说，每个节点要么必须有两棵子树，要么没有子树。

• 满二叉树 和 完全二叉树 的对比图
  

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

• 问题：链式二叉树中的find方法只能用在contain方法里,能不能返回一个BinaryTreeNode对象 ，便于往树中添加新的元素
• 问题解决方案：
  1.find方法源代码
  

  public T find(T targetElement) 
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
      

返回BinaryTreeNode对象的find方法代码

public BinaryTreeNode<T> findNode(T targetElement) 
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return current;
      

2.经过对代码的深入理解发现这种方法并不可行，因为这样新加入的元素并不能是一个单独的LinkedBinaryTree（链式二叉树）对象，只是一个BinaryTreeNode（二叉树结点）对象，这样会导致新插入的元素不能使用链式二叉树类里的方法。

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

• 问题：背部诊断器类运行时一直报错
  

• 问题解决方案：
  经过单步调试发现是因为我的LinkedBinaryTree类里的getLeft方法和getRight方法返回的是BinaryTreeNode对象而不是LinkedBinaryTree对象,
  对两个方法进行修改后终于使问题得到解决
  1.修改前的getLeft方法和getRight方法代码
  

//返回结点的左侧子结点
    public BinaryTreeNode<T> getLeft() 
        return left.root;
    
    //返回结点的右侧子结点
    public BinaryTreeNode<T> getRight() 
        return right.root;
      

1. 修改后的getLeft方法和getRight方法代码
   

   public LinkedBinaryTree<T> getLeft() 
        return left.root;
    
    //返回结点的右侧子结点
    public LinkedBinaryTree<T> getRight() 
        return right.root;
        

代码托管

上周考试错题总结

上周无错题！！！

结对及互评

• 本周结对学习情况
  本周主要对链式二叉树进行了较为深入的学习，在学习的过程中遇到了诸多较难的问题，有的问题我们两个也是都摸不着头脑，但是通过查阅相关的资料最终使问题得到了解决！
  • 20172307

感想

本周的主要学习内容是对树的概念进行了较为深入的了解，并且对链式二茬表的实现进行了学习和实现，本章课本的例题代码比较复杂（对我来说很复杂了），在阅读代码的过程中也是花费了不少时间，通过对本章的学习也是认识到了我的阅读代码能力还是很差的！希望以后继续努力，让自己在这方面的能力有所提高吧！

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/0	1/1	4/4
第二周	464/464	1/2	10/14	理解掌握了用数组和链表实现栈的方法
第三周	494/958	1/3	10/24	理解掌握了用数组和链表实现队列的方法
第四周	1629/2587	2/5	20/44	对用链表和数组实现列表进行了学习
第五周	856/3443	2/7	15/59	较为深入的学习了查找和排序方法的实现
第六周	668/4111	1/8	20/79	学习了链式二叉树的实现

• 计划学习时间:20小时

• 实际学习时间:20小时

• 改进情况：注重提高阅读复杂代码的能力，努力提高解决代码bug的能力！！！

参考资料

• Java软件结构与数据结构(第4版)
• 重温数据结构：二叉树的常见方法及三种遍历方式 Java 实现

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... 查看详情

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

20172301《程序设计与数据结构》第七周学习总结教材学习内容总结二叉查找树是一种含有附加属性的二叉树，其左孩子小于父结点，父结点小于或者等于右孩子。用链表实现二叉查找树addElement操作：根据给定元素的值，在树中的... 查看详情

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

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

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

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

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

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

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

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

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、什么是二叉查找树：二叉查找树是一种带有附加属性的二叉树，即对树中的每个结点，其... 查看详情