本篇笔记主要与数据结构(树)相关。笔记中会尽量避免使用过于严格且枯燥的数学语言,以直观理解为最重要的目的。
基本概念
一般地,树分为自由树与有根树。自由树是一个连通无环无向图,而有根树不仅是一个连通无环无向图,但其中存在一个顶点与其他顶点的不同,它被称为树的根(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)。
Comentários