Data Structure 03 - Tree
# 前置知识
在阅读本文档前,请确保你已经掌握线性表的基础知识,详见 Data Structure 知识板块中的 01 - Linear List 文档。
# 基本概念
树是最基本的一类数据结构,和线性表一样,它也是一类数据结构的统称。不同的是,树是一类非线性的数据结构,它通常用来表达类似于“祖先-后代”、“上级-下属”、“整体-部分”这样的层次关系,例如一个家族的族谱,一本书的目录等,都是树状的层次关系。
树是非常重要的数据结构概念,建议将其定义彻底吃透,不要停留在一知半解的程度。
首先声明,在图论中有无根树的概念,但我们在本文中只讨论有根树。
树 (Tree) 指的是由有限个 节点 (node) 组成的树状结构。
下图中给出了一棵树的逻辑上的示例,以便于理解。
下面我们尽可能清晰地给出树的基本定义,配合图中的示例,帮助读者逐渐了解树这一新鲜事物,其后再给出严格规范的定义。这里的定义非常多,但都很容易理解。
一棵树上包含 个节点,常用 等来表示一个节点。当 时,称该树为空树,否则为非空树。如上图中的树有 。
每一棵非空树都有一个 根节点 (root) ,常用 来表示一棵树,其中 为 的根节点。如节点 即为根节点,记为 。
树上的每个节点都有一个 深度 (depth) ,记节点 的深度为 。通常我们定义根节点的深度为 或 ,也可以是其他值,其下每一层的节点都比其上层节点的深度更大。定义节点 的深度为 到根节点的距离再加上根节点的深度,例如如果我们规定根节点的深度为 ,那么 。
一个节点的 邻接节点 (adjacent node) 包括所有与该节点直接相连的节点,例如节点 的邻接节点有 ,节点 的邻接节点有 ,节点 的邻接节点只有 。
一个节点的邻接节点中,比该节点深度大的为该节点的 子节点 (child) ,比该节点深度小的为该节点的 父节点 (parent, or father) 。
树上的每个节点都有若干个子节点,也可能没有。例如节点 有两个子节点 和 ,节点 没有子节点。
树上的每个节点都有且仅有一个父节点,除了根节点,只有根节点是没有父节点的。记节点 的父节点为 。例如 。
定义一个节点的子孙节点为该节点的子节点的递归定义,意思是 的子节点的子节点的……的子节点是 的子孙节点。例如 的子孙节点包括树上除了 以外的所有节点,节点 的子孙节点包括 ,节点 没有子孙节点,节点 的子孙节点包括 。
如果我们把树上的任意一个非根节点 ,和它的所有子孙节点,视为一棵树,那么这棵树称为原树的一棵子树,称 为该子树的根节点。例如 是 的一棵子树, 是 的一棵子树,但是 同时也是 的一棵子树。另外,虽然节点 没有子孙节点,但是 也是 或是 的一棵子树。
下图中给出了常见的一种表示子树的图样。
下面我们给出严格规范的树的递归定义。
对于一棵非空树 ,设 的子节点为 ,该树的递归定义为节点 和以 的每个子节点为根节点的子树 组成的节点集合。
注意,在图论中,树也被定义为一种具有特殊性质的图,并且前文中也提到过,图论中存在无根树这一简单而却非常重要的定义。
此处我们不会介绍图论知识,仅介绍树的一些独立于图论之外的内容,关于图论的内容详见 Graph Theory 知识板块。
# 概念
节点,子节点,父节点,子孙节点,根节点,子树,树的概念均已在上文中用非常详细的语言介绍了,故此处不予赘述。唯一要提醒的是,注意区分子节点和子孙节点的概念。
下面给出一些树上节点的其他重要概念。
节点的度:设 是 上的一个节点,则 的 度 (degree) 为的子节点个数,记为 。这里的度和图论中的度的概念是不同的,敬请注意。
叶子节点:设 是 上的一个节点,若 ,则称 为 的一个 叶子节点 (leaf) 。
兄弟节点:设 是 上的节点,若 ,则称 互为 兄弟节点 (siblings) 。
祖先节点:父节点的递归定义,即 等都是节点 的 祖先节点 (ancestor) 。
下面给出一些树的其他重要概念。
树的度:设 是一棵树,则 的度为 上所有节点的度的最大值,即 。
树的高度:设 是一棵树,则 的 高度 (height) 为 上所有节点的深度的最大值,即 ,亦称为树的深度。
层:设 是一棵树,称 上所有满足 的节点组成了 的第 层。
有序树/无序树:设 是一棵树, 是 的任意一个节点,如果 的子节点 的顺序是有意义的,则称 是一棵有序树,否则称 是一棵无序树。
例如下图中的两棵树,如果采用有序树的定义,则它们是不同的,如果采用无序树的定义,则它们是相同的。
通常来说,除非特别指出或定义,否则我们均用“树”一词来表示无序树。
树的退化:设 是一棵非空树,若 的每个非叶子节点都只有 个子节点,则称 是一棵退化的树,此时 的结构等同于链表。这个定义并不那么严格,当 的结构很接近链表时,例如几十个节点里只有四五个节点的度数大于 ,那么我们有时也称 是退化的。特殊考虑树的退化的理由是因为这往往会影响我们程序的最坏时间复杂度。
森林: 森林 (forest) 指的是若干棵互不相连的树所组成的集合。如果删掉一棵树上的任意一个非叶子节点,则该树会变成一棵森林。
# 存储及表示方式
在实现和使用图论之外的有根树时,我们通常使用类似链表的存储方式,至于是动态链还是静态链都无所谓,我们只关心它的逻辑形式。为了与大多数入门教材相符合,我们先使用动态链来实现,后面再附上静态链实现的代码。至于图论中的树,其存储方式与一般的图完全等同。
# 子节点表示法
我们首先介绍最常见的子节点表示法。
有根树的节点定义和链表的节点定义非常相似,唯一的区别是,链表只有一个 指针,或是双向链表还有一个 指针,而树的节点可能有很多个指针。
根据树的定义,树上的每个节点都可能有若干个子节点,我们既可以用顺序表、也可以用链表来记录指向这些节点的指针。两种方法的优缺点和适用场合你应该已经掌握了,为了方便起见,我们假定已知树上节点的最大度数为 ,并使用顺序表来存储。
类似于链表的头指针 ,树也需要一个根节点指针,记为 。
// 定义:子节点表示法
const int MAXDEG = ...;
class Node {
public:
int value;
Node * children[MAXDEG];
int chcnt;
public:
Node(int v) : value(v), chcnt(0) {
for (int i = 0; i < MAXDEG; i ++) {
children[i] = nullptr;
}
}
};
Node * root = nullptr;
类似于带头节点的链表,你也可以使用一个不存储有效数据的节点,并将根节点设为它的子节点。这种处理方式和带头节点的链表几乎一样,此处就不再赘述了,我们不进行这一处理。
# 父节点表示法
如果使用子节点表示法,那么显然,我们从某个节点出发很容易就可以访问它的所有子孙节点,但却很难访问它的祖先节点。而有时我们可能更希望能够快速访问祖先节点,因此就有了父节点表示法的存在。
根据树的定义,树上除了根节点以外的每个节点都有且仅有一个父节点,因此我们可以为每个节点维护一个指向父节点的指针。
// 定义:父节点表示法
class Node {
public:
int value;
Node * parent;
public:
Node() : value(0), parent(nullptr) {}
Node(int v) : value(v), parent(nullptr) {}
};
Node * root = nullptr;
但这样又带来一个问题,我们现在很难访问一个节点的子孙节点了。因此子节点表示法和父节点表示法的优缺点都很突出。
事实上,这并不是什么问题,在实际应用中,我们经常既使用子节点指针也使用父节点指针。
从实际情况上讲,我们常见到子节点表示法和父子节点表示法,很少见到单独的父节点表示法,因为在多数情况下我们会从根节点出发对树进行遍历,亦或是从根节点递归到底再向上回溯,极少时候必须一开始就从叶子节点出发向上进行遍历。
如果我们关注空间的使用情况,那么通常会使用子节点表示法,否则为了方便我们会使用父子节点表示法。
鉴于父子节点表示法的物理结构很显然,就不再给出图示了。
# 左儿子右兄弟表示法
接下来我们介绍另外一种重要的表示法,左儿子右兄弟表示法。这是一种重要的思想,但是其实我们在实际应用中较少采用,你只会在少数必要的场合见到这种表示法。例如有时我们会用这种表示法作为二项堆和斐波那契堆的物理实现,但这也不是必须的。
顾名思义,左儿子右兄弟表示法为每个节点维护两个指针 和 ,其中 指针指向它在存储结构上的最左的子节点, 指针指向它在存储结构上的右侧最近的兄弟节点。显然,这种表示法更适合在有序树上使用,因为无序树缺乏左右的概念,可能会引起混乱。
// 定义:左儿子右兄弟表示法
class Node {
public:
int value;
Node * child;
Node * next;
public:
Node() : value(0), child(nullptr), next(nullptr) {}
Node(int v) : value(v), child(nullptr), next(nullptr) {}
};
Node * root = nullptr;
这种表示法的物理结构如下图所示,这正是本文最开始的那棵树。我们用红线表示 指针,用蓝线表示 指针。
# 应用
通常,我们很少使用独立于图论之外的一般树。在独立于图论之外的情况下,我们大量使用二叉树及其多种多样的衍生应用,而这种不加任何限制的一般树则更常用于图论体系之内。
换句话说,二叉树才是我们的重点,本文只是帮助你对“树”这一新生事物构建一个最基本的了解而已。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01