2018201920172321《Java软件结构与数据结构》第六周学习总结

教材学习内容总结

第10章 树

10.1概述

• 树由一个包含结点和边的集构成，其中的元素被储存在这些结点中，边则将一个结点和另一个结点连接起来。

• 一棵树只有一个根节点。

• 树是一种非线性结构，其中的元素被组织成一个层次的结构。

• 10.1.1树的分类

  • 每一结点限制为不超过n个孩子的树称为一颗n元树。结点最多具有两个的树称为二叉树。
  • 平衡树：如果树的所有叶子都位于同一层或者至少是彼此相差不超过一个层，就称之为是平衡的。

  

  • 完全树：如果某树是平衡的，且底层所有叶子都位于shu的左边，则认为该树是完全的。

  

  • 满树：如果一颗n元树的所有叶子都位于同一层且每一结点要么是一片叶子要么正好具有n个孩子，则称次树是满的。

  

10.2实现树的策略

• 10.2.1树的数组实现之计算策略
  • 左孩子存储在（2n+1）处，右孩子存储在（2（n+1））处
  • 左孩子存储在（2n+1）处，右孩子存储在（2（n+1））处
• 10.2.2树的数组实现之计算策略
• 10.2.3树的分析
  • 一般而言，一棵含有m个元素的平衡n元树具有的高度为lognm

10.3树的遍历

• 前序遍历：从根节点开始，访问每一结点及其孩子
• 中序遍历从根节点开始，访问结点的左孩子，然后是该结点，再然后是任何剩余结点
• 后序遍历：从根节点开始，访问结点的孩子，然后是该结点
• 层序遍历：从根节点开始，访问每一层的所有结点，一次一层

• 10.3.1前序遍历
  • A——B——D——E——C——F
• 10.3.2中序遍历
  • D——B——E——A——F——C
• 10.3.3后序遍历
  • D——E——B——F——C——A
• 10.3.4层序遍历
  • A——B——C——D——E——F

10.4二叉树

• 二叉树的操作

public interface BinaryTreeADT 
{
    //返回指向二叉树的引用
    public T getRootElement();
    //判断该树是否为空
    public boolean isEmpty();
    //判断树中的元素数目
    public int size();
    //判断目标是否在该树中
    public boolean contains(T targetElement);
    //如果找到指定元素，则返回指向其的引用
    public T find(T targetElement);
    //返回树的字符串表示
    public String toString();
    //返回一个迭代器
    public Iterator iterator();
    //为数的中序遍历返回一个迭代器
    public Iterator iteratorInOrder();
    //为数的前序遍历返回一个迭代器
    public Iterator iteratorPreOrder();
    //为数的后序遍历返回一个迭代器
    public Iterator iteratorPostOrder();
    //为数的层序遍历返回一个迭代器
    public Iterator iteratorLevelOrder();
}

10.5使用二叉树：表达式树

• 算法思想：
  • 依次读取字符。
  • 如果该符号是操作数，创建操作数结点并且入栈。
  • 如果该符号为操作符，把栈顶T1、T2相继出栈，创建操作符结点，操作符结点的左右孩子分别为T1、T2，最后把操作符结点入栈。

10.7用链表实现二叉树

线性结构和非线性结构

• 线性结构是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
  常用的线性结构有：线性表，栈，队列，双队列，数组，串。
• 非线性结构中各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。根据关系的不同，可分为层次结构和群结构。
  常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。（其中多维数组是由多个一维数组组成的，所以不再是线性结构）

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

• 问题1：问题2：满二叉树和完全二叉树，概念太扯了吧，不懂在说啥
• 问题1解决方案：听王老师讲课大概有点感觉。
  • 满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
  • 完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
  • 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
• 问题2对于树的度，节点的度，树的高度，深度以及节点的层次概念不清楚
• 问题2解决方案：
  • 节点的度分为0，1，2.及表示节点所含的分支个数，上图中3 的度是 2，10 的度是 1。
  • 树的度分为0，1，2即表示一棵树中最大节点的度，即哪个节点的子节点最多，它的度就是树的度，上图中树的度为 2。
  • 树的高度，即从叶子节点开始，自底向上增加。
  • 树的深度与树的高度相反，从根节点向下增加。比如上图中的 6 ，高度是 2 ，深度是 3。

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

第一次我写了测试，出现了这个恐怖的东西，但是我马上意识到了肯定是我Alt+Enter的时候点到了没有修改过的例题那个类里面，那里的所有方法都是return null或者0的

但是再修改运行之后又是这样

之后我自己改了哪些我都不知道了，然后居然就可以了？？？可以了？？以了？了。

代码托管

上周考试错题总结

没有测试

结对及互评

• [20172324曾程]（http://www.cnblogs.com/amberR/p/9670328.html）
• 博客中值得学习的或问题：
  • 内容详略得当；
  • 代码调试环节比较详细；
• 基于评分标准，我给本博客打分：14分。得分情况如下：
  • 正确使用Markdown语法（加1分）
  • 模板中的要素齐全（加1分）
  • 教材学习中的问题和解决过程, 加4分
  • 代码调试中的问题和解决过程, 加4分
  • 本周有效代码超过300分行，加2分
  • 其他加分，加2分
  • 排版精美的加一分
  • 进度条中记录学习时间与改进情况的加1分

学习进度条

参考资料

• 《Java软件结构与数据结构》第四版
• 完全树-学术百科-知网空间
• 完美二叉树, 完全二叉树和完满二叉树