引入

之前我们讲的都是线性表，它们有可以是顺序存储结构或者链式存储结构的数组、链表、栈、队列。我们之前讨论的线性结构都是一对一的。那什么不是一对一呢？例如妈妈的两个孩子，一个妈妈对应了两个孩子，这种一对多的数据结构，我们称之为树。当然了，以后还会有多对多的概念，今天我们先了解一下树的概念。

树的定义

树（Tree）是 n ($n\geq0$) 个结点的有限集。n=0 时，我们称之为空树。
在任意一棵非空树中：

有且仅有一个特定的称之为根（Root）的结点。
当 n>1 时，其余结点可分为 m($m\geq0$)个互补相交的有限集
有限集 T1、T2、….、Tm，其中每一个集合本身又是一棵树
我们称由这些有限集合构成的树，为根的子树（SubTree）。

上面的图中

根：A 结点是这棵树的根
结点：每一个圈都是一个结点
子树：B、C、D、E、F、G、H都是子树

注意：
n>0 时，根节点是唯一的。绝不可能存在多个根节点。
m>0 时，子树个数没有限制，但是它们一定不相交。

注意：B、C 是 A 这个根的子树，BC 是不能像上面这样相连的。

注意：同样的，G 是 C 的子树，BG 是不能像上面这样相连的。也就是不能两个双亲结点指向一个子结点。

结点分类

我们称上面的每一个圈，都是数的一个结点。

结点拥有子树的数，称之为结点的度（Degree）
树的度的值，为当前书内各结点度的最大值。

看上面这个图

度为 0 的结点称为叶结点（leaf）或终端结点。
度不为 0 的结点称为分支结点或非终端结点。
根结点除外，分支结点也称为内部结点。
所有结点中度最大的就是 B，度为3，所以就是整个树的度。

结点间的关系

看上面这张图

结点的子树的根，我们称之为该结点的孩子（Child）
例如 B 是一个棵子树，B 作为这棵子树的根，B 就是 A 的孩子。
该结点称为孩子的双亲（Parent）
例如 B 是 A 的孩子，A 就是 B 的双亲
同一双亲的孩子之间，互称为兄弟（Sibling）
例如 A 结点下有有两个孩子B、C ， B 和 C 之间互称兄弟，B 是 C 的兄弟。
结点的祖先是根到该结点的所有结点
例如 D 的祖先就是 B A

结点的层次

结点的层次分为

根节点为第一层
例如，A 在第一层
根的孩子为第二层
例如 B、C 在第二层
双亲在同一层的结点互为堂兄弟
B C 都在第二层，E 是 B 的孩子，H 是 C 的孩子，E H互为堂兄弟
树中结点的最大层次为树的深度（Depth）或高度。
例如上面图中，树的 Depth 为 3。

其它树

有序树和无序树：

如果一棵树，树中的各个结点的子树
是从左到右有顺序的
不能互换的
我们就称这种树为有序树。
否则就是无序树。

森林（Forest）：

森林（Forest）是 m(m>=0)棵互不相交的树的集合
对于树中每个结点而言，其子树的集合，就是森林。

我们看上面的图

这棵树的 B 和 C 都是这棵树的子树
由 B D E F 组成的可以看做森林
由 C G H 组成的，也可以看做森林

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。