😄树结构基础概念

为什么要有树结构？

在维护一个动态的数据集合(需要增删查) 的时候，二叉树(树结构的一种) 可以在增删查的时候都做到 O(logn) 的时间复杂度。
而线性的数据结构则做不到，原因如下。

例如下面这些数据，数据是无序的情况下：

采用数组结构：
增加元素：直接在最后添加一个元素即可，复杂度是 O(1) 。
删除元素：如果删除的是第1个元素，则剩余的所有元素都要往前移动，复杂度成了 O(n) 。
查找元素：最差的情况下需要遍历所有元素，复杂度是 O(n) 。

采用链表结构：增加和删除元素都可以做到 O(1) ，查找还是 O(n) 。

数据是有序的情况下：

数组结构：
增加元素也还是 O(1) 。
删除元素也还是 O(n) 。
查找元素的时候，因为是有序的，所以可以采用二分法，复杂度可以达到 O(logn)。

采用用链表结构：增加和删除元素都可以做到 O(1) ，查找还是 O(n) ，因为链表结构无法使用二分法，无法定位中间的元素是第几个元素。

所以使用线性的数据结构无法在增删查的时候都做到 O(logn) 的复杂度，而使用树结构则可以做到。

树的基础概念

树 是n（n>=0）个结点的有限集。n=0时称为空树。

在任意一棵非空树中：

1. 有且仅有一个特定的称为根结点；
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集，其中每一个结点本身又是一棵树，并且称为根的子树。

数结构如下图所示：

例如上图的树结构中：
1 是根结点，1有3棵子树，分别是：2为根节点的树，3为根结点的树，4为根结点的树。
3 有1棵子树 8 ；4有1棵子树 9 。

结点

1. 结点包含一个数据元素和若干个指向子树的分支。
2. 结点拥有的子树数量称为结点的度(Degree)。
3. 度为0的节点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。
4. 除根结点外，分支结点也称为内部结点。

树的度是树内各结点的度的最大值。

例如上图的树结构中：
结点1的度为3 ， 结点2的度为3， 结点3的度为1 ，结点4的度为1，结点5,6,7,8,8,9的度为0；这课数的度为3。
结点5,6,7,8,9是叶子结点，结点1,2,3,4是非终端结点或分支结点。

结点的子树的根称为该结点的孩子(Child) ；该结点称为该孩子双亲(Parent)；同一个双亲结点之间互称兄弟(Sibling)。

例如上图的树结构中：
结点2,3,4是结点1的孩子，结点1是结点2,3,4的双亲 ； 结点2是结点5,6,7的双亲，结点5,6,7是结点2的孩子；
结点2,3,4是兄弟，结点5,6,7是兄弟；结点7和8不是兄弟，因为他们没有共同的双亲。

结点的层次(Level)从根开始定义起，根为第1层。双亲在同一层的结点互为堂兄弟。
结点的深度（Depth）：根结点到当前结点的路径上的所有结点总数。
结点的高度 (Height) ：当前结点到最远叶子结点路径上的结点总数。
树的深度（Depth）：所有结点深度中的最大值。
树的高度 (Height) ：所有结点高度中的最大值。
一般树的高度 = 树的深度

例如上面的树形结构中：

树一共有4层； 结点1在第1层，结点10和11在第4层。

结点6的深度是3，因为经过了3个结点：1,2,6；结点3的深度是2，因为经过了1和3，2个结点；结点10的深度是4；所有结点中，深度最高的是4，所以这棵树的深度是4。

结点2的高度是2，因为到最远结点的距离是2和6，经过2个结点；结点3的高度是3，到最远叶子结点的路径是3,8,10；所有结点中，最高的结点应该是根结点1，到最远叶子的路径是1,3,8,10，高度为4；所以，树的高度也是4。

森林（Forest）

森林是 m ( m >=0 ) 棵互不相交的树的集合。