青海网站设计企业网站快速收录
目录
树的结构以及示意图
树的概念编辑
树的结构与递归的关系编辑
树的结构以及示意图
树是一种非线性的数据结构，它是由 n(n>=0) 个有限节点组成一个具有层次关系的集合
把这种结构叫做树是因为它看起来像一棵倒挂的树
特点：
有一个特殊的节点，称为根节点，根节点没有前驱节点
除根节点外，其余节点被分为 M(M>0) 个互不相交的集合
示意图：
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
树的概念
节点的度：
一个节点含有的子树的个数称为该节点的度
如上图：A 节点的度为6，因为 A 节点有 6 个子节点
叶节点或终端节点：
度为 0 的节点为叶节点 ；如上图：B、H、I、P、Q……等节点都为叶节点
非终端节点或分支节点：
度不为 0 的节点 ；如上图：D、E、F、G、A 节点为分支节点
双亲节点或父节点：
若一个节点含有子节点，则这个节点称为其子节点的父节点
如上图：A 节点是 B 节点的父节点，A 节点同时也是 C 节点的父节点……
孩子节点或子节点：
一个节点含有的子树的根节点称为该节点的子节点
如上图：B 节点是 A 节点的孩子节点
兄弟节点：
具有相同父节点的节点互称为兄弟节点 ；如上图：B 和 C 是兄弟节点
树的度：
一棵树中，最大的节点的度就是整个数的度
如上图：A 节点的度为 6 ，那么树的度也为 6
节点层次：
从根开始定义起，根为第 1 层，根的子节点为第 2 层，那么以上图的层次为 4
树的高度或深度：
树种节点的最大层次 ；如上图：树的高度为 4
堂兄弟节点：
双亲在同一层的节点互为堂兄弟 ；如上图：H 和 I 节点互为堂兄弟节点
节点的祖先：
从根节点到该节点所经分支上的所有节点 ；如上图：A 是所有节点的祖先
子孙节点：
以某节点为根的子树中任意节点都称为该节点的子孙节点
如上图：所有节点都是都是 A节点 的子孙
森林：
由 m(m>0) 棵互不相交的树的集合称为森林
树的结构与递归的关系
任何一棵树都可以看成：根节点和 N 棵子树构成
比如：
A 节点是根节点，以下的节点都是子树
E 节点也可以看着根节点，I 和 J 节点是子树
I 节点既是子树也是根节点，只是 I 节点没有子树
所以可以验证：树是由根节点和 N 棵子树 递归 构成的，只要当递归到叶子节点就不用递归了