前言

现实中的树有着十分清晰的结构，从根开始连着树干，树干又进行分化成为树枝，树枝又可以分裂成多个树枝，树枝上最后有着树叶，现实生活中很多结构都是树的抽象（180°旋转的树），比如公司的组织架构，家族的家谱，但都万变不离其中，如图：
image.png
而在真实的开发中，我们常将树分为两个分支，这就是我们之后要学习的二叉树
**

树的优势

我们为什么要学习树？树相对于链表，数组，哈希表而言又有着什么优势呢？
首先我们讨论下不同数据结构的优缺点：
数组

  • 优点：可以通过下标值访问，效率高；
  • 缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作；

链表

  • 优点：数据的插入和删除操作效率都很高；
  • 缺点：查找效率低，需要从头开始依次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高。

哈希表

  • 优点：哈希表的插入/查询/删除效率都非常高；
  • 缺点：空间利用率不高，底层使用的数组中很多单元没有被利用；并且哈希表中的元素是无序的，不能按照固定顺序遍历哈希表中的元素；而且不能快速找出哈希表中最大值或最小值这些特殊值。

树结构

  • 优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。

总的来说：每种数据结构都有自己特定的应用场景。

树的常用术语

树结构：

  • 树（Tree）：由 n（n ≥ 0）个节点构成的有限集合。当 n = 0 时，称为空树。
  • 对于任意一棵非空树（n > 0），它具备以下性质：
    • 数中有一个称为根（Root）的特殊节点，用 r 表示；
    • 其余节点可分为 m（m > 0）个互不相交的有限集合 T1，T2，…，Tm，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）。
  • 节点的度（Degree）：节点的子树个数，比如节点 B 的度为 2；
  • 树的度：树的所有节点中最大的度数，如上图树的度为 2；
  • 叶节点（Leaf）：度为 0 的节点（也称为叶子节点），如上图的 H，I 等；
  • 父节点（Parent）：度不为 0 的节点称为父节点，如上图节点 B 是节点 D 和 E 的父节点；
  • 子节点（Child）：若 B 是 D 的父节点，那么 D 就是 B 的子节点；
  • 兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点，比如上图的 B 和 C，D 和 E 互为兄弟节点；
  • 路径和路径长度：路径指的是一个节点到另一节点的通道，路径所包含边的个数称为路径长度，比如 A->H 的路径长度为 3；
  • 节点的层次（Level）：规定根节点在 1 层，其他任一节点的层数是其父节点的层数加 1。如 B 和 C 节点的层次为 2；
  • 树的深度（Depth）：树种所有节点中的最大层次是这棵树的深度，如上图树的深度为 4；

树的简单表示

数据结构（八）———树 - 图2

如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引用，分别指向子节点 B，C，D；B 节点需要 2 个引用，分别指向子节点 E 和 F；K 节点由于没有子节点，所以不需要引用，但是我们无法确定某一结点的引用数。

儿子—兄弟表示法：**
image.png
这种结构的结点树固定，每个节点中引用的数量都固定

  1. //节点A
  2. Node{
  3.   //存储数据
  4.   this.data = data
  5.   //统一只记录左边的子节点
  6.   this.leftChild = B
  7.   //统一只记录右边的第一个兄弟节点
  8.   this.rightSibling = null
  9. }
  11. //节点B
  12. Node{
  13.   this.data = data
  14.   this.leftChild = E
  15.   this.rightSibling = C
  16. }
  18. //节点F
  19. Node{
  20.   this.data = data
  21.   this.leftChild = null
  22.   this.rightSibling = null
  23. }

儿子—兄弟旋转表示法
image.png

故此我们可以清晰的发现：

  • 其实所有树的本质都可以用二叉树模拟出来
  • 所以二叉树是十分重要的