2018-2019学年第六周《Java数据结构与算法》学习总结

### 第六周学习总结：非线性数据结构——树

#### 概述
本周我们深入探讨了第十章的内容，即非线性集合与数据结构——树。树作为一种重要的数据结构，在计算机科学中有着广泛的应用。本章节主要讨论了树的定义、实现方式及实际应用场景。

#### 树的基本概念
树是一种非线性的层次结构，由结点（Node）和边（Edge）组成。以下是树的一些关键术语：

- **根（Root）**：树的顶层唯一结点。
- **孩子（Children）**：位于较低层的结点是上一层结点的孩子。
- **兄弟（Siblings）**：同一双亲的孩子互为兄弟。
- **叶子（Leaf）**：没有孩子的结点。
- **内部结点（Internal Node）**：至少有一个孩子的非根节点。
- **祖先（Ancestor）**：从某一特定结点到根结点路径上的所有结点。
- **子孙（Descendant）**：从根结点到某一特定结点路径上的所有结点。
- **路径长度（Path Length）**：从根结点到该结点的边数。
- **高度（Height）**：从根到最远叶子结点的路径长度。

#### 树的分类
树可以根据其度（Order）进行分类，也可以根据是否平衡进行分类：

- **广义树**：无限制的孩子数目。
- **n元树**：每个结点最多有n个孩子。
- **二叉树**：每个结点最多有两个孩子。
- **平衡树**：所有叶子结点位于同一层或相差不超过一层。
- **完全树**：平衡且底层叶子位于左边。
- **满树**：所有叶子在同一层，每个内部结点有n个孩子。

#### 树的实现方法
树可以通过链式结构或数组实现：

- **链式结构**：使用指针连接各个结点，适合动态变化的树结构。
- **数组实现**：将树元素按特定规则存储在数组中，适用于静态或相对稳定的树结构。

#### 遍历树的方法
遍历树有四种基本方法：

- **前序遍历（Preorder Traversal）**：先访问根结点，再访问左子树，最后访问右子树。
- **中序遍历（Inorder Traversal）**：先访问左子树，再访问根结点，最后访问右子树。
- **后序遍历（Postorder Traversal）**：先访问左子树，再访问右子树，最后访问根结点。
- **层序遍历（Level-order Traversal）**：按层次从上到下逐层访问。

#### 二叉树的应用
表达式树是一种典型的二叉树应用，用于计算后缀表达式。链式结构实现优于数组结构实现，因为链式结构在组合新树时复杂度更低。

#### 学习中的问题及解决

- **问题1**：理解树的数组实现中的模拟链接策略。通过老师的讲解，我明白了这种策略是通过连续分配数组位置来存储树元素，而不是基于树的结构定位。
- **问题2**：理解`ExpressionTreeOp`类中的`termType`变量的作用。这个变量用于区分操作符和操作数，在程序中起到中间值的作用。

#### 代码实现中的挑战

- **问题1**：实现`toString`方法以输出树结构。尝试使用迭代器但未成功，最终未能找到合适的解决方案。
- **问题2**：正确计算树的高度。最初使用了错误的循环逻辑，经过讨论后改为递归查找最远路径。
- **问题3**：运行`BackPainAnalyzer`类时文件找不到。通过添加路径解决了这个问题。

#### 测试活动错题改正

- **问题1**：Java Collections API中索引列表的实现数量。答案选C，但原因尚不明确。
- **问题2**：接口引用可以指向任何实现了该接口的对象。答案选A，正确。

#### 总结
非线性结构的学习标志着我们对更复杂数据结构的理解进一步加深。尽管树结构中仍然存在链表和数组的身影，但我们需要继续努力才能真正融会贯通。

#### 参考资料
- [Java软件结构与数据结构]（第四版）
- JavaAPI文档中List的解释
- Java非线性数据结构 树的深刻研究
- Java数据结构-树及树的存储结构