树

2020/2/7 二月的南京还是有点冷，没开空调，写笔记，手已冻僵。

1. 树的定义¶

树是一种非线性的数据结构，它是由n(n>=1)个有限节点组成的一种具有层次关系的集合，之所以称之为树，是因为它长得像一颗倒过来的树。

举个例子，每个人都有家族树，家族树一般长这样：

家族树的样子看起来像一颗正常的树，而数据结构中的树则像是一颗倒过来的树：

可以看出，一棵树有多个节点，上图中带〇的字母就是一个节点。每个节点可能有0个或更多子节点，每个节点至多有一个父节点，没有父节点的那个称之为根节点。除根节点外，每个节点又可以分为多个不相交的子树。

树中每个元素都叫节点

树顶端的节点称之为根节点，也叫树根

除根节点之外，其他节点可以分为多个树的集合，叫做子树，在上图中，K这个节点可以称之为一颗子树，而H、K、L三个节点组合起来也可以叫做一颗子树

一个节点直接含有的子树的个数，称之为节点的度。比如上图中B节点的度为3，C节点的度是2，I、J、K、L节点的度是0

度为0的节点叫做叶子节点，也叫叶节点、终端节点，其实就是没有子节点的节点，或者说没有子树的节点

父节点就是一个节点上头的那个节点，如果一个节点包含若干子节点，那么这个节点就是这些子节点的父节点，也叫双亲节点

拥有相同父节点的节点互称为兄弟节点

一棵树中最大节点的度称之为树的度，即树中哪个节点的子节点最多，那么这个节点的度也就是树的度

从根这一层开始，根算1层，根的子节点算2层，一直到最下面一层

树的深度是从根节点开始、自顶向下逐层累加（根节点的高度是1）助记：深度从上到下
树的高度是从叶节点开始、自底向上逐层累加（叶节点的高度是1）助记：高度由下向上
虽然树的高度和深度一样，但是具体到某个节点上，其高度和深度通常是不一样的。

堂兄弟节点是同一层，父节点不同，或者说双亲节点在同一层的节点称之为堂兄弟节点

从根节点到某一节点一路顺下来的除了该节点的所有节点都是该节点的祖先节点

以某节点为根的子树中，任何一个节点都是其子孙，也就是说这个节点下面与这个节点有关的节点都是这个节点的子孙

由m棵不相交的树组成的集合，叫做森林

树的种类有很多，我们接触到的树有二叉树、平衡二叉树、二叉查找树、B树、B+树、哈夫曼树、B*树、红黑树和trie树等。