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