数据结构 ——— 树的概念及结构

目录

树的结构以及示意图

树的概念​编辑

树的结构与递归的关系​编辑 

---

树的结构以及示意图

树是一种非线性的数据结构，它是由 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 棵子树 递归 构成的，只要当递归到叶子节点就不用递归了