树

今天我们会介绍树这种数据结构，树作为数据存储的一种结构，相对于栈、队列和表要相对复杂一些。也是一种常见的数据结构，例如我们文件在计算机中就是以树的结构进行存储的。

文件夹结构

我们公司中组织架构也通常是一种树形结构

组织架构

不过在计算机中重点研究的就是二叉树，不过我们还是先从树开始介绍，首先我们应该知道树是一种非线性的数据结构，可以表现一种多对一的关系。

树结构

这种一对多的关系表现为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 在第三层，以此类推。