通用树

简单的回顾一下数据结构的概念：本质上是一种组织数据的方式，目的就是为了更高效的处理数据。

大体上，数据结构可以分为两大类，一类是线性结构，一类是非线形结构。线性结构有数组(静态、动态)、链表(单向链表、单向循环链表、双向链表、双向循环链表)、栈、队列。栈和队列其实就是操作受限的线性表，栈遵从的是LIFO(Last In First Out)，队列遵从的是FIFO(First in First Out)。字符串其实就是内容受限的线性表。那么，非线形数据结构的最主要还有的树、图。所谓线性结构，指的的是数据以一种顺序的形式排列，一个接着一个，这是通俗的说法，但也最能表达概念。而所谓非线形，则意味着数据存在于多个层级中，这是一种层次结构。线形结构只有一个层级，数据按顺序存储，会形成一种特定的排列顺序。而非线形结构则包含多个层级，数据是以层级的形式组织的。

那么，什么是具有层次关系的数据呢？可以举个例子，比如一所大学的员工架，院长，主任，班主任、辅导员等等的，使用字母来表示了，大概的结构如下：

额，图画的不太好，懒得调整了。在图中可以看出，在最顶层有一个数据，第二层有3个，第三层有4个，第四层有5个数据，这些数据以层级的结构组织起来，这些数据具有层级关系。那么树是什么？

树本质上是一种非线形数据结构，用于模拟这种层级结构。树就是用来表示这种层级结构，或者说，树用于表示彼此间存在层级关系的数据项。因此，上图中就是数据结构中树这种数据结构的逻辑表示。

注意，你需要明确讨论树时所处的具体语境，是在图论的语境下，还是在数学形式中，亦或是在计算机编程或数据结构的语境下讨论树。

在图论中，我们认为树是一个连通且无环的无向图。
在数据结构中，我们认为树是具有方向的。如上图，是一颗树，那么你可以从A到B，但是你不能从B到A。所以，树基本上是自上而下生长的。同理，你可以从B到E、F，但是不可以从E、F到B。

有些情况下，树会用方向来表示，有些时候则不用。但即便不使用方向来表示，其中的规则或条件就是，你只能从上往下走，比如A到B，A到C，A到D，但是不能从C回到A。如果你把数据结构中的这棵树和真实的树做比较，那么你会发现真实的树是从地面向空中生长的，它也是有方向的，它有树根、树枝、树叶。在数据结构中的这棵树是从上到下生长的。你可以这么理解，把真实的树倒过来，那么顶端就有了树根，然后也可以说有树枝和树叶。因此，在数据结构中的树，这个顶端结点被称为什么？被称为root。在上述图中也就是A节点。剩下的可以统称为节点。节点是用来存储信息的单元(结点)。所以上述的结点都会存储一些信息。树中的结点内容可以是数字，比如1，2，3，4；也可以是字符；也可以是字符串。但关键在于，结点都承载着某些信息。

如何定义一个树？

结合上述所说的内容，那么如何定义一个树呢？树可以定义为一组元素的集合。不过，在树中不称为元素，而是称为节点(结点)。在数组中称为元素，在链表中称为节点，在树中也是节点。因为节点本身不仅仅包含要存储的信息，也包含下一个节点的地址(或者是与下一个节点的链接信息)。

比如上图中的D节点指向它的后继节点H。因此，树就是通过链接连接在一起，用来模拟层次关系的一组节点，这就是树，一种非线形数据结构。

树的基本术语

树是一种表示层级关系的数据结构，本身具有很多性质和术语，理解主要的术语和术语之间的关系至关重要。

节点(node)：本质上就是用来存储一些信息的单元，且还包含其他节点的链接。在上图中，所有的元素都被称为节点。
根(root)：也称为根节点，它是一棵树中最顶层的元素，也就是没有任何父节点的那个节点。在上图中就是A节点。
父节点(parent node)：前面说到，树是具有方向的，自上而下生长。从A→B，但不可以从B→A。因此A是B、C、D节点的父节点。同理，C也是G的父节点。准确的说，任意节点的直接前驱节点，就称为该节点的父节点。前驱指的是该节点的上一个节点，而直接这个限定词意味着是紧挨着的前一个节点。以G节点为例，它的父节点，也就是它的直接前驱节点，就是C节点，那么C节点就是G节点的父节点。但是节点A的父节点呢？它没有上一个节点，也就是直接前驱节点，它就是第一个节点，因此它是没有父节点的。
子节点(child node)：根据上述父节点的描述，一个节点有直接前驱节点，被称为父节点，那么一个节点也可能有直接后继节点，这个后继节点就是子节点。对于节点A，它的直接后继节点有三个，分别是B、C、D节点，也就是紧挨着的三个节点。它们都是节点A的子节点。对于节点L，它是没有任何直接后继节点的。

通过上述基本术语的描述，一个节点可能具有多种身份，比如C节点，它是A的直接后继节点，是A的子节点，但同时又是节点G的直接前驱节点，是G的父节点，那么节点A可以说是节点G的祖先节点。在定义一个节点表达的含义的时候，要看它相对于哪个节点，或者说在哪种描述场景下。

叶子节点(leaf node)：没有子节点的节点称为叶子节点。比如节点L，它是没有任何直接后继节点的，节点L就是一个叶子节点。在上图中，叶子节点包括：I、J、K、F、L、M节点。叶子节点也可以被称为外部节点。
非叶子节点(non-leaf node)：至少拥有一个子节点的节点称为非叶子节点。它也被称为是内部节点。在上图中被称为非叶子节点的有A、B、C、D、E、G。
路径(path)：从A节点到L节点，需要经过A→C→G→L，那么这就是一条路径。在这条路径中，连接两个节点的线称为边(edge)。准确的说路径就是从一个源节点到目标节点的一系列连续的边。从A到L，需要经过A→C、C→G、G→L这三条边。
祖先(ancestor)：一个节点的祖先，是从根节点到该节点路径上的任何一个前驱节点。举个例子，L的祖先都有哪些？先看A到L的路径是什么，A→C→G→L找到L的前驱节点，这个前驱节点，可以不是紧挨着的前驱节点，只要是在它前面的，都算是前驱节点，那么A、C、G就都是它的前驱节点，它们都是L的祖先。对于B节点的祖先是谁，根节点A到B的路径是A→B，且A是它的前驱节点，那么它的祖先就只有一个节点，那就是A。
后代(descendant)：一个节点的后代，是从该节点到任意一个叶子节点的路径上的任何后继节点。以节点C为例，找出C节点的所有后代，那么先找出C节点到各个叶子节点的路径是什么。一条路径是C→G→L，一条路径是C→G→M，L和M都是叶子节点。所以这是两条路径，那么在这个路径上，C的所有后继节点就是G、L、M，这三个节点都是C的后代。而B的后代有哪些呢？总共有四条路径，分别是B→F，B→E→I，B→E→J，B→E→K，那么F、E、I、J、K都是B的后代。

那么G节点与H节点是否有共同祖先呢？分别找到G和H的祖先，有相同的节点那就是共同祖先，G和H节点的共同祖先是节点A。那么C节点和D节点是否有共同的后代呢？找到这两个节点的所有后代，发现并没有共同后代。

子树(subtree)：假设上图中的树称为T，那么任意树T的子树，可以定义为包含树T的某个节点，以及该节点的所有后代。比如上图中，B节点以及它的所有后代就是一颗子树，这个子树就是包含了树T的某个节点，也就是B节点，以及它的所有后代。C、D是某个节点加上它们的后代也可以分别称为一颗子树。甚至在B节点以及它的所有后代组成的子树内部，也包含两个子树，一个是以E节点以及它的所有后代组成的子树；另外一个是F节点组成的子树。一颗子树至少要有一个节点。
兄弟节点(sibling)：同一个父节点的所有子节点，它们互为兄弟节点。比如A是B、C、D节点的父节点(直接前驱)，那么B、C、D就互为兄弟节点。但是F和G不能是兄弟节点，因为它们的父节点不同，但是它们的父节点互为兄弟节点，它们可以称为堂兄弟节点。
度(degree)：指的是该节点拥有的子节点个数。比如节点A的度就是3，它有三个子节点。所有叶子节点的度都是0，因为它们没有叶子节点。
- 节点的度：该节点拥有的子节点的个数
- 树的度：树中的所有节点的度的最大值。在上图中，树的度就是3。节点A与节点E的子节点都是3，其他节点的子节点个数没有超过3的了。
节点深度(depth)：从根节点到该节点的路径长度。那么如何确定路径的长度呢？首先明白路径是什么？它是一系列连续的边，那么路径的长度呢？就是这条路径上的边的数量。因此，通俗的说节点深度：就是从根节点到该节点所经过的边的个数。那么节点F的深度是多少？先看根节点到节点F的路径，A→B→F，有两条边分别是A→B、B→F，那么路径长度就是2，节点F的深度就是2。根节点的深度为0
- 树的深度：树中所有节点深度的最大值。那其实就是最远的叶子节点的深度。
节点高度(height)：从该节点到其所有叶子节点的最大路径长度。通俗的来说就是，先找到其所有的叶子节点，计算出从该节点到其叶子节点的边数，取它们的最大值。比如上图中的节点B，它有4个叶子节点，其中到F节点的边数是1，到I、J、K节点的边数是2，2 > 1那么节点B的高度就是2。叶子节点的高度为0

现在来看，一个节点的高度和深度可能相同，也可能不同。比如节点B的高度是2，深度是1，是不同的；但是节点D的高度为1，深度也是1，高度与深度相同。

树的高度(height)：树的高度就是根节点的高度。也就是说求出从根节点到其所有的叶子节点的边数，从而进行对比得出最大值，就是到最远叶子节点的深度。
节点层级(level)：一个节点的层级，同样指的是从根节点到该节点的距离(也就是从根节点到该节点的路径上所经过的边数)。比如节点L的层级，A→C→G→L，经过的边数是3，因此节点L的层级就是3。根节点的层级是0。
- 节点层级的计算方式与节点深度的计算方式是一样的，因此，一个节点的深度总是等于该节点的层级。但是一个节点的层级不一定等于该节点的高度。
- 树的层级其实可以看作是树的高度，因为树的高度就是根节点的高度，根节点的高度就是到其所有叶子节点的边数的最大值，这个最大值代表的就是这个叶子节点的所在的层级最大，所以树的层级可以看作是树的高度。
- 结合之前树的深度与树的高度、树的层级的概念(从零开始)：树的深度等于树中所有节点深度的最大值；树的高度等于根节点的高度(根节点的高度等于到最远叶子节点的边数，那其实就是该叶子节点的深度，最远叶子节点，它的深度是最大的，因此它又是树的层级)；所以，树的深度等于树的高度，同时树的层级就是树的高度，那所以树的高度等于树的深度等于树的层级(层级从0开始)。而节点的深度等于该节点的层级但是不等于节点的高度。

在很多基本术语的加持下，每个术语之间也存在着很多关系，利用这些关系往往可以很高效的解决问题。其中一个很关键的关系就是：树的边数 = 树中的节点数 - 1。edge = (n - 1)，n表示节点数，若再加一条边，就会成为一个环，比如你在I与J之间加上一条边，那么就会有一个环存在了。而在树结构中，是不能存在环的，它必须是无环的。

给通用树加点限制

那么如何高效的操作这棵树呢？上面的图示表示的也是一棵树的逻辑数据结构，这只是它的逻辑表示。上述讨论的是一般树或者说是通用树，在一般树中一个节点可以有任意多个子节点，也就是说它不限定每个节点有多少分支。在讲述基本术语的时候，更倾向于讲解一般树，也就是上述图中的结构，在一个节点中，有一个分支的，也有两个分支的，也有三个分支的，但其实还可以有100、1000个分支，不做限制。这种不加任何限制的通用树，主要是用来建立树的抽象概念，但是它足够复杂，用于训练关于树的递归思维和算法能力是不适合的，使用具体的数据类型表达一个节点也是很复杂的。因此既然通用树是不加限制的，那么就可以加一些限制，使其成为相对简单，但又可锻炼思维与算法能力的树。它和链表数据结构不同，说链表时，第一个说的是单向链表，单向链表本身就是一个核心的数据结构，不是一个过渡的概念。而通用树只是用来建立基础概念，基础概念适合任何加了限制的树。而在所有加了限制的树结构中，第一个核心重点就是二叉树。

顾名思义，二叉树代表每个节点最多有两个子节点，也就是最多两个分叉。对比通用树的每个节点可以有任意个子节点，也就是任意多个分叉来说，二叉树更简单，结构看起来更完整，不会像通用树那么乱，且递归关系是很清晰的。看以下图示：这是二叉树的逻辑结构

上述图中的数据结构就是一个加了限制的树，一个节点最多只能有两个子节点，也就是两个孩子。可以有0个，也可以有1个，也可以有2个。F画的不太规整，是右节点。

而且，在此规整的结构中，一般将一个节点中的左边的子节点称为左孩子，右边的子节点称为右孩子。这种结构运用上述的基本术语，可以更好的锻炼递归思维与算法能力。二叉树相比较于通用树虽然结构简单，递归性强。但最简单的往往是最难的，因为它可以引申更多的变种，所谓的变种就是为了能够适应更多场合，在二叉树的基本上又加了很多限制，从而引出二叉搜索树、堆等大量重要结构，简单的描述一下吧。

二叉树在通用树的基础上加了一个限制：一个节点最多只能有两个节点，通用树的一个特化版本。
二叉搜索树Binary Search Tree)：在二叉树的基础上加上搜索顺序限制。首先是一颗二叉树，随后在二叉树的基础上加上两个条件，假设节点中存储的是整数，那么对于任意一个节点
- 左子树中的所有节点值 < 当前节点值
- 右子树中的所有节点值 > 当前节点值
BST的核心是左小右大，在查找的过程中，直接对比当前节点值的数据，若小于则直接可忽略右子树，若大于则可直接忽略左子树。通过搜索顺序限制换来了较快的查找、插入、删除能力。
AVL树、红黑树：BST如果不平衡的话，可能会退化为链表，这时候查找复杂度可能从理想的O(logn)退化到O(n)。因此就需要在BST的基础上加上平衡限制
- AVL树要求更严格的高度平衡，也就是任意节点左右子树高度差不能超过1。
- 红黑树相对宽松，但加了颜色规则，这一点后面详细研究
加的不同的限制，只是为了防止BST退化成链表，保证操作复杂符维持在O(logn)。
二叉堆(binary heap)：它与BST的限制完全不同，二叉堆的限制包括两个：
- 形状限制：必须是完全二叉树(除了最后一层，其他层都是满的，且最后一层的节点必须是从左到右连续排列的。)
- 顺序限制：父节点和孩子节点之间满足堆序关系
分为最大堆和最小堆：
- 最大堆：每个父节点必须大于等于它的孩子节点
- 最小堆：每个父节点必须小于等于它的孩子节点
二叉堆的目的不是快速查找任意元素，而是快速取得最大值或最小值，所以堆经常用于优先队列、堆排序、Top K问题、调度系统等等

BST和二叉堆的限制完全不同：

BST的限制限制左子树 < 根 < 右子树，关心的全局搜索顺序。
二叉堆的限制是：基于完全二叉树的基础上，要求父节点 ≤ 子节点或者父节点 ≥ 子节点

一棵树可能是最大堆，但它不一定是BST。

回到主题，先从最简单的二叉树开始学习这种挺具有魅力的数据结构，上面的内容目前也是简单了解，后面会深入了解。

节点类型与物理结构

节点类型

通用树之所以复杂是因为无法使用一个确定的的类型去描述一个节点，因为通用树中一个节点可能有三个子节点，也可能没有子节点，也可能有四个、五个子节点等等。更不用说定义整个插入树的抽象数据类型了。而二叉树不同，已经很明确的说明一个节点最多只能有两个子节点，可以有0个子节点，也可以有1个子节点，但是不能超过2个。这样一来，可使用一个明确的数据类型来表达一个节点：

1
2
3
4
5
6
7
8
9
class node{
  node(int data = 0)
    :data_ {data}
    ,left{nullptr}
    ,right{nullptr}{}
  int data_;
  node* left_;
  node* right_;
};

在上述类型中，定义一个节点类node，类中有三个数据成员，其中data用于存储节点数据，这里假设是整数。其他两个数据成员分别是node*类型的指针，分别指向自己的左右子树，当一个节点有左子树而无右子树或者都没有的时候，可将其值设为nullptr。这样就可以很好的表达一个节点的类型了。

物理结构

通过上述的节点类型了解到，左右指针存储的是一个节点的地址，那么就是按照链表这种物理结构的方式去存储一个节点，可将上述二叉树逻辑结构中的节点换成另外一种形式。

虽然使用的还是逻辑结构，但是每个节点的地址是不同的，且是不连续的，这是链表物理结构的特征。可以看到，一个节点最多指向两个子节点，且无子节点的节点的左或者右指针的值都是nullptr，叶子节点是没有左右子节点的，因此都是nullptr。

应用

在之前的讨论中，树是用来存储层次化数据的，那么当你需要存储层次化数据的时候，就需要用到它。

它会被应用于实现文件系统，在文件系统中，存储的数据也是类似上述图中的这种结构，一个节点是一个目录，目录下还是一个子目录，或者都是文件等等，这是一种层级形式，树基本上就是用来实现整个模型，也就是文件系统。
在路由协议中，也会用到树状数据结构。
还有一个应用就是它可以组织数据以支持快速搜索、插入和删除，比如二叉搜索树、二叉堆等等