树结构基础概念

1 定义

为什么要有树结构？

在维护一个动态的数据集合(需要增删查)的时候，二叉树(树结构的一种)可以在增删查的时候时间复杂度都是O(logn)。

而线性的数据结构则做不到，原因如下：

例如下面这些数据：

无序数据结构.png

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

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

如果采用的是有序的数据结构

有序数据结构.png

如果使用的是数组结构：
增加元素也还是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. 结点包含一个数据元素和若干个指向子树的分支。
2. 结点拥有的子树数量称为结点的度(Degree)。
3. 度为0的节点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。
4. 除根结点外，分支结点也称为内部结点。

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

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

结点的层次(Level)从根开始定义起，根为第一层。
双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度(Depth)或高度。

森林（Forest）是m（m》=0）棵互不相交的树的集合。

2 存储结构

双亲表示法：每个结点设置一个指向该结点双亲的指针域。
孩子表示法：
将结点连接起来存在1个链表。
链表的每个结点，都有一个存储自己子结点的链表。