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时称为空树。
在任意一棵非空树中：
- 有且仅有一个特定的称为根的结点；
- 当n>1时，其余节点可分为m(m>0)个互不相交的有限集，其中每一个几何本身又是一棵树，并且称为根的子树。
结点
- 结点包含一个数据元素和若干个指向子树的分支。
- 结点拥有的子树数量称为结点的度(Degree)。
- 度为0的节点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。
- 除根结点外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值。
结点的子树的根称为该结点的孩子(Child) ；
该结点称为该孩子双亲(Parent)；
同一个双亲结点之间互称兄弟(Sibling)。
结点的层次(Level)从根开始定义起，根为第一层。
双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度(Depth)或高度。
森林（Forest）是m（m》=0）棵互不相交的树的集合。
2 存储结构
双亲表示法：每个结点设置一个指向该结点双亲的指针域。
孩子表示法：
将结点连接起来存在1个链表。
链表的每个结点，都有一个存储自己子结点的链表。
网友评论