数据结构与算法-树

# 数据结构与算法-树

# 树结构

生活中的树

树01

树结构的特点：

树一般都有一个根，连接着根的是树干；
树干会发生分叉，形成许多树枝，树枝会继续分化成更小的树枝；
树枝的最后是叶子；

现实生活中很多结构都是树的抽象，模拟的树结构相当于旋转 180° 的树。

树02

# 树的优点

树结构对比于数组/链表/哈希表有哪些优势呢？

数组：

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

链表：

优点：数据的插入和删除操作效率都很高；
缺点：
- 查找效率低，需要从头开始依次查找，直到找到目标数据为止；
- 如果要插入和删除中间位置的数据，需要重头先找到对应的数据。查找效率不高。

哈希表：

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

树结构：

优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。
- 而且为了模拟某些场景，我们使用树结构会更加方便。比如文件的目录结构、部门结构

# 树的术语

# 树的定义

树（Tree）：由 n（n ≥ 0）个节点构成的有限集合。当 n = 0 时，称为空树。

对于任意一棵非空树（n > 0），它具备以下性质：

数中有一个称为根（Root）的特殊节点，用 r 表示；
其余节点可分为 m（m > 0）个互不相交的有限集合 T1，T2，...，Tm，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）。

树03

树的常用术语：

节点的度（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；

# 树的表示

树有多种表示方式

# 最普通表示

树04

如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。

不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引用，分别指向子节点 B，C，D；B 节点需要 2 个引用，分别指向子节点 E 和 F；K 节点由于没有子节点，所以不需要引用。

这种方法缺点在于我们无法确定某一节点的引用数。

在代码实现时无法很好地进行标识，比如A节点有B、C、D三个子节点，如果再有X、Y、Z三个子节点，表示就有一定的困难性。

//节点A
Node{
  //存储数据
  this.data = data
  //统一只记录左边的子节点
  this.left = B
  this.middle = C
  this.right = D
  // X Y Z如何表示呢
  // ...
}

# 儿子-兄弟表示法

树05

这种表示方法可以完整地记录每个节点的数据。

每个节点只有两个引用，一个引用指向子节点，没有子节点则为null；另一个引用指向兄弟节点，没有则为null。

这种表示法的优点在于每一个节点中引用的数量都是确定的。

// 节点A
Node{
  // 存储数据
  this.data = data
  // 统一只记录左边的子节点
  this.leftChild = B
  // 统一只记录右边的第一个兄弟节点
  this.rightSibling = null
}

// 节点B
Node{
  this.data = data
  this.leftChild = E
  this.rightSibling = C
}

// 节点F
Node{
  this.data = data
  this.leftChild = null
  this.rightSibling = null
}

每个节点只需要3个属性，就可以完整地记录每个节点的数据。

# 儿子-兄弟表示法旋转

儿子-兄弟表示法组成的树结构顺时针旋转 45° 。

表示：

树08

旋转后节点的引用可看作左右引用，左引用指向子节点，右引用指向兄弟节点。

每个节点最多只有两个子节点，这样就成为了一棵二叉树，由此我们可以得出结论：所有的树本质上都可以使用二叉树模拟出来。

# 二叉树

如果树中每个节点最多有两个子节点，这样的树就称为二叉树。

二叉树可以为空，也就是没有节点；若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

# 二叉树的形态

二叉树有五种形态：

空的二叉树
只有一个节点的二叉树
只有左子树 TL 的二叉树
只有右子树 TR 的二叉树
有左右两个子树的二叉树。

树09

# 二叉树的特性

二叉树有几个比较重要的特性：

一个二叉树的第 i 层的最大节点数为： $2^{i-1}$ ，i >= 1
深度为 k 的二叉树的最大节点总数为： $2^k - 1$ ，k >= 1
对任何非空二叉树，若 $n_0$ 表示叶子节点的个数， $n_2$ 表示度为 2 的非叶子节点个数，那么两者满足关系： $n_0 = n_2 + 1$ ；

树10

如上图所示：H，E，I，J，G 为叶子节点，总数为 5；A，B，C，F 为度为 2 的非叶子节点，总数为 4；满足 $n_0 = n_2 + 1$ 的规律。

证明：假设有一个二叉树，度为2的节点有 $n_2$ 个，度为1的节点有 $n_1$ 个，叶子节点有 $n_0$ 个，那么这个二叉树的边数为 $2n_2 + n_1$ ；又这个二叉树的边数为 $n_0 + n_1 + n_2 - 1$ ；所以 $2n_2 + n_1 = n_0 + n_1 + n_2 - 1$ ，即 $n_0 = n_2 + 1$ 。也就是叶子节点个数总比度为2的节点个数多1个。