## JavaScript实现树结构（一）
### 一、树结构简介
#### 1.1.简单了解树结构
**什么是树？**
真实的树：
**树的特点：**
* 树一般都有一个**根**，连接着根的是**树干**；
* 树干会发生分叉，形成许多**树枝**，树枝会继续分化成更小的**树枝**；
* 树枝的最后是**叶子**；
现实生活中很多结构都是树的抽象，模拟的树结构相当于旋转`180°`的树。
**树结构对比于数组/链表/哈希表有哪些优势呢：**
**数组：**
* 优点：可以通过**下标值访问**，效率高；
* 缺点：查找数据时需要先对数据进行**排序**，生成**有序数组**，才能提高查找效率；并且在插入和删除元素时，需要大量的**位移操作**；
**链表：**
* 优点：数据的插入和删除操作效率都很高；
* 缺点：**查找**效率低，需要从头开始依次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高。
**哈希表：**
* 优点：哈希表的插入/查询/删除效率都非常高；
* 缺点：**空间利用率不高**，底层使用的数组中很多单元没有被利用；并且哈希表中的元素是**无序**的，不能按照固定顺序遍历哈希表中的元素；而且不能快速找出哈希表中**最大值或最小值**这些特殊值。
**树结构：**
优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。
总的来说：**每种数据结构都有自己特定的应用场景**
**树结构：**
* **树（Tree）**:由 n（n ≥ 0）个节点构成的**有限集合**。当 n = 0 时，称为**空树**。
对于任一棵非空树（n > 0），它具备以下性质：
* 数中有一个称为**根（Root）**的特殊节点，用 **r **表示；
* 其余节点可分为 m（m > 0）个互不相交的有限集合 T~1~，T~2~，...，T~m~，其中每个集合本身又是一棵树，称为原来树的**子树（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；
#### 1.2.树结构的表示方式
* **最普通的表示方法**：
如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同。比如节点A需要3个引用，分别指向子节点B，C，D；B节点需要2个引用，分别指向子节点E和F；K节点由于没有子节点，所以不需要引用。
这种方法缺点在于我们无法确定某一结点的引用数。
* **儿子-兄弟表示法**：
这种表示方法可以完整地记录每个节点的数据，比如：
```
//节点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
}
```
这种表示法的优点在于每一个节点中引用的数量都是确定的。
* **儿子-兄弟表示法旋转**
以下为儿子-兄弟表示法组成的树结构：
将其顺时针旋转45°之后：
这样就成为了一棵**二叉树**，由此我们可以得出结论：**任何树都可以通过二叉树进行模拟**。但是这样父节点不是变了吗？其实，父节点的设置只是为了方便指向子节点，在代码实现中谁是父节点并没有关系，只要能正确找到对应节点即可。
### 二、二叉树
#### 2.1.二叉树简介
**二叉树的概念**：如果树中的每一个节点最多只能由**两个子节点**，这样的树就称为**二叉树**；
二叉树十分重要，不仅仅是因为简单，更是因为几乎所有的树都可以表示成二叉树形式。
**二叉树的组成**：
* 二叉树可以为空，也就是没有节点；
* 若二叉树不为空，则它由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成；
**二叉树的五种形态**：
上图分别表示：空的二叉树、只有一个节点的二叉树、只有左子树TL的二叉树、只有右子树TR的二叉树和有左右两个子树的二叉树。
**二叉树的特性**：
* 一个二叉树的第 i 层的最大节点树为：2^(i-1)^，i >= 1；
* 深度为k的二叉树的最大节点总数为：2^k^ - 1 ，k >= 1；
* 对任何非空二叉树，若 n~0~ 表示叶子节点的个数，n~2~表示度为2的非叶子节点个数，那么两者满足关系：n~0~ = n~2~ + 1；如下图所示：H，E，I，J，G为叶子节点，总数为5；A，B，C，F为度为2的非叶子节点，总数为4；满足n~0~ = n~2~ + 1的规律。
#### 2.2.特殊的二叉树
**完美二叉树**
完美二叉树（Perfect Binary Tree）也成为满二叉树（Full Binary Tree），在二叉树中，除了最下一层的叶子节点外，每层节点都有2个子节点，这就构成了完美二叉树。
**完全二叉树**
完全二叉树（Complete Binary Tree）:
* 除了二叉树最后一层外，其他各层的节点数都达到了最大值；
* 并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；
* 完美二叉树是特殊的完全二叉树；
在上图中，由于H缺失了右子节点，所以它不是完全二叉树。
#### 2.3.二叉树的数据存储
常见的二叉树存储方式为**数组**和**链表**：
**使用数组：**
* **完全二叉树**：按从上到下，从左到右的方式存储数据。
| 节点 | A | B | C | D | E | F | G | H |
| -------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| **序号** | **1** | **2** | **3** | **4** | **5** | **6** | **7** | **8** |
使用数组存储时，取数据的时候也十分方便：左子节点的序号等于父节点序号 * 2，右子节点的序号等于父节点序号 * 2 + 1 。
* **非完全二叉树**：非完全二叉树需要转换成完全二叉树才能按照上面的方案存储，这样会浪费很大的存储空间。
| 节点 | A | B | C | ^ | ^ | F | ^ | ^ | ^ | ^ | ^ | ^ | M |
| -------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ------ | ------ | ------ | ------ |
| **序号** | **1** | **2** | **3** | **4** | **5** | **6** | **7** | **8** | **9** | **10** | **11** | **12** | **13** |
**使用链表**
二叉树最常见的存储方式为**链表**：每一个节点封装成一个Node，Node中包含存储的数据、左节点的引用和右节点的引用。
### 三、二叉搜索树
#### 3.1.认识二叉搜索树
**二叉搜索树**（**BST**，Binary Search Tree），也称为**二叉排序树**和**二叉查找树**。
二叉搜索树是一棵二叉树，可以为空；
如果不为空，则满足以下**性质**：
* 条件1：非空左子树的**所有**键值**小于**其根节点的键值。比如三中节点6的所有非空左子树的键值都小于6；
* 条件2：非空右子树的**所有**键值**大于**其根节点的键值；比如三中节点6的所有非空右子树的键值都大于6；
* 条件3：左、右子树本身也都是二叉搜索树；
如上图所示，树二和树三符合3个条件属于二叉树，树一不满足条件3所以不是二叉树。
**总结：**二叉搜索树的特点主要是**较小的值**总是保存在**左节点**上，相对**较大的值**总是保存在**右节点**上。这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中"搜索"的来源。
#### 3.2.二叉搜索树应用举例
下面是一个二叉搜索树：
若想在其中查找数据10，只需要查找4次，查找效率非常高。
* 第1次：将10与根节点9进行比较，由于10 > 9，所以10下一步与根节点9的右子节点13比较；
* 第2次：由于10 < 13，所以10下一步与父节点13的左子节点11比较；
* 第3次：由于10 < 11，所以10下一步与父节点11的左子节点10比较；
* 第4次：由于10 = 10，最终查找到数据10 。
同样是15个数据，在排序好的数组中查询数据10，需要查询10次：
其实：如果是排序好的数组，可以通过二分查找：第一次找9，第二次找13，第三次找15...。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是**二叉搜索树**。这就是数组二分法查找效率之所以高的原因。
> 参考资料：[JavaScript数据结构与算法](https://www.bilibili.com/video/av86801505?from=search&seid=4967761411915016256)
