本篇笔记主要与数据结构（树）相关。笔记中会尽量避免使用过于严格且枯燥的数学语言，以直观理解为最重要的目的。
基本概念
一般地，树分为自由树与有根树。自由树是一个连通无环无向图，而有根树不仅是一个连通无环无向图，但其中存在一个顶点与其他顶点的不同，它被称为树的根（root）。
在下面的笔记中，没有明确说明的情况下，我们都默认树是有根树。
有根树数据结构
在一棵有根树中，顶点也被称为节点（node）。树会有枝芽，一个节点 x 可能会是另一个节点 y 的子节点（children），这种情况下我们也说节点 y 是节点 x 的父节点（parent)。在树中，一个节点可能有若干个子节点，但它只能有一个父节点。两个共享同一个父节点的节点被称为兄弟节点（sibling）。
根据这些概念，我们可以很轻松地写出数据结构 TreeNode，这里我们直接使用 struct 来写。
此时，我们可以用一个 TreeNode *head 来表示一个指向有根树根节点的指针。由于连通性，根节点就可以直接指代该树了。
二叉树数据结构
特殊地，二叉树（Binary Tree）是定义在有限节点集上的结构，它或者不包含任何节点，或者包含三个不相交的节点集合：一个根节点，一个左子树（同样也是二叉树），一个右子树（同样也是二叉树）。不包含节点的二叉树就是一棵空树。如果一个节点没有左子树也没有右子树（或者说左右子树都是空树），则该节点称为叶节点（leaf）。
我们可以简单地修改 TreeNode 数据结构，就可以将其仅用作二叉树节点。
特殊地，完全二叉树（Complete Binary Tree）指的是每一层的节点都尽可能被填满，除了最后一层（叶）节点外所有节点数都达到了最大值，最后一层的节点如果没有满，那么这些节点从左到右连续排列，右边可能有空缺，中间不会有空缺的树。
完全二叉树具有下面这些性质：
对于一个深度为 d 的完全二叉树，其最大节点数位 2^d - 1。
在所有节点数为 n 的树中，完全二叉树是高度最小的（树的高度指的是从根到任意叶节点中最长的路径的长度）。
满二叉树（Full Binary Tree）指的是每个节点都有 0 个或 2 个子节点，所有子节点在同一层。满二叉树是完全二叉树的另一个情况。
基本算法
有根树遍历
在关于有根树的所有算法中，遍历（traverse）是一个相对简单、基础的算法。利用树的性质，我们往往可以利用递归或者栈与队列写出很直观的算法。
以二叉树为例，我们分别介绍前序（preorder）、层序（level order）、中序（in order）、后序（post order）四种遍历顺序。假设我们要将遍历的结果存入一个 vector 并输出。
前序遍历
前序遍历的顺序是根 → 左 → 右。因此非常简单。
注：recursion的过程中我们尽量按照引用传递已经写好的 result 数组，避免使用 vector::insert(), 可能会导致额外的拷贝和效率问题。
中序遍历
中序遍历的顺序是左 → 根 → 右。与上面使用递归的方法几乎一样。
后序遍历
后序遍历的顺序是左 → 右 → 根。与上面使用递归的方法几乎一样。
层序遍历
层序遍历要求一层一层访问，并且每层从左到右。在这里，我们不再去使用 recursion 来进行遍历，而是使用队列。队列符合先进先出，因此每层我们让左树先进队列，右树后进队列，然后依序 pop 队列中的节点进行遍历。
分支无限制的有根树
如果每个节点子节点的个数是有限的常数，我们可以用最开始的方法来记录一棵树。我们还有一种巧妙的方法可以用来表示孩子数任意的树，只需要 O(n) 的存储空间，这种方法叫做左子右兄弟表示法（left child, right sibling）。
Comments