树
今天我们会介绍树这种数据结构 ， 树作为数据存储的一种结构 ， 相对于栈、队列和表要相对复杂一些 。也是一种常见的数据结构 ， 例如我们文件在计算机中就是以树的结构进行存储的 。
文章插图
文件夹结构
我们公司中组织架构也通常是一种树形结构
文章插图
组织架构
不过在计算机中重点研究的就是二叉树 ， 不过我们还是先从树开始介绍 ， 首先我们应该知道树是一种非线性的数据结构 ， 可以表现一种多对一的关系 。
文章插图
树结构
这种一对多的关系表现为A 对 B 和 C 的关系 ， B 对 D、E 和 F 的关系 。接下来我们介绍一下树构成以及构成树每一个部分
结点
使用树结构存储的每一个数据元素都被称为结点 ， 在上图 A、B 和 G 都是结点 。结点根据关系又分为根节点、父节点和子节点 。对于 D、E 和 F 他们父结点是 B ， 翻过来说 B 的子结点是 D、E 和 F 。D、E 和 F 他们之间是兄弟结点的关系 。每一个非空树都有且只有一个被称为根结点 ， 图中根节点就是 A 。对于结点没有任何子结点 ， 那么此结点称为叶子结点（叶结点） ， 图中 H、F、D 和 G 都是叶子结点 。
子树和空树
- 子树
在图中 B 、D、E 和 F 有组成以 B 为根结点的数 ， 这几个结点组成的树为整棵树的子树 。
【支持递归算法的数据结构是栈还是树】单个结点也是一棵树 ， 只不过根结点就是他本身 ， G 也是一棵树 。
- 空树
如果集合本身为空 ， 那么构成的树就被称为空树 。空树中没有结点 。
知道了子树的概念后 ， 树也可以这样定义 ， 树是由根结点和若干棵子树构成的 。
在树结构中 ， 对于具有同一个根结点的各个子树 ， 相互之间不能有交集 。如果有 ， 就破坏了树的结构 ， 不能算做是一棵树 。结点的度
一个节点含有的子树的个数称为该结点的度 。
文章插图
结点的度
叶节点或终端节点：度为 0 的节点称为叶节点 ， 非终端节点或分支节点 ， 度不为 0 的节点 。图中这里 B 节点有 D、E 和 F 三个节点 ， 也就是 B 节点的度为 3 。A 节点有 B 和 C 两个节点 ， 也就是度为 2 ， F 因为没有子节点所有节点 F 度为 0 。
一棵树的度是树内各结点的度的最大值 ， 图中树度为 3 。结点的层次
文章插图
结点的层次
结点的层次 ， 从一棵树的树根开始 ， 树根所在层为第一层 ， 根的孩子结点所在的层为第二层 ， 依次类推 。对于图 A 来说 ， A 结点在第一层 ， B、C 为第二层 ， D、E、F、G 在第三层 ， 以此类推 。
推荐阅读
- 高级生命支持包括哪些
- 三星s10支持多大功率快充 三星s10支持多少瓦快充
- 杭州地铁充值如何开发票 目前仅支持电子发票
- 魅蓝note6支持北斗吗
- 苹果x支持5g吗
- 华为P10支持无线充电吗
- 7p支持无线充电嘛 苹果7p能不能使用无线充电
- 苹果八支持无线充电吗
- 华为P9会支持快充吗
- vivo支持快充吗