2020-03-12

Essay

14 分钟读完 (大约 2065 个字)

树

在之前的章节当中，我们花费了许多篇幅介绍了单链表，循环链表，双向链表与双向循环链表，栈和队列等相关知识，但是如果细心观察可以发现，我们之前介绍的种种，它们其实都是一种『一对一』的线性结构，无论是线性表也好，或者说是栈和队列，都是一样的，所以今天我们就来看一种『一对多』的数据结构，那就是『树结构』

树的定义

树（Tree）是 n（n >= 0）个结点的有限集，当 n = 0 时成为空树，在任意一棵非空树中，有以下特点

有且仅有一个特定的称为根（Root）的结点
当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集 T1、T2、... Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

如下图所示

但是有两个需要注意的地方，即

当 n > 0 时，根结点是唯一的，不可能存在多个根结点
当 m > 0 时，子树的个数是没有限制的，但它们互相是一定不会相交的

比如下面两个图片所表示的『均是错误』的

结点分类

在之前树的定义当中，图中的每一个圈圈我们就称为树的一个结点，结点拥有的子树数称为结点的度（Degree），树的度取树内各结点的度的最大值

度为 0 的结点称为叶结点（Leaf）或终端结点
度不为 0 的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点

可以用下图来进行表示

结点间的关系

结点间的关系简单来说，结点的子树的根称为结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent），同一双亲的孩子之间互称为兄弟（Sibling），而结点的祖先则是从根到该结点所经分支上的所有结点，结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层，其双亲在同一层的结点互为堂兄弟，树中结点的最大层次称为树的深度（Depth）或高度，如下图所示

树的存储结构

之前我们介绍了树的定义和一些基本概念，下面我们就来看看如何在内存中安排树这种结构的存放，说到存储结构，就会想到我们之前介绍过的顺序存储和链式存储两种基本结构，对于线性表来说，很直观就可以理解，但是对于树这种一对多的结构，我们应该怎么办呢？

如果要存储树，简单的顺序存储结构和链式存储结构是无法实现的，但是如果充分利用它们各自的特点，完全可以间接地来实现，这里我们主要介绍三种不同的表示法，『双亲表示法』、『孩子表示法』和『孩子兄弟表示法』，下面我们就一个一个来看

双亲表示法

双亲表示法，言外之意就是以双亲作为索引的关键词的一种存储方式，我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点在数组中位置的元素，也就是说，每个结点除了知道自己是谁之外，还知道它的双亲结点在哪里，可以作如下定义

// 树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode {
  ElemType data;  // 结点数据
  int parent;     // 双亲位置
} PTNode;

typedef struct {
  PTNode nodes[MAX_TREE_SIZE];
  int r;          // 根的位置
  int n;          // 结点数目
} PTree;

如果用图片来表示的话，如下

如上图这样的存储结构，我们可以根据某结点的 parent 指针找到它的双亲结点，所用的时间复杂度是 O(1)，索引到 parent 的值为 -1 时，表示找到了树结点的根，但是也是存在缺点的，比如我们如果想要知道某结点的孩子是什么？那么则需要遍历整个树结构，所以基于这个问题，我们可以考虑稍微来改变一下它的结构，如下图

同理，比如我们需要了解它的兄弟之间的关系，可以调整如下图

由上我们可以发现，存储结构的设计是一个非常灵活的过程，只要你愿意，你可以设计出任何你想要的结构，一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等等，所以并不需要拘泥于所学过的有限的数据类型，而是以当前的使用场景来进行考虑

孩子表示法

看完了双亲表示法，我们再来看看孩子表示法，这次我们换个角度来考虑，由于树中每个结点可能有多棵子树，所以可以考虑用多重链表来实现，这里我们还是以开头例子当中的树为例，同样的，孩子表示法也有多种可以实现的方式，我们一个一个来看，首先来看方案一，也是最简单粗暴的方法，即『根据树的度，声明足够空间存放子树指针的结点』即可，如下图所示（在这里我们使用 ^ 来代表空指针，也就是 null）

当然，缺点也是显而易见的，那就是造成了空间的浪费，所以针对于这个缺点，我们就有了方案二，如下图

我们引入了一个新的变量用来表示『每个结点的度的值』，这样一来我们就克服了空间浪费这个缺点，但是同时可以发现，因为每个结点的度的值不同，初始化和维护起来也是存在一定问题的，所以就有了方案三

我们通过将数组和链表的一定搭配结合来进行实现，但是如果只找到孩子找不到双亲貌似还不够完善，那么我们干脆就将它们一起合并起来，也就有了我们的『双亲孩子表示法』，如下图

下面我们就来看看『双亲孩子表示法』的定义代码

#define MAX_TREE_SIZE 100

typedef char ElemType;

// 孩子结点
typedef struct CTNode {
  int child;                    // 孩子结点的下标
  struct CTNode *next;          // 指向下一个孩子结点的指针
} * ChildPtr;

// 表头结构
typedef struct {
  ElemType data;               // 存放在树中的结点的数据
  int parent;                  // 存放双亲的下标
  ChildPtr firstchild;         // 指向第一个孩子的指针
} CTBox;

// 树结构
typedef struct {
  CTBox nodes[MAX_TREE_SIZE];  // 结点数组
  int r, n;
}

# Essay

树