08.树:1_介绍

1.树相关的定义

树介绍

树(Tree)是n(n>=0)个结点的有限集。
子树(SubTree)是根又可以分为互不相交的有限集，每个集合本身又是一棵树。
结点子树的根称为： 结点的孩子(Child)
该结点称为： 孩子的双亲(Parent)
同一双亲的孩子之间互称为 兄弟(Sibling)
结点的祖先是从根到该结点所经分支上的所有结点。


度

结点的度(Degree)： 表示结点拥有的子树。
树的度：取树内各结点的度的最大值。
度=0的结点称为叶结点(Leaf)或者终端结点。
度!=0的结点称为分支结点或者非终端结点，除根结点外，分支结点也称为内部结点.


结点的分层

第一层：根结点
第二层：根结点的孩子(同一层的结点互为 堂兄弟)
。。。
树中结点的最大层次称为树的深度(Depth)或高度。


如果将树中结点的各子树看成从左到右是有次序的，不能互换，则称该树为有序树，否则称为无序树。
森林(Forest)是m(m>=0)棵互不相交的树的集合。
对树中的每个结点而言，其子树的集合即为森林。

2.树的存储结构

一个存储结构设计的是否合理，取决于该存储结构的运算
1.是否适合
2.是否方便
3.时间复杂度好不好。

双亲表示法
我们可以根据结点，找到双亲结点，时间复杂度：O(1)
索引到parent的值为-1时，表示找到了树结点的根。




结构定义