该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 数据结构的静态操作与动态操作
静态操作(static operation) : search
动态操作(dynamic operation) : insert, remove
| 效率 | Vector | List |
|---|---|---|
| static | O(lgn) | 线性 |
| dynamic | 线性 | O(1) |
因为vector和list在静态或者动态操作中，有一种操作为线性的效率，因此称他们为线性数据结构。
Tree综合了Vector和List的优点，高效地兼顾了静态操作与动态操作。虽然具有线性特征，但是不完全是线性结构，因此可以称之为半线性结构。
2. 有根树与有序树
有根：树本身是一个图，指定图中某个点为root，该图则变成有根树。
有序：在数学上树的孩子可以无序，但是在计算机对树的表示中，需要指定出孩子间所存在的一种有序性，因此称为有序树。
关于树的节点还有边的关系，重要的是：它们的数量级同阶
3. 树结构的特性（与图的区别）
简单来讲，树是一种连通无环图.
- 连通性(connected)：任意两点之间均有路径 -> 边数不会太少
- 无环性(acyclic)：不存在环路 -> 边数不能太多
推论：
任何节点v与root之间存在唯一的path
- 对于半线性的另一种理解：前驱(prev)只有一个，唯一确定，后继(succ)可以有多个，不确定。
4. 树的表示
“长子兄弟(1st-child & sibling)”法：每个节点维持两个指针，一个指针指向第一个child node，另一个指针指向后一个sibling node。
5. 二叉树
5.1 性质
节点数最少与高度h同阶，最多可以是高度h的幂指数级。
5.2 表示与实现
6. 二叉树的遍历
通过遍历，将半线性结构的树转换为完全线性结构的遍历序列，使某些问题得到简化。
按照节点被访问的顺序分类：先序(pre-order)，中序(in-order)，后序(post-order)，层次(level-order)
特点：每个节点只被访问一次，复杂度O(n).
6.1 先序遍历
(1)递归实现
按照定义，递归实现很简单。但是在运行栈中，由于每个递归实例需要占据固定的空间，递归实现的效率其实并不高。
(2)迭代实现1
因为stack的LIFO性质，注意节点入栈的顺序：先右后左
(3)迭代实现2
虽然迭代实现1非常简单易懂，但是不利于推广到中序以及后序遍历中，因此需要一个更加能够抓住遍历本质的算法。
通过对遍历过程的观察可知，遍历具有这样一个特点：先沿着左侧链(left-branch)不断向下访问，再自下而上地去访问右子树。
因此，实现的思路是：
沿着left-branch自上而下地访问节点，同时将其对应的右孩子压入栈中。
6.2 中序遍历
(1) 递归实现
同理
(2) 迭代实现
观察可知：最先访问的节点是最左的节点，总体而言自下而上地进行访问。因此需要一种LIFO的数据结构-Stack。
因此，实现的思路是：
沿着left-branch找到最左节点并访问，在这个过程中将沿途的节点压入栈中。访问完当前节点后控制权转移到当前节点的右子树。
(3) 效率分析 - 分摊分析(Amortized Analysis)法
乍一看，两个循环，每个循环最坏可以达到O(n)，因此O(n2)。这好比一个正方形，每个循环分别代表一条边，因为每条边的长度O(n)，因此面积O(n2)。
但是仔细分析之后，真正的运行时间好比正方形框中的一条条直线，每条直线的长度对应s.push()的操作次数，因为每个节点最多入栈一次，节点数目为n，因此各条直线的累积和为O(n)。相当与平均下来，每条直线的长度只是O(1)，因此实际面积(即实际时间复杂度)为O(n).
6.3 后序遍历
观察可知：最先访问的节点是最左的叶节点，总体而言自下而上地进行访问。因此需要一种LIFO的数据结构-Stack。
因此，实现的思路是：
沿着left-branch找到最左叶节点并访问，在这个过程中将沿途的节点以及其右子树节点压入栈中。访问完当前节点后控制权转移到当前节点的右子树。
后序遍历应用 - 表达式树
对表达式树的后序遍历可以生成RPN，再根据RPN的算法来计算表达式的值。
6.4 层次遍历
思路：在之前的三种遍历中，都有着一种逆序访问的过程，即后代咸鱼祖先被访问。因此，这三种遍历的实现都借助与Stack这种具有LIFO特性的数据结构。但是在层次遍历中，严格遵循着父辈先与子辈被访问，因此需要一种FIFO的数据结构-Queue。
6.5 重构
思想：通过遍历序列确定root + 左子树节点 + 右子树节点，然后递归地重构出二叉树。
(1) 普适方法
通过先序/后序遍历的序列来确定root，再根据中序遍历序列来确定左、右子树。
注意，只通过先序和后续遍历的序列，是不能够保证重构的，因为：
若只存在左子树或者右子树，是无法确定是左子树还是右子树的。
(2) 特殊情况：真二叉树proper binary tree
由于在真二叉树中，某个节点要么左右子树都没有，要么左右子树都有，因此可以确定出root，左子树以及右子树。
